题目链接: 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[][],dir[][]={,-,,,-,,,};
bool vis[][][];
int bfs(int sx,int sy)
{
queue<status> Q;
vis[sx][sy][]=true;
Q.push(status(sx,sy,,));
while(!Q.empty())
{
status s=Q.front();Q.pop();
for(int i=;i<;i++)
{
int X=s.x+dir[i][],Y=s.y+dir[i][],time;
if(X<||X>n||Y<||Y>m||map[X][Y]==) continue;
if(s.time<=) continue;
if(map[X][Y]==) time=;
else time=s.time-;
if(vis[X][Y][time]) continue;
vis[X][Y][time]=true;
if(map[X][Y]==) return s.t+;
Q.push(status(X,Y,s.t+,time));
}
}
return -;
}
int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]==) {sx=i;sy=j;}
}
int ans=bfs(sx,sy);
printf("%d\n",ans);
}
}
| 2867257 | 2015-02-02 00:12:36 | Accepted | 1072 | 0MS | 1100K | 1337 B | C++ | Physcal |