Tempter of the bone

奇偶判断

#include <bits/stdc++.h>
using namespace std;
char mat[8][8],visit[8][8];                //地图，标记走过
int n, m, t;
int flag;                                  //flag=1，表示找到了答案
int a, b, c, d;                            //起点S(a,b)，终点D(c,d)
int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};               //上下左右4个方向
#define CHECK(xx,yy) (xx>=0 && xx<n && yy>=0 && yy<m)         //是否在迷宫中
void dfs(int x, int y, int time){
  if(flag) return;                         //逐层退出DFS，有多少层DFS，就退多少次
  if(mat[x][y] == 'D'){
    if(time == t) flag = 1;                                   //找到答案
    return;                                //D只能走一次，所以不管对不对，都返回
  }
  int tmp = t - time - abs(c-x) - abs(d-y);                  //剩下还允许走的步数比最短距离还少
  if(tmp < 0) return;                      //剪枝
  for(int i=0; i<4; i++){                  //上下左右
    int xx = x + dir[i][0], yy = y + dir[i][1];              //下一步的位置
    if(CHECK(xx,yy) && mat[xx][yy]!='X' && !visit[xx][yy]){//不能跳出迷宫，不能撞墙，不能已走过
      visit[xx][yy] = 1;                   //地板标记为走过，不能再走
      dfs(xx, yy, time + 1);               //遍历所有的路径
      visit[xx][yy] = 0;                   //递归返回，这块地板恢复为没走过
    }  
  }
  return;
}
int main(){
  while(~scanf("%d%d%d",&n,&m,&t)){        //EOF（通常EOF=-1），取反为0，循环结束
    if(n==0 && m==0 && t==0) break;        //输入结束    
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++){
        cin>>mat[i][j];
        if(mat[i][j] == 'S') a=i,b=j;      //标记起点
        if(mat[i][j] == 'D') c=i,d=j;      //标记终点
      }
    memset(visit, 0, sizeof(visit)); 
    int tmp = t - abs(c-a) - abs(d-b);     //在DFS之前，做奇偶判断，曼哈顿距离
    if(tmp & 1){ puts("NO"); continue; }   //无解，不用DFS了
    flag = 0;
    visit[a][b] = 1;                       //标记起点已经走过
    dfs(a, b, 0);                          //搜索路径
    if(flag) puts("YES");
    else puts("NO");
  }
  return 0;
}

笔记：暴力搜索的复杂度很高，最多36个格子，假设每个点有3个出口，就有3³⁶条路径，用奇偶判断可以提前筛选不可能的情况，可以减少大大的减少不必要的计算。如果剩下还允许走的步数比最短距离还少，那就剪枝寻找更好的路径