首页 > 代码库 > 【BFS】uva10047The Monocycle
【BFS】uva10047The Monocycle
/* 本题的特殊之处,到达一个格子时,因为朝向不同,以及接触地面的颜色不同, 会处于不同的状态;;;;;;;;; 把(x, y, d, c)作为一个结点,表示所在位置(x, y),方向为d,颜色为c;;;;; ------------------------------------------------------------------------ 在方向上我们把前,左,右编号为0,1,2;;;; 颜色,从蓝色开始编号为0,1,2,3;;;;;;;;;; -------------------------------------------------------------------------- vis[x1][y1][0][0] = 1;起点S进入队列 node a, b; a.x = x1; a.y = y1; a.d = 0; a.c = 0; a.t = 0; q.push(a); ----------------------------------------------------------------------- b.t = a.t + 1;前进方向;;;时间加1 b.c = (a.c + 1)%5;扩展后的颜色 b.x = a.x + d[a.d][0];扩展后的位置 b.y = a.y + d[a.d][1]; b.d = a.d;方向不变 if(judge(b)) { if(b.x == x2 && b.y == y2 && b.c == 0)是否到达终点 return b.t; vis[b.x][b.y][b.d][b.c] = 1; q.push(b); } ---------------------------------------------------------------------------------- b = a;向右转 b.t ++; b.d = (b.d + 1)%4;扩展后的方向 if(judge(b)) { vis[b.x][b.y][b.d][b.c] = 1; q.push(b); } b = a;向左转 b.t ++; b.d = (b.d - 1 + 4)%4; if(judge(b)) { vis[b.x][b.y][b.d][b.c] = 1; q.push(b); } ------------------------------------------------------------------- for(int i=0; i<m; i++)寻找始末点S和T点 { for(int j=0; j<n; j++) { if(g[i][j] == 'S') { x1 = i; y1 = j; break; } } } for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(g[i][j] == 'T') { x2 = i; y2 = j; break; } } } ------------------------------------------------------------------------------ */ #include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define INF 0x3f3f3f3f using namespace std; const int MAXN = 30; struct node { int x, y, d, c, t; }; int m, n; char g[MAXN][MAXN]; int vis[MAXN][MAXN][6][6]; int x1, x2, y1, y2; int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; int judge(node b) { if(b.x < 0 || b.x >= m || b.y < 0 || b.y >= n) return false; if(g[b.x][b.y] == '#') return false; if(vis[b.x][b.y][b.d][b.c]) return false; return true; } int bfs() { queue<node> q; vis[x1][y1][0][0] = 1; node a, b; a.x = x1; a.y = y1; a.d = 0; a.c = 0; a.t = 0; q.push(a); while(!q.empty()) { a = q.front(); q.pop(); b.t = a.t + 1; b.c = (a.c + 1)%5; b.x = a.x + d[a.d][0]; b.y = a.y + d[a.d][1]; b.d = a.d; if(judge(b)) { if(b.x == x2 && b.y == y2 && b.c == 0) return b.t; vis[b.x][b.y][b.d][b.c] = 1; q.push(b); } b = a; b.t ++; b.d = (b.d + 1)%4; if(judge(b)) { vis[b.x][b.y][b.d][b.c] = 1; q.push(b); } b = a; b.t ++; b.d = (b.d - 1 + 4)%4; if(judge(b)) { vis[b.x][b.y][b.d][b.c] = 1; q.push(b); } } return -1; } int main() { //freopen("input.txt","r",stdin); int kase = 1; while(scanf("%d%d",&m,&n) != EOF && (n+m)) { if(kase != 1) printf("\n"); printf("Case #%d\n",kase++); getchar(); for(int i=0; i<m; i++) gets(g[i]); for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(g[i][j] == 'S') { x1 = i; y1 = j; break; } } } for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(g[i][j] == 'T') { x2 = i; y2 = j; break; } } } memset(vis, 0, sizeof(vis)); int time = bfs(); if(time == -1) printf("destination not reachable\n"); else printf("minimum time = %d sec\n",time); } return 0; }
----------------------------
wuwuwuwuwuwuwuwu...................................
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。