HDU 2579 Dating with girls(2)(BFS)

HDU 2579 Dating with girls(2)(BFS)

http://acm.hdu.edu.cn/showproblem.php?pid=2579

题意:依然是一个R*C的迷宫,要你找从起点到终点的最短距离,但是这里有点小变化,如果是障碍的格子在k倍数的时间点会消失.

分析:一般的BFS,直接做即可.需要vis与dist数组.

注意在此题中,人不能停留,也就是说如果你在此时走到障碍前,但是障碍下一秒不消失,你不能在这等到障碍消失.

所以如果我们仅仅用2维数组表示dist的话,就是错的.假设K=4,现在如果我们在5秒到达了(3,3)格子,也就是说我们花了5秒最短时间到了(3,3)格子,但是此时(3,4)格子是障碍,我们到不了(3,4)格子.但是如果我们能在7秒到达(3,3)格子,我们就能在第8秒到达(3,4)格子.

这里我们是不是应该把到达(3,3)格子的时间反而取大的值呢?不用,因为5和7秒是不同的两个时间属性,5秒到(3,3)或许能到一些7秒到(3,3)到不了的格子.5与7的区别仅在5%4==1而7%4==3.所以我们这里加一维dist[r][c][yu],最后一维表示我们在时间%K==yu的时间点上到了r,c格子.

由上面分析可知对于1%4==1和5%4==1,如果1秒和5秒都到了同一个网格坐标的话,我们取1秒到达的时间即可,因为任意5秒能到的网格,从1秒也能到.(想想是不是)

AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=105;
int dr[]={-1,1,0,0};//上下左右
int dc[]={0,0,-1,1};
int R,C,K;
char map[maxn][maxn];
int dist[maxn][maxn][11];//dist最后一维是 时间%K的余数
int r1,c1,r2,c2;
struct Node
{
    int r,c,time;//time是人到当前状态的时间%K的余
    Node(int r,int c,int t):r(r),c(c),time(t){}
};
bool can_move(int r,int c,int time)
{
    if(dist[r][c][time]==-1 && (map[r][c]=='.'||time==0) ) return true;
    return false;
}
int BFS()
{
    memset(dist,-1,sizeof(dist));
    queue<Node> Q;
    Q.push(Node(r1,c1,0));
    dist[r1][c1][0]=0;
    while(!Q.empty())
    {
        Node node =Q.front();Q.pop();
        int r=node.r,c=node.c,t=node.time;
        for(int d=0;d<4;d++)
        {
            int nr=r+dr[d] , nc=c+dc[d],nt=(t+1)%K;
            if(nr>=0&&nr<R&&nc>=0&&nc<C&&can_move(nr,nc,nt))
            {
                dist[nr][nc][nt]=dist[r][c][t]+1;
                Q.push(Node(nr,nc,nt));
                if(nr==r2&&nc==c2) return dist[nr][nc][nt];
            }
        }
    }
    return -1;
}
int main()
{
    int T; scanf("%d",&T);
    while(scanf("%d%d%d",&R,&C,&K)==3)
    {
        for(int i=0;i<R;i++)
            for(int j=0;j<C;j++)
            {
                scanf(" %c",&map[i][j]);
                if(map[i][j]=='Y')
                {
                    map[i][j]='.';
                    r1=i,c1=j;
                }
                else if(map[i][j]=='G')
                {
                    map[i][j]='.';
                    r2=i,c2=j;
                }
            }
        int ans=BFS();
        if(ans==-1) printf("Please give me another chance!\n");
        else printf("%d\n",ans);
    }
    return 0;
}