本文主要是介绍hdu(2579) Dating with girls(2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个题有意思的是：墙可以消失，只要时间是k的倍数，
在此时墙都可以消失一秒，
单此题不同之处就是，每一个点可以走多次，但必须是在不同的时刻，
这就必须要用三维数组来标记了。
visit[i][j][s/k]表示在（i，j）这个点在s/k的时刻走过了。。
所以在本题可以行走的条件是；
一；map[i][j]=='.'；
二；map[i][j]=='#'and s/k==0时；任意一个都行。。
#include"stdio.h"
#include"string.h"
#include"queue"
int visit[200][200][200];
char map[200][200];
int dir[4][2]={-1,0, 0,1, 1,0, 0,-1};
using namespace std;
int n,m,k,sx,sy;
struct point
{
int x,y;
int step;
};
int judge(int x,int y,int s)
{
if(x>=0&&x<n&&y>=0&&y<m&&(map[x][y]!='#'||(map[x][y]=='#'&&s%k==0)))
return 1;
return 0;
}
int bfs(int x,int y)
{
int i;
memset(visit,0,sizeof(visit));
queue<point>q;
point cur,next;
cur.x=x,cur.y=y,cur.step=0;
visit[x][y][0]=1;
q.push(cur);
while(!q.empty())
{
next=q.front();
q.pop();
if(map[next.x][next.y]=='G')
return next.step;
for(i=0;i<4;i++)
{
cur.x=next.x+dir[i][0];
cur.y=next.y+dir[i][1];
cur.step=next.step+1;
if(judge(cur.x,cur.y,cur.step)&&visit[cur.x][cur.y][cur.step%k]==0)
{
visit[cur.x][cur.y][cur.step%k]=1;
q.push(cur);
}
}
}
return -1;
}
int main()
{
int i,j,p,t;
scanf("%d",&p);
while(p--)
{
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<n;i++)
{
scanf("%s",map[i]);
for(j=0;j<m;j++)
{
if(map[i][j]=='Y')
{
sx=i;
sy=j;
}
}
}
t=bfs(sx,sy);
if(t!=-1)
printf("%d\n",t);
else
printf("Please give me another chance!\n");
}
return 0;
}
这篇关于hdu(2579) Dating with girls(2)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
