Dating with girls(2) HDU - 2579

If you have solved the problem Dating with girls(1).I think you can solve this problem too.This problem is also about dating with girls. Now you are in a maze and the girl you want to date with is also in the maze.If you can find the girl, then you can date with the girl.Else the girl will date with other boys. What a pity!
The Maze is very strange. There are many stones in the maze. The stone will disappear at time t if t is a multiple of k(2<= k <= 10), on the other time , stones will be still there.
There are only ‘.’ or ‘#’, ’Y’, ’G’ on the map of the maze. ’.’ indicates the blank which you can move on, ‘#’ indicates stones. ’Y’ indicates the your location. ‘G’ indicates the girl's location . There is only one ‘Y’ and one ‘G’. Every seconds you can move left, right, up or down.
Dating with girls(2) HDU - 2579

Input

The first line contain an integer T. Then T cases followed. Each case begins with three integers r and c (1 <= r , c <= 100), and k(2 <=k <= 10).
The next r line is the map’s description.

Output

For each cases, if you can find the girl, output the least time in seconds, else output "Please give me another chance!".

Sample Input

1
6 6 2
...Y..
...#..
.#....
...#..
...#..
..#G#.

Sample Output

题意：男孩子Y要找女孩子G约会，其中会有墙和路，当所用时间为k的倍数时墙会变成路,
如果能够找到女孩，输出最短时间，否则输出"Please give me another chance!"

思路：
这道题跟一般的bfs不一样的是墙会消失，所以要建立一个三维数组，来保存每个点的时间状态，因为那些障碍物会在第k的倍数消失，
所以在该点来走过也是可以再走的，除了横纵坐标外，另一个就是time%k。
代码：
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
struct node//建立结构体
{
int x,y,time;
};
char mapp[120][120];
int book[120][120][120];
int r,c,k,t,sx,sy,flag;
int nextt[4][2]={0,1,1,0,0,-1,-1,0};
void bfs()
{
queue<node>Q;
node p,q;
p.x=sx;
p.y=sy;
p.time=0;
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(mapp[p.x][p.y]=='G')//找到女孩
{
flag=1;
printf("%d\n",p.time);
return;
}
for(int i=0;i<4;i++)
{
q.x=p.x+nextt[i][0];
q.y=p.y+nextt[i][1];
q.time=p.time+1;
if(q.x<0||q.y<0||q.y>=c||q.x>=r||book[q.x][q.y][q.time%k])//边界
continue;
if(mapp[q.x][q.y]=='#'&&q.time%k)
continue;
book[q.x][q.y][q.time%k]=1;
Q.push(q);
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&r,&c,&k);
flag=0;
memset(book,0,sizeof(book));
for(int i=0;i<r;i++)//输入
scanf("%s",mapp[i]);
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(mapp[i][j]=='Y')//记录起始坐标
{
sx=i;
sy=j;break;
}
}
}
book[sx][sy][0]=1;
bfs();
if(!flag)
printf("Please give me another chance!\n");
}
return 0;
}

Dating with girls(2) HDU - 2579

相关推荐