HOJ 1010 Tempter of the Bone（深搜，奇偶剪枝）

深搜，奇偶剪枝
题目意思：有个 n * m 的矩阵，有起点S, 终点 D 。要求恰好在 t 步内，从 S 走到 D。
而且不重复经过两点。 矩阵中 ‘X’ 表示墙，不能走。

本题要点：
1、这题被 TLE 卡吐了。后来看到老哥的博客 点这里
有个奇偶剪枝。
2、其他的就是套用深搜的常用套路， 搞个 vis 数组。上下左右 4个方向。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
const int MaxN = 10;
char mp[MaxN][MaxN];
bool vis[MaxN][MaxN];
int n, m, t, ds;
int sx, sy, door_x, door_y;
int dx[4] = {
    0, -1, 0, 1};
int dy[4] = {
    1, 0, -1, 0};
bool ans;bool valid(int x, int y)
{
    return x >= 0 && x < n && y >= 0 && y < m;
}void dfs(int x, int y, int time)
{
    if(ans)return;if(t == time && x == door_x && y == door_y){
    ans = true;return;}vis[x][y] = 1;for(int i = 0; i < 4; ++i){
    int a = x + dx[i], b = y + dy[i];if(valid(a, b) && mp[a][b] != 'X' && !vis[a][b]){
    dfs(a, b, time + 1);		}}vis[x][y] = 0;
}int main()
{
    while(scanf("%d%d%d", &n, &m, &t)){
    if(0 == n && 0 == m && 0 == t)break;for(int i = 0; i < n; ++i){
    scanf("%s", mp[i]);for(int j = 0; j < m; ++j){
    if(mp[i][j] == 'S'){
    sx = i, sy = j;}if(mp[i][j] == 'D'){
    door_x = i, door_y = j;}}}	// dist 是S 和 D 的曼哈顿距离。 t 只有和 dist 相差是偶数，才可能恰好t步走到。int dist = abs(sx - door_x) + abs(sy - door_y);	// 奇偶剪枝if(t < dist || (t - dist) % 2 == 1){
    printf("NO\n");	continue;}ans = false;memset(vis, 0, sizeof vis);dfs(sx, sy, 0);if(ans)printf("YES\n");elseprintf("NO\n");}return 0;
}/* 4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0 *//* NO YES */