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

#include<stdio.h>
#include<string.h>
#include<queue>
#define N 110

int m, n, k, x1, x2, y1, y2;
char map[N][N];
int v[N][N][N];//当时间是k的倍数时，障碍消失，之后又重现，所以在平时使用的二维标记数组中再加一维
int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

using namespace std;

struct node
{
    int x, y , stemp;
};

int BFS()
{
    node now, next;
    int i;
    memset(v, 0, sizeof(v));
    queue<node>Q;
    now.x = x1;
    now.y = y1;
    now.stemp = 0;
    v[x1][y1][0] = 1;
    Q.push(now);
    while(!Q.empty())
    {
        now = Q.front();
        Q.pop();
        if(now.x == x2 && now.y ==y2)
            return now.stemp;
        for(i = 0 ; i < 4 ; i++)
        {
            next.x = now.x + d[i][0];
            next.y = now.y + d[i][1];
            next.stemp = now.stemp + 1;
            if(next.x >= 0 && next.x < m && next.y >= 0 && next.y < n && (map[next.x][next.y] != ‘#‘ || next.stemp % k ==  0) && v[next.x][next.y][next.stemp] == 0)
            {
                v[next.x][next.y][next.stemp] = 1;
                Q.push(next);
            }
        }
    }
    return -1;
}
int main()
{
    int t, i, j, ans;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &m, &n, &k);
        for(i = 0 ; i < m ; i++)
            scanf("%s", map[i]);
        for(i = 0 ; i < m ; i++)
        {
            for(j = 0 ; j < n ; j++)
            {
                if(map[i][j] == ‘Y‘)
                    x1 = i, y1 = j;
                else if(map[i][j] == ‘G‘)
                    x2 = i, y2 = j;
            }
        }
        ans = BFS();
        if(ans == -1)
            printf("Please give me another chance!\n");
        else
            printf("%d\n", ans);
    }
    return 0;
}