本文主要是介绍uva 10047 Problem A: The Monocycle (搜索:BFS+优先队列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一道很简单的BFS题目...居然用了两个小时
原因就是开始题目没有读清楚,原来转向还需要1S
而且也没有用优先队列,所以我的结果不是最优的
最后想通了就好做了
好像我的做法和很多人都不一样,别人的思路都是先让车子转向后进栈
在出栈的时候再执行前进操作
而我是直接分四个方向判断,感觉这样虽然代码长了些,但是思路很清晰,很容易理解
代码如下:
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 30
#define LL long long
using namespace std;/* col含义: | dir含义:* 0 - 绿色 | 0 - 北* 1 - 黑色 | 1 - 西* 2 - 红色 | 2 - 南* 3 - 蓝色 | 3 - 东* 4 - 白色 |*/int m, n, ans;
int g[MAXN][MAXN];
bool vis[MAXN][MAXN][MAXN][MAXN];struct Position {int x, y, dir, col, time;bool operator < (const Position& rhs) const {return time > rhs.time;}
}start, end;bool BFS(Position start, Position end) {Position tmp, cur;priority_queue<Position> q;memset(vis, 0, sizeof(vis));start.col = 0;start.dir = 0;start.time = 0;end.col = 0;q.push(start);while(!q.empty()) {tmp = q.top();q.pop();vis[tmp.x][tmp.y][tmp.dir][tmp.col] = true;
// cout << "tmp.x = " << tmp.x << "\ttmp.y = " << tmp.y << endl << endl;if(tmp.x==end.x && tmp.y==end.y && tmp.col==end.col) {ans = tmp.time;return true;}if(tmp.x-1>=0 && g[tmp.x-1][tmp.y]==0 && !vis[tmp.x-1][tmp.y][0][(tmp.col+1)%5]) {//车子向北走cur.x = tmp.x-1;cur.y = tmp.y;cur.col = (tmp.col+1)%5;cur.dir = 0;cur.time = tmp.time+1;if(tmp.dir == 2) cur.time += 2;else if(tmp.dir != 0) cur.time++;q.push(cur);}if(tmp.y-1>=0 && g[tmp.x][tmp.y-1]==0 && !vis[tmp.x][tmp.y-1][1][(tmp.col+1)%5]) {//车子向西走cur.x = tmp.x;cur.y = tmp.y-1;cur.col = (tmp.col+1)%5;cur.dir = 1;cur.time = tmp.time+1;if(tmp.dir == 3)cur.time += 2;else if(tmp.dir != 1)cur.time++;q.push(cur);}if(tmp.x+1<m && g[tmp.x+1][tmp.y]==0 && !vis[tmp.x+1][tmp.y][2][(tmp.col+1)%5]) {//车子向南走cur.x = tmp.x+1;cur.y = tmp.y;cur.col = (tmp.col+1)%5;cur.dir = 2;cur.time = tmp.time+1;if(tmp.dir == 0)cur.time += 2;else if(tmp.dir != 2)cur.time++;q.push(cur);}if(tmp.y+1<n && g[tmp.x][tmp.y+1]==0 && !vis[tmp.x][tmp.y+1][3][(tmp.col+1)%5]) {//车子向东走cur.x = tmp.x;cur.y = tmp.y+1;cur.col = (tmp.col+1)%5;cur.dir = 3;cur.time = tmp.time+1;if(tmp.dir == 1)cur.time += 2;else if(tmp.dir != 3)cur.time++;q.push(cur);}}return false;
}int main(void) {char ch;int cnt = 1;while(scanf("%d%d", &m, &n) && m+n) {memset(g, 0, sizeof(g));for(int i=0; i<m; ++i) {getchar();for(int j=0; j<n; ++j) {ch = getchar();if(ch == 'S') {start.x = i;start.y = j;g[i][j] = 0;} else if(ch == 'T') {end.x = i;end.y = j;g[i][j] = 0;} else if(ch == '#') {g[i][j] = -1;} else {g[i][j] = 0;}}}if(cnt != 1)cout << endl;printf("Case #%d\n", cnt++);if(BFS(start, end)) {printf("minimum time = %d sec\n", ans);} else cout << "destination not reachable" << endl;}return 0;
}这篇关于uva 10047 Problem A: The Monocycle (搜索:BFS+优先队列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
