1010-Tempter of the Bone

题目链接

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

Sample Input
4 4 5
S.X.
..X.
..XD
….
3 4 5
S.X.
..X.
…D
0 0 0

Sample Output
NO
YES

解题思想

/*
- dfs+奇偶性剪枝 - 奇偶性剪枝：假设起点为s，终点为e，并且起点到 - 终点的最短路径为dis = e-s， - 假设dis为偶数，那么给定一个步数t，t > - dis（t为从起点到终点可能的步数，必须大于等 - t，反证：如果小于t<dis，如果给的t比最短路径 - 还小，肯定走不到），其次t与dis应该同为奇数， - 或同为偶数（重点）考虑对角线上的两点，从 - 走到另一点必须经过偶数步，同行或同列必须经 - 奇数步。 
*/

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 8;
char a[maxn][maxn];
int point[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int N,M,T;
int sx,sy,ex,ey;
int flag = 0;
void dfs(int x, int y, int cnt)
{
    if(x<1 || x>N || y<1 || y>M) //越界
        return;
    if(x==ex && y==ey && cnt == T) //满足条件
    {
        flag = 1;
    }
    if(flag)
        return;
    int shor = abs(ex-x)+abs(ey-y);
    int tem = T-cnt - shor ; //已走cnt步，剩余T-cnt步，shor为俩点最短距离
    if(tem < 0 || tem & 1) //奇偶性剪枝
        return;
    for(int i=0; i<4; ++i)
    {
        int dx = x + point[i][0];
        int dy = y + point[i][1];
        if(a[dx][dy]!='X')
        {
            a[dx][dy] = 'X';
            dfs(dx,dy,cnt+1);
            a[dx][dy] = '.'; //回溯
        }

    }

}
int main()
{
    while(scanf("%d%d%d",&N,&M,&T)!=EOF)
    {
        getchar(); //必须加，应为接收完nmt后，有个\n，需要接收掉，不然后占用数组空间
        if(!N && !M && !T)
            break;
        int wall = 0;
        for(int i=1; i<=N; ++i)
        {

            for(int j=1; j<=M; ++j)
            {
                scanf("%c",&a[i][j]);
                if(a[i][j] == 'S')
                {
                    sx = i;
                    sy = j;
                }
                if(a[i][j] == 'D')
                {
                    ex = i;
                    ey = j;
                }
                if(a[i][j] == 'X')
                {
                    wall++;
                }
            }
            getchar(); //与上面的同理
        }
        if(M*N-wall < T)
        {
            cout << "NO" <<endl;
            continue;
        }
        a[sx][sy] = 'X';
        flag = 0;
        dfs(sx,sy,0);
        if(flag)
        {
            cout << "YES" <<endl;
        }
        else
        {
            cout << "NO" <<endl;
        }
    }
    return 0;
}