hdu 2102 A计划 （dfs）

注意传送的时候一定要传送过去。如果另外一边还是传送门的话   也是死路。

注意判断终点的时候  还要层数一样

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

char map[2][12][12];
bool vis[2][12][12];
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int lim;
int n,m;
int stx,sty,stc,tgx,tgy,tgc;

bool ok(int x,int y)
{
    if(x<n && x>=0 && y<m && y>=0)return true;
    return false;
}
bool dfs(int posx,int posy,int posc,int dep)
{
    if(posx==tgx && posy==tgy && posc==tgc && dep<=lim)return true;
    else if(dep>lim)return false;

    for(int d=0;d<4;d++)
    {
        int x=posx+dx[d];
        int y=posy+dy[d];

        if(ok(x,y) && map[posc][x][y]==‘#‘ && map[1-posc][x][y]!=‘*‘ && !vis[1-posc][x][y] && map[1-posc][x][y]!=‘#‘)
        {
            vis[1-posc][x][y]=true;

            if(dfs(x,y,1-posc,dep+1))return true;

            vis[1-posc][x][y]=false;
        }
        else if(ok(x,y) && map[posc][x][y]!=‘#‘ && map[posc][x][y]!=‘*‘ && !vis[posc][x][y])
        {
            vis[posc][x][y]=true;

            if(dfs(x,y,posc,dep+1))return true;

            vis[posc][x][y]=false;
        }
    }

    return false;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&lim);

        for(int i=0;i<n;i++)
        {
            scanf("%s",map[0][i]);
            for(int j=0;j<m;j++)
            {
                if(map[0][i][j]==‘S‘)
                {
                    stx=i,sty=j,stc=0;
                }
                else if(map[0][i][j]==‘P‘)
                {
                    tgx=i,tgy=j,tgc=0;
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            scanf("%s",map[1][i]);
            for(int j=0;j<m;j++)
            {
                if(map[1][i][j]==‘S‘)
                {
                    stx=i,sty=j,stc=0;
                }
                else if(map[1][i][j]==‘P‘)
                {
                    tgx=i,tgy=j,tgc=1;
                }
            }
        }


        memset(vis,0,sizeof vis);

        vis[stc][stx][sty]=true;
        if(dfs(stx,sty,stc,0))
        printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

/*
1
5 5 14
S*#*.
.#...
.....
****.
...P.

..*..
#.*..
***..
...*.
*.#..
*/

hdu 2102 A计划 （dfs）,布布扣,bubuko.com

hdu 2102 A计划 （dfs）

原文：http://blog.csdn.net/u010709592/article/details/21744821