本文主要是介绍10047 - The Monocycle（BFS +状态判断），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：10047 - The Monocycle
题目大意：还是迷宫问题，只是这次有要求方向和轮子着地的颜色。
解题思路：BFS ，但是需要判断状态， 并且一个格子不在是走过一次就不可以走了，而是要判断走过这个格子的轮子的方向啊，颜色啊，所以那个是否走过格子的数组是四元数组，刚开始没有想到这个，不知道到了终点后颜色不符合要求该怎么办，后面看了别人的代码，才发现可以都遍历一遍，看看有没有符合要求的最短的。剩下的就是要细心了，这题很麻烦。
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;const int N = 30;
int r, c, t;
char map[N][N];
int visit[4][5][N][N], time;struct M {int x, y, dre, cor, time;
};int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};queue<M> q;int bfs(M x) {visit[x.dre][x.cor][x.x][x.y] = 1;q.push(x);while(!q.empty()) {x = q.front();q.pop();for(int i = 0; i < 4; i ++) {if((x.dre + 2) % 4 != i) {int x1 = x.x + dir[i][0];int y1 = x.y + dir[i][1];M y;int a = x.time;if(i == x.dre ) {if(x1 >= 0 && x1 < r && y1 >= 0 && y1 < c) {if(map[x1][y1] != '#' && !visit[i][(x.cor + 1) % 5][x1][y1]) {visit[i][(x.cor + 1) % 5][x1][y1] = 1;y.time = a + 1;y.x = x1;y.y = y1;y.cor = (x.cor + 1) % 5;y.dre = i;if(map[x1][y1] == 'T' && y.cor == 0) {time = y.time;return true;}q.push(y);} }}else if(!visit[i][x.cor][x.x][x.y]){visit[i][x.cor][x.x][x.y] = 1;y.x = x.x;y.y = x.y;y.dre = i;y.cor = x.cor;y.time = a + 1;q.push(y);}}}}return false;
}int main() {while(scanf("%d%d", &r, &c), r || c) {t++;if(t != 1)printf("\n");memset(map, 0, sizeof(map));memset(visit, 0, sizeof(visit));int i, j;for(i = 0; i < r; i++)scanf("%s", map[i]);M S;for(i = 0; i < r; i++) for(j = 0; j < c; j++) {if(map[i][j] == 'S') {S.x = i;S.y = j;S.dre = 0;S.cor = 0;S.time = 0;}}printf("Case #%d\n", t);time = 0;if(bfs(S)) printf("minimum time = %d sec\n", time);elseprintf("destination not reachable\n");while(!q.empty()) {q.pop();}}return 0;
}这篇关于10047 - The Monocycle（BFS +状态判断）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
