学步园

题意：给一个字符矩阵，S是起点，D是终点，X不能走，其它地方可以走，求T步数的时候是否能从S恰好走到T。。。

思路：开始题意理解错了，以为就是个BFS()，WA掉。。。后来看了discuss是dfs()。。TLE掉，后来上网搜，原来得加个“奇偶剪枝”的东西、、、

奇偶剪枝：http://www.cnblogs.com/newpanderking/archive/2012/10/09/2716984.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char map[10][10];
int vis[10][10] , sx , sy , ex , ey , n , m , T;
bool dfs(int x , int y , int step) {
    int i , j , k;
    //printf("%d %d %d\n",x,y,step);
    int tmp;      //偏移路径 
    tmp = T - step - abs(x-ex) - abs(y-ey);
    if(tmp < 0 || tmp%2!=0) return false;   /*走最近的情况还无法到达剪枝1，奇偶剪枝2*/
    if(step == T && x == ex && y == ey) return true;
    for(k = 0 ; k < 4 ; k ++) {
        i = x + dir[k][0];
        j = y + dir[k][1];
        if(!vis[i][j] && i>=0 && i<n && j>=0 && j<m) {
            vis[i][j] = 1;
            if(dfs(i , j , step+1)) return true;  
            vis[i][j] = 0;  
        }    
    }
    return false;
}
int main() {
    int i , j;
    while(~scanf("%d%d%d",&n,&m,&T)) {
        if(!n&&!m&&!T) break;
        for(i = 0 ; i < n ; i ++)
        scanf("%s",map[i]);
        memset(vis , 0 , sizeof(vis));
        int cnt = 0;
        for(i = 0 ; i < n ; i ++) {
            for(j = 0 ; j < m ; j ++) {
                if(map[i][j]=='S') {
                    sx = i , sy = j;
                    vis[i][j] = 1;    
                } else if(map[i][j]=='D') {
                    ex = i , ey = j;    
                } else if(map[i][j]=='X') {
                    vis[i][j] = 1;
                    cnt++;
                }    
            } 
        }
        if(n*m - cnt<T) {
            printf("NO\n");        /*剪枝3*/
            continue;    
        }
        if(dfs(sx , sy , 0)) printf("YES\n");
        else printf("NO\n");
    }    
}