题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2579
题目大意：走迷宫。对于障碍点，只有当前（dep+1）%k才能走，问最少时间。
解题思路：
只有一个关键：
每个点不是只可以走一次。最多可以走k次。
原因是对于一个点，可能是通过障碍点在k的倍数（即余数为0）步到达的，也可能是通过其它途径到达的，但是不是k的倍数（余数为1~k）。
这样，判断状态是否重叠的依据就是看在(x,y)点的余数状态了。vis的第三维非常重要。
#include "cstdio"
#include "string"
#include "cstring"
#include "iostream"
#include "queue"
using namespace std;
int n,m,k,sx,sy,ex,ey,T,vis[][][],dir[][]={-,,,,,-,,};
char map[][];
struct status
{
int x,y,dep;
status(int x,int y,int dep):x(x),y(y),dep(dep) {}
};
int bfs(int x,int y)
{
queue<status> Q;
Q.push(status(x,y,));
vis[x][y][]=true;
while(!Q.empty())
{
status t=Q.front();Q.pop();
for(int s=;s<;s++)
{
int X=t.x+dir[s][],Y=t.y+dir[s][],dep=t.dep+;
if(X<||X>n||Y<||Y>m) continue;
if(map[X][Y]=='#')
{
if(dep%k==&&!vis[X][Y][dep%k])
{
vis[X][Y][dep%k]=true;
Q.push(status(X,Y,dep));
}
}
else
{
if(vis[X][Y][dep%k]) continue;
if(X==ex&&Y==ey) return dep;
vis[X][Y][dep%k]=true;
Q.push(status(X,Y,dep));
}
}
}
return -;
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
string tt;
cin>>T;
while(T--)
{
memset(vis,,sizeof(vis));
cin>>n>>m>>k;
for(int i=;i<=n;i++)
{
cin>>tt;
for(int j=;j<tt.size();j++)
{
map[i][j+]=tt[j];
if(tt[j]=='Y') {sx=i;sy=j+;}
if(tt[j]=='G') {ex=i;ey=j+;}
}
}
int ans=bfs(sx,sy);
if(ans==-) cout<<"Please give me another chance!"<<endl;
else cout<<ans<<endl;
}
}
| 11899492 | 2014-10-18 10:10:31 | Accepted | 2579 | 0MS | 964K | 1734B | C++ | Physcal |