传送门:
http://acm.hdu.edu.cn/showproblem.php?pid=1010
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 144191 Accepted Submission(s): 38474
把矩阵看成如下形式:
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
从为 0 的格子走一步,必然走向为 1 的格子 。
从为 1 的格子走一步,必然走向为 0 的格子 。
即:
从 0 走向 1 必然是奇数步,从 0 走向 0 必然是偶数步。
所以当遇到从 0 走向 0 但是要求时间是奇数的或者 从 1 走向 0 但是要求时间是偶数的,都可以直接判断不可达!
#include<bits/stdc++.h> char s[10][10]; int ax,ay,bx,by,n,m,k; int t[4][2]={1,0,-1,0,0,1,0,-1};//方向引导数组 int vist[10][10],flag; void dfs(int x,int y,int c) { int i,mx,my; if(x==bx&&y==by)//找到终点 { if(k==c)//恰好在规定时间找到终点则标志位置1 flag=1; return; } if(c>=k)//超出规定时间,剪掉 return; if(s[x][y]!=‘X‘)//可走点 { for(i=0;i<4;i++) { mx=x+t[i][0]; my=y+t[i][1]; if(s[mx][my]!=‘X‘&&mx>=1&&mx<=n&&my>=1&&my<=m&&!vist[mx][my])//判断能不能往这个方向走 { vist[mx][my]=1; dfs(mx,my,c+1); vist[mx][my]=0;//回退 if(flag) //注意,在找到了目标之后,就不需要再找!以往编写dfs时,没有注意这点 return; } } } } int main() { while(scanf("%d%d%d",&n,&m,&k)>0&&(n+m+k)) { int i,c; for(i=1;i<=n;i++) { getchar(); for(int j=1;j<=m;j++) { scanf("%c",&s[i][j]); if(s[i][j]==‘S‘) { ax=i;//起点 ay=j; } if(s[i][j]==‘D‘) { bx=i;//终点 by=j; } } } getchar(); memset(vist,0,sizeof(vist)); if(abs(ax-bx)+abs(ay-by)>k||(ax+bx+ay+by+k)%2==1) // 最短距离都大于k的剪枝和奇偶剪枝 { printf("NO\n"); continue; } vist[ax][ay]=1; flag=0; c=0; dfs(ax,ay,c); if(flag==1) printf("YES\n"); else printf("NO\n"); } return 0; }
原文:https://www.cnblogs.com/yinbiao/p/9313239.html