题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1072
题目大意：走迷宫。走到装置点重置时间，到达任一点时的时间不能为0，可以走重复路，求出迷宫最短时间。
解题思路：
vis的第三维标记一下到这个格子的时间。
尽管可以格子可以重复走，但在相同时间到这个格子是没有意义的。
小心一下时间不能为0的问题就行了。
#include "cstdio" #include "queue" #include "cstring" using namespace std; struct status { int x,y,t,time; status(int x,int y,int t,int time):x(x),y(y),t(t),time(time) {} }; int n,m,sx,sy,map[10][10],dir[4][2]={0,-1,0,1,-1,0,1,0}; bool vis[10][10][10]; int bfs(int sx,int sy) { queue<status> Q; vis[sx][sy][6]=true; Q.push(status(sx,sy,0,6)); while(!Q.empty()) { status s=Q.front();Q.pop(); for(int i=0;i<4;i++) { int X=s.x+dir[i][0],Y=s.y+dir[i][1],time; if(X<1||X>n||Y<1||Y>m||map[X][Y]==0) continue; if(s.time<=1) continue; if(map[X][Y]==4) time=6; else time=s.time-1; if(vis[X][Y][time]) continue; vis[X][Y][time]=true; if(map[X][Y]==3) return s.t+1; Q.push(status(X,Y,s.t+1,time)); } } return -1; } int main() { //freopen("in.txt","r",stdin); int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&map[i][j]); if(map[i][j]==2) {sx=i;sy=j;} } int ans=bfs(sx,sy); printf("%d ",ans); } }
| 2867257 | 2015-02-02 00:12:36 | Accepted | 1072 | 0MS | 1100K | 1337 B | C++ | Physcal |