Tempter of the Bone(被粗心坑苦了）

清疚 2022-08-27 15:50 78阅读 0赞

题目大意：

某个不行的孩纸，触动了一个N\*M的长方形密室的机关，他需要从密室逃出去，但他站在某块地板上后，下一秒地板将会下陷（他也会挂掉），而密室的门只有在据他开始移动T秒后才会开启，并且开启时间不超过一秒，他1秒内只能移动到相邻的下一个地板（前后左右四个方向），问他能否逃出密室？？？

题目分析：

虽然N、M最大为6，但是深度优先全部遍历的话，时间肯定会超时，因为深搜级别是指数增长；因次剪枝就成为了非常必要的事情，此题中用到了奇偶剪枝；具体来说就是到一个地方的时间的奇偶性和到这个地方的最短距离的奇偶性相同......

\*\*：我被一个打错的变量坑了半天，下一次再有错误直接重写一遍的了（不过找不出原来的错误还是会让人不爽╮(╯\_╰)╭）

#include <iostream>
    #include <cstdio>
    #include <math.h>
    #include <stdlib.h>
    using namespace std;
    #define N 10
    char map[N][N];
    int T,n,m,t,dir[4][2]={1,0,0,1,-1,0,0,-1},flag;
    struct coor
    {
    	int x,y,step;
    }S,D;
    void dfs(int px,int py,int step)
    {
     	int i;
     	for(i=0;i<4;i++)
     	{
    	 	int tx,ty,tstep;
    	 	tx=px+dir[i][0];
    	 	ty=py+dir[i][1];
    	 	tstep=step+1;
    	 	if(tstep==T&&tx==D.x&&ty==D.y){flag=1;return;}//出口
    	 	if(flag)return ;//找到目标后就不必继续再找了。。。。
     	 	if((abs(D.x-tx)+abs(D.y-ty))%2!=(T-tstep)%2)return;
    	 	if(tstep<T&&tx>=0&&tx<n&&ty>=0&&ty<m&&map[tx][ty]=='.')
    	 	{
    		 	 map[tx][ty]='X';
    			 dfs(tx,ty,tstep);
    			 map[tx][ty]='.';
            }
    	 }
    }
    int main(int argc, char *argv[])
    {
    	while(scanf("%d%d%d",&n,&m,&T)==3&&n&&m)
    	{
    		S.x=-1;S.y=-1;D.x=-1;D.y=-1;
    		int count=0;
    		for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++)
    		{
    			scanf(" %c",&map[i][j]);
    			if(map[i][j]=='S'){S.x=i;S.y=j;S.step=0;}
    			if(map[i][j]=='D'){D.x=i;D.y=j;}
    			if(map[i][j]!='X')count++;
    		}
    		flag=0;--count;//可走的点的上限
    		if(T<=count)dfs(S.x,S.y,0);
    		if(flag)printf("YES\n");
      		else printf("NO\n");
    	}
    	return 0;
    }