Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2705 Accepted Submission(s):
759
题意：给一个迷宫Y是起点，G是终点，#是石头不能通过 .是路可以走，但是当走到的步数step%k==0时#全部变为路可以通过，问从起点到终点的最少步数
题解：此题不用标记走过的路，但要避免走的路径重复走，同一个路径只在同一个时刻走过（当再次走到这个点且step%k刚好再次与此时相同时 不可以走），用一个三维数组标记
从起点到终点，bfs，不同的是对于图中的点，可能走多次，分别是在不同的时刻。
vis[ t%k ][ i ][ j ]=1:表示坐标（ i，j ）在 t %k 时刻走过，接下来再出现 t%k 就不用再走一次了。
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define MAX 110
#define INF 0x7ffff
using namespace std;
int n,m,k;
char map[MAX][MAX];
int vis[MAX][MAX][MAX];
int b,e;
struct node
{
int x,y;
int step;
friend bool operator <(node a,node b)
{
return a.step>b.step;
}
};
int judge(int a,int b)
{
if(a<0||a>=n||b<0||b>=m)
return 0;
return 1;
}
void bfs()
{
int move[4][2]={1,0,-1,0,0,1,0,-1};
node beg,end;
priority_queue<node>q;
while(!q.empty())
q.pop();
memset(vis,0,sizeof(vis));
beg.x=b;
beg.y=e;
beg.step=0;
vis[0][b][e]=1;
q.push(beg);
while(!q.empty())
{
end=q.top();
q.pop();
if(map[end.x][end.y]==‘G‘)
{
printf("%d\n",end.step);
return ;
}
for(int i=0;i<4;i++)
{
beg.x=end.x+move[i][0];
beg.y=end.y+move[i][1];
if(judge(beg.x,beg.y))
{
if(map[beg.x][beg.y]!=‘#‘)
{
beg.step=end.step+1;
if(!vis[beg.step%k][beg.x][beg.y])
{
vis[beg.step%k][beg.x][beg.y]=1;
q.push(beg);
}
}
else
{
beg.step=end.step+1;
if(!vis[beg.step%k][beg.x][beg.y]&&beg.step%k==0)
{
vis[beg.step%k][beg.x][beg.y]=1;
q.push(beg);
}
}
}
}
}
printf("Please give me another chance!\n");
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<n;i++)
scanf("%s",map[i]);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(map[i][j]==‘Y‘)
{
b=i;
e=j;
}
}
}
bfs();
}
return 0;
}
hdoj 2579 Dating with girls(2)【三重数组标记去重】
原文：http://www.cnblogs.com/tonghao/p/4940672.html