[BFS|DFS]HDU 1010 Tempter of the Bone


这个题最有意思的就是那个奇偶性剪枝了,就是 从一个点到终点的最短路径该点到终点的其他路径 奇偶性相同

怎么证明呢,想想差不多就是那样,你横着朝左多走了,肯定还得有朝右的补回来,不然到不了终点啊,所以中间多出来的总是偶数。

没有这个剪枝,程序要超时的。

#include 
#include 
const int N = 10;
char maze[N][N];
int flag;
int d[4][2] = {1,0,0,1,-1,0,0,-1};
int h,w,sx,sy,dx,dy,time;
void DFS(int t, int x, int y)
{
   if(flag) return;
   int k = time-t-abs(x-dx)-abs(y-dy);
   if(k<0 || k&1)return;
   if(t == time && x == dx && y == dy)
   {
      flag = 1;
      return;
   }
   int x1,y1;
   for(int i = 0; i < 4; i++)
   {
      x1 = x + d[i][0];
      y1 = y + d[i][1];
      if(x1 > 0 && y1 > 0 && x1 <= h && y1 <= w && maze[x1][y1] != 'X')
      {
         maze[x1][y1] = 'X';
         DFS(t+1,x1,y1);
         maze[x1][y1] = '.';
      }
   }
}
int main()
{
   int wall;
   while(scanf("%d%d%d",&h,&w,&time) && (h||w||time))
   {
	  getchar();
      wall = 0;
      for(int i = 1; i <= h; i++)
      {
         for(int j = 1; j <= w; j++)
         {
            scanf("%c",&maze[i][j]);
			if(j==w) getchar();
            if(maze[i][j] == 'S')
            {
               sx = i;
               sy = j;
            }
            else if(maze[i][j] == 'D')
            {
               dx = i;
               dy = j;
            }
            else if(maze[i][j] == 'X')
            {
               wall++;
            }
         }
      }
      flag = 0;
      maze[sx][sy] = 'X';
      DFS(0,sx,sy);
      if(flag) puts("YES");
      else puts("NO");
   }
   return 0;
}

发表评论