hdu1010 迷宫 Tempter of the Bone DFS+优先队列

xiaoxiao2021-02-28  12

/* 其中t-cnt为剩余的步数, s1+s2为剩余步数 如果走偶数步要求的时间是奇数,或者走奇数步要求的时间是偶数,都明显不可行 又因为奇数-偶数 = 奇数,偶数 - 奇数 = 偶数,而奇数-奇数= 偶数,偶数-偶数=偶数 所以tem必须为偶数  */ #include<stdio.h> int n,m,t; char map[10][10]; int flag; int di,dj,wall; int to[4][2]={{0,-1},{0,1},{-1,0},{1,0}};//4个方向  void dfs(int si,int sj,int cnt)//深度搜索 cnt代表已经走过的步数  {  int i,tem; if(si>n||sj>m||si<=0||sj<=0)//参数非法,退出  return; if(cnt==t&&si==di&&sj==dj)//表示已经到达终点,flag置1并退出  flag=1, return; int s1=si-di; int s2=sj-dj; if(s1<0) s1=-s1; if(s2<0) s2=-s2; tem=t-cnt-s1-s2;  if(tem<0||tem%2)//看剩下的时间能否到达终点,tem%2是判断是否偶数。 //根据奇偶性剪枝可得tem只有为偶数才可能到达,奇数不行。  return; for(i=0;i<4;i++) { if(map[si+to[i][0]][sj+to[i][1]]!='X') { map[si+to[i][0]][sj+to[i][1]]='X';//走过的地方变为墙  dfs(si+to[i][0],sj+to[i][1],cnt+1); map[si+to[i][0]][sj+to[i][1]]='.';//遍历返回,将刚刚没有用到的路从墙还原为路 } } return; } int main() { int i,j,si,sj; while(scanf("%d%d%d",&n,&m,&t)) { if(n==0&&m==0&&t==0) break; getchar(); wall=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%c",&map[i][j]); if(map[i][j]=='S') { si=i; sj=j; } else if(map[i][j]=='D') { di=i; dj=j; } else if(map[i][j]=='X') wall++; } getchar(); } if(n*m-wall<=t)//剪枝处理,t是能走的步数。步数加墙数必须小于总格子数,因为里面总格子数还包括起点S和终点D { printf("NO\n"); continue; } flag=0; map[si][sj]='X';//出发点是不可能再走的了,变为墙  dfs(si,sj,0); if(flag) printf("YES\n"); else  printf("NO\n"); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-2449981.html

最新回复(0)