TZOJ 3305 Hero In Maze II(深搜)

描述

500年前，Jesse是我国最卓越的剑客。他英俊潇洒，而且机智过人^_^。
突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了，他急忙赶到迷宫，开始到处寻找公主的下落。令人头痛的是，Jesse是个没什么方向感的人，因此，他在行走过程中，不能转太多弯了，否则他会晕倒的。 我们假定Jesse和公主所在的位置都是空地，初始时，Jesse所面向的方向未定，他可以选择4个方向的任何一个出发，而不算成一次转弯。希望你帮他判断一下他是否有机会找到心爱的公主。 

输入

题目包括多组测试数据.

第1行为一个整数T(1 ≤ T≤ 100),表示测试数据的个数，接下来为T组测试数据.

每组测试数据以两个整数N,M,K(1<=N, M≤100, 0<K<=10)开头，分别代表迷宫的高，长和Jesse最多能转的弯数，(紧接着有N行，M列字符，由"."，"*"，"P"，"S"组成。其中
"." 代表能够行走的空地。
"*" 代表墙壁，Jesse不能从此通过。
"P" 是公主所在的位置。
"S" 是Jesse的起始位置。
每个时间段里Jesse只能选择“上、下、左、右”任意一方向走一步。

输出

如果Jesse能在晕之前找到公主，输出“YES”，否则输出“NO”。

样例输入

2
5 5 1
P..**
*.**.
S....
.....
*....
5 5 2
P..**
*.**.
S....
.....
*....

样例输出

NO
YES

题意

国王S能否在规定转K个弯的时间内找到公主P

题解

这个题有个小问题

深搜是最快搜到终点，但是这题要求的是转弯次数最小

有一种情况，搜到终点但是转弯次数很多不符合要求，还有一条路符合转弯的要求但是很远，根据深搜，这是有问题的，因为可以多次到达终点

可以这样考虑，深搜的时候，把搜过的点先标记为墙，搜完回退的时候，把搜过的点再标记为路，这样就解决多条路到终点的问题了

还有个问题就是深搜的起点，既要让方向满足，也要让转弯满足

初始的方向设置为-1，初始的转弯次数也设置为-1

这样的话，一开始搜4个方向的时候，方向改变的同时，转弯次数+1变成0，满足

代码

#include<cstdio>
const int N=1e2+5;
struct p{int x,y;}s,e;
int flag,n,m,K;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
char G[N][N];
void dfs(int x,int y,int dir,int k)
{
    if(flag==0&&k<=K)
    {
        G[x][y]='*';
        if(x==e.x&&y==e.y)flag=1;
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&G[xx][yy]!='*')
            {
                if(dir==i)dfs(xx,yy,i,k);
                else dfs(xx,yy,i,k+1);
            }
        }
        G[x][y]='.';
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&K);
        for(int i=0;i<n;i++)
        {
            scanf("%s",G[i]);
            for(int j=0;j<m;j++)
            {
                if(G[i][j]=='S')
                    s.x=i,s.y=j;
                if(G[i][j]=='P')
                    e.x=i,e.y=j;
            }
        }
        flag=0;
        dfs(s.x,s.y,-1,-1);
        printf("%s
",flag?"YES":"NO");
    }
    return 0;
}