逃离迷宫(dfs).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
using namespace std;

int t,n,m,k;
int x1,x2,y1,y2;
char map[110][110];
short turn[110][110];

bool dfs(short x,short y,short t,short d)
{
    int tx,ty,tt,td,i,j;
    bool flag;
    
    if(x<0 || x>=n || y<0 || y>=m)
        return false;
    if(t > turn[x][y] || t > k)    return false;
    else    turn[x][y] = t;
    
    if(t == k)
        if(x!=x2-1 && y!=y2-1)
            return false;

    if(x==x2-1 && y==y2-1)    return true;
    
    for(i=0;i<4;i++)
    {
        if(i==2)    continue;
        td = (d+i) % 4;
        tt = t + i%2;
        switch(td)
        {
        case 0:
            tx = x-1;
            ty = y;
            break;
        case 1:
            tx = x;
            ty = y+1;
            break;
        case 2:
            tx = x+1;
            ty = y;
            break;
        case 3:
            tx = x;
            ty = y-1;
            break;
        }
        
        if(map[tx][ty] == '.')
        {
            map[tx][ty] = '*';
            if( dfs(tx,ty,tt,td) )
            {
                map[tx][ty]  = '.';
                return true;
            }
            map[tx][ty]  = '.';
        }
    }
    return false;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        getchar();
        for(int i=0;i<n;i++)
            gets(map[i]);
        scanf("%d %d %d %d %d",&k,&y1,&x1,&y2,&x2);
        memset(turn,127,sizeof(turn));
        for(i=0;i<4;i++)
        {
            map[x1-1][y1-1] = '*';
            if( dfs(x1-1,y1-1,0,i) )
                break;
        }
        if(i==4)    printf("no\n");
        else    printf("yes\n");
    }
}