题目链接

Tempter of the Bone

4 4 5S.X...X...XD....3 4 5S.X...X....D0 0 0 Sample Output
YES AuthorZHANG, Zheng 题意： 给你m * n 的迷宫， 有一只小狗重起点S开始出发要正好T步走到迷宫的终点D， 能就输出YES， 不能就输出NO。解题思路：DFS  + 奇偶剪枝。 直接DFS会超时。将该迷宫看成0，1 交替的如下形式：0 1 0 1 0 1 01 0 1 0 1 0 10 1 0 1 0 1 01 0 1 0 1 0 1然后就会发现从0走到0或从1走到1的不论怎么走都是偶数步数，从0走到1或从1走到0都是奇数步数，假设我们所在的点是sx, sy。 终点是ex， ey。如果起点是0走到0或1走到1的情况那么T(这里的T是指当前还剩余的步数)必须是偶数，反之必须是奇数。我们能够求出t1 = abs(sx - ex) + abs(sy - ey)是从起点到终点所需要的最少步数。那么T和t1的奇偶性必须相同，如果不相同， 则直接舍去（这里就是剪枝， dfs过程中不用再深搜下去）。 因为奇数减去奇数是偶数， 偶数减去偶数是偶数所以(T-t1)%2 判断奇偶性即可（ 但要注意如果T-t1<0的话步数不够也应直接舍去）在DFS搜索过程中碰到以上情况的直接return，不用继续深搜下去以节省时间。代码：
#include <cmath>#include <string>#include <cstdio>#include <sstream>#include <cstring>#include <iostream>#include <algorithm>#define LOCALusing namespace std;int f[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};  //方向char s[10][10]; int m, n, t;int si, sj, ei, ej;int flag = 0;void dfs(int x, int y, int z){    if(flag == 1) return;       if(t == z && x == ei && y == ej)   //到达终点    {        flag = 1;        return;    }    if(x <= 0 || x > m || y <= 0 || y > n)  //判断边界        return;    int t1 = t - z - abs(x - ei) - abs(y - ej);    if(t1 < 0 || t1&1)                       //这里就是奇偶剪枝        return;    for (int i = 0; i < 4; i++)    {        int nx = x + f[i][0];        int ny = y + f[i][1];        if(s[nx][ny] != 'X')        {            s[nx][ny] = 'X';                    //标记走过            dfs(nx, ny, z+1);            s[nx][ny] = '.';                    //还原地图        }    }    return;}int main(){//    #ifdef LOCAL//    freopen("data.in", "r", stdin);//    freopen("data.out", "w", stdout);//    #endif    while (scanf("%d%d%d",&m, &n, &t) != EOF)    {        getchar();        if(m == 0 && n == 0 && t == 0) break;        memset(s, 0, sizeof(s));        int wall = 0;        for (int i = 1; i <= m; i++)        {            for (int j = 1; j <= n; j++)            {                scanf("%c", &s[i][j]);                if(s[i][j] == 'S')                {                    si = i; sj = j;                }                else if(s[i][j] == 'D')                {                    ei = i; ej = j;                }            }            getchar();        }        flag = 0;        s[si][sj] = 'X';         //出发点要记得标记走过， 之前因为没有标记导致WA。        dfs(si, sj, 0);        if(flag == 1)            printf("YES/n");        else            printf("NO/n");    }    return 0;}