HDU 1010 Tempter of the Bone

DFS加奇偶剪枝

题目链接HDU 1010

题目大意

从S出发，到D，每走一步需要一秒，走过的路会塌陷，问你能否刚好在t秒内到达。

题目解析

首先思路是DFS，记录横坐标，纵坐标，和已经走的步数。用DFS搜索，看能否出现满足题意的情况，注意DFS之后要把vis数组重置，因为dfs只是模拟，dfs到某一点不满足的话这一个点以后搜索的时候还是可以走的。
但是会T，Baidu发现需要进行奇偶剪枝。对每一点搜索时，先判断这一点到目的地的横纵坐标差的和，是否和要用的步数的奇偶性相同，不同的话怎么绕都是无法满足的，可直接return。

AC代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int n,m,t,p,q;
char a[8][8];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int vis[8][8];
bool cango(int x,int y) //该点是否可行
{
        if(x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]&&a[x][y]!='X')
        {
                return true;
        }
        return false;
}
int dfs(int x,int y,int num) //横、纵坐标  已用步数
{
        if((abs(p-x)+abs(q-y))%2!=(t-num+1)%2)
        {
                return 0;
        }
        for(int i=0;i<4;i++)
        {
                int xx=x+dx[i];
                int yy=y+dy[i];
                if(cango(xx,yy))
                {
                        if(a[xx][yy]=='D'&&num==t)
                        {
                                return 1;
                        }
                        if(a[xx][yy]=='.')
                        {
                                vis[xx][yy]=1;
                                if(dfs(xx,yy,num+1)==1)
                                {
                                        return 1;
                                }
                                vis[xx][yy]=0; //注意重置为0
                        }
                }
        }
        return 0;
}
int main()
{
        while(cin>>n>>m>>t,n||m||t)
        {
                for(int i=0;i<n;i++)
                {
                        for(int j=0;j<m;j++)
                        {
                                cin>>a[i][j];
                        }
                }
                memset(vis,0,sizeof(vis));
                for(int i=0;i<n;i++)
                {
                        for(int j=0;j<m;j++)
                        {
                                if(a[i][j]=='D')
                                {
                                        p=i;
                                        q=j;
                                }
                        }
                }
                for(int i=0;i<n;i++)
                {
                        for(int j=0;j<m;j++)
                        {
                                if(a[i][j]=='S')
                                {
                                        vis[i][j]=1;
                                        if(dfs(i,j,1)==1)
                                        {
                                                cout<<"YES"<<endl;
                                        }
                                        else
                                        {
                                                cout<<"NO"<<endl;
                                        }
                                }
                        }
                }
        }
        return 0;
}