HDU 1010 Tempter of the Bone（奇偶判断）

题目链接：点击这里

image.png

image.png

题意：给定 的矩阵，'.' 表示可以走，'X' 表示不可走，从 出发，问能否在 时刻恰好到达 。

两个可行性剪枝：

1. 当前走了 步，如果 ，即已经走的超过了限制步数，还没有找到 点，则剪掉。

2. 设从起点 走了 步到了当前位置 ，而 到 点 的最短距离为 ，如果有 ，也就是 ，这说明剩下还允许走的步数比最短距离还少，肯定走不到了，剪掉。其中

用下面的图来解释方格图的奇偶性：

image.png

对每个方格用 进行交错标记。从 格子走一步，只能到 格子，从 格子走一步只能到 格子。图中任取 个点为起点 和终点 ，如果它们都是 或 都是 ，那么偶数步才能走到；如果一个是 一个是 ，那么奇数步才能走到。这就是奇偶判断的原理。

所以，给定起点 、终点 、限制的步数 ，可以立刻判断是否有解：

1. 和 同 或同 ， 是偶数，可能有解； 是奇数，必定无解。
2. 和 不同， 是奇数，可能有解； 是偶数，必定无解。

但是，方格的 标记如何得到呢，或者换个说法，给定 和 ，如何判断它们的 是否相同呢。很简单，用曼哈顿距离，如果 和 的曼哈顿距离 是奇数，说明 和 一个是 一个是 ；如果 是偶数，说明 和 同 或同 。

从以上分析可以知道，奇偶判断只能用在方格图上，方格里允许有不可走的障碍，这些障碍不影响逻辑正确性。

因此，在本题中，如果 是奇数则肯定无解。只需要对起点 、终点 做一次奇偶判断就够了，DFS内部不用再做。因为，从 走到方格中的任何一点 ， 与 的奇偶性，与 和 的奇偶性相同。

#include<bits/stdc++.h>
using namespace std;

char mat[8][8];
bool visit[8][8];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int n, m, T;

bool flag;          // flag为true表示找到了答案
int a, b, c, d;     // 起点S(a,b)，终点D(c,d)

void dfs(int x, int y, int t)
{
    if(flag)    return;
    
    if(mat[x][y] == 'D')
    {
        if(t == T)  flag = true;    // 找到答案
        return;                     // D只能走一次，所以不管对不对，都返回
    }
    
    if(t > T)   return;         // 剪枝1，因为有剪枝2，1就多余了
    
    int tmp = T - t - abs(c - x) - abs(d - y);
    
    if(tmp < 0) return;             // 剪枝2
    
    for(int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if(xx < 0 || xx >= n || yy < 0 || yy >= m)  continue;
        if(mat[xx][yy] == 'X')  continue;
        if(visit[xx][yy])   continue;
        visit[xx][yy] = true;       // 标记为走过，不能再走        
        dfs(xx, yy, t + 1);
        visit[xx][yy] = false;      // 递归返回，这块地板恢复为没走过  
    }
    
    return;
}

int main()
{
    while(~scanf("%d%d%d", &n, &m, &T), n + m + T)
    {
        for(int i = 0; i < n; i++)  scanf("%s", mat[i]);
        
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(mat[i][j] == 'S')    a = i, b = j;
                if(mat[i][j] == 'D')    c = i, d = j;
            }
        }
        
        int tmp = T - abs(c - a) - abs(d - b);  // 在DFS之前做奇偶判断
        
        if(tmp & 1)                             // 无解，不用DFS了
        {
            puts("NO");
            continue;
        }
        
        memset(visit, false, sizeof(visit));
        flag = 0;
        
        visit[a][b] = true;                 // 标记起点已经走过
        dfs(a, b, 0);                       // 搜索路径
        
        if(flag)    puts("YES");
        else    puts("NO");
    }
    
    return 0;
}