HDU-2579:Dating with girls(2)

BFS

题面链接

• 题意

  男孩子Y要找女孩子G约会，其中会有石头和平地，当所用时间为k的倍数时石头变为平地是可以走的,如果能够找到女孩，输出最短时间，否则输出"Please give me another chance!"
  我们可以直接看样例

  Sample Input
  1 ///代表测试数据组数
  6 6 2 ///6*6的矩阵其中k=2
  ...Y..
  ...#..
  .#....
  ...#..
  ...#..
  ..#G#.

  Sample Output
  7

• 代码

#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
int i,j,l,dir[4][2]={1,0,-1,0,0,1,0,-1},vis[111][111][20],t,r,c,k,x,y,ex,ey,xx,yy;
char a[111][111];
struct node
{
    int x,y,time;
};
void BFS()
{
    queue<node>q;
    node now,next;
    now.x=x;
    now.y=y;
    now.time=0;
    q.push(now);
    for(i=1;i<=r;i++)
        for(j=1;j<=c;j++)
           for(l=0;l<=k;l++)
              vis[i][j][l]=1000000000;
    vis[x][y][0]=0;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(now.x==ex&&now.y==ey)
        {
            printf("%d\n",now.time);
            return;
        }
            for(i=0;i<4;i++)
        {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(next.x<1||next.x>r||next.y<1||next.y>c)
                continue;
            next.time=now.time+1;
            if(a[next.x][next.y]!='#'&&vis[next.x][next.y][next.time%k]>next.time)
              {
                 vis[next.x][next.y][next.time%k]=next.time;
                 q.push(next);
                 continue;
              }
            if(a[next.x][next.y]=='#'&&next.time%k==0&&vis[next.x][next.y][next.time%k]>next.time)
              {
                 vis[next.x][next.y][next.time%k]=next.time;
                 q.push(next);
              }
         }
    }
    printf("Please give me another chance!\n");
}
int main()
{
   scanf("%d",&t);
   while(t--)
   {
       scanf("%d%d%d",&r,&c,&k);
       for(i=1;i<=r;i++)
       {
           scanf("%s",&a[i][1]);
           for(j=1;j<=c;j++)
       {
           if(a[i][j]=='Y')
           {
               x=i;
               y=j;
           }
           if(a[i][j]=='G')
           {
               ex=i;
               ey=j;
           }
       }
       }
       BFS();
   }
   return 0;
}