HDU 1010 Tempter of the Bone-白红宇

HDU 1010 Tempter of the Bone

阅读量：6368 次

发布时间：2019-06-23

本文共 1468 字，大约阅读时间需要 4 分钟。

dfs+剪枝

题意是说一仅仅狗要逃出迷宫，可是必须在某个时间点刚好到出口。

開始裸了一个dfs，TLE。。

。剪枝没有啥思路。本来想用bfs先判是否能到达，感觉不靠谱。

然后看Discuss，了解了一个奇偶性剪枝。

0 1 0 1 0 1 0 1 0   1 0 1 0 1 0 1 0 1   0 1 0 1 0 1 0 1 0   1 0 1 0 1 0 1 0 1   0 1 0 1 0 1 0 1 0   1 0 1 0 1 0 1 0 1

0->1 和 1->0 都是奇数

0->0 和 1->1 都是偶数。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define INF 0x7fffffff#define eps 1e-8#define LL long long#define PI 3.141592654#define CLR(a,b) memset(a,b,sizeof(a))#define FOR(i,a,n) for(int i= a;i< n ;i++)#define debug puts("==fuck==")#define acfun std::ios::sync_with_stdio(false)#define SIZE 1000+10using namespace std;int xx[]={0,0,-1,1};int yy[]={-1,1,0,0};int n,m,T;char g[10][10];int endx,endy;bool vis[10][10];bool flag;void dfs(int x,int y,int t){ if(flag)return; int tmp=(T-t)-abs(endx-x)-abs(endy-y); if(tmp<0||tmp&1)return; if(g[x][y]=='D'&&t==T) flag=1; else { FOR(k,0,4) { int i=x+xx[k]; int j=y+yy[k]; if(i<0||j<0||i>=n||j>=m||g[i][j]=='X'||vis[i][j]) continue; vis[i][j]=1; dfs(i,j,t+1); vis[i][j]=0; } }}int main(){ //freopen("test","w",stdout); while(~scanf("%d%d%d",&n,&m,&T)) { if(!n&&!m&&!T)return 0; char str[11]; int x=0,y=0; FOR(i,0,n) { scanf("%s",str); FOR(j,0,m) { g[i][j]=str[j]; if(g[i][j]=='S') x=i,y=j; else if(g[i][j]=='D') endx=i,endy=j; } } CLR(vis,0); flag=0; vis[x][y]=1; dfs(x,y,0); if(flag)puts("YES"); else puts("NO"); }}