首页 > 代码库 > HDU1010DFS
HDU1010DFS
#include<iostream> #include<math.h> using namespace std; char s[10][10]; int ax,ay,bx,by,n,m,k; int t[4][2]={1,0,-1,0,0,1,0,-1},vist[10][10],flag; void dfs(int x,int y,int count) { int i,mx,my; if(x==bx&&y==by) { if(k==count) flag=1; return; } if(count>=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,count+1); vist[mx][my]=0; if(flag) //注意,在找到了目标之后,就不需要再找!以往编写dfs时,没有注意这点 return; } } } } int main() { while(~scanf("%d%d%d",&n,&m,&k)&&(n+m+k)) { int i,count; 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) //剪枝 { printf("NO\n"); continue; } vist[ax][ay]=1; flag=0; count=0; dfs(ax,ay,count); if(flag==1) printf("YES\n"); else printf("NO\n"); } return 0; }
HDU1010DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。