首页 > 代码库 > HDU 1241 Oil Deposits(dfs)
HDU 1241 Oil Deposits(dfs)
#include<cstdio>#include<cmath>#include<cstring>#include<iostream>#include<algorithm>using namespace std;char mat[10][10];int vis[10][10];int ok,dx,dy;int m,n,d;int op[4][2]={0,1,1,0,0,-1,-1,0};bool jiezhi(int x,int y,int rt){ int now=abs(dx-x)+abs(dy-y); if(d-rt<now) return false; if((d-rt-now)%2!=0) return true; return true;}bool okn(int x,int y,int rt){ if(x<0||x>=n||y<0||y>=m||rt>d||vis[x][y]==1||mat[x][y]==‘X‘) return false; if(rt<d&&mat[x][y]==‘D‘) return false; if(rt==d) { if(mat[x][y]==‘D‘) ok=1; return false; } return true;}void dfs(int x,int y,int rt){ if(jiezhi(x,y,rt)!=1||ok) return; int nx,ny; for(int i=0;i<4;i++) { nx=x+op[i][0]; ny=y+op[i][1]; if(okn(nx,ny,rt+1)) { vis[nx][ny]=1; dfs(nx,ny,rt+1); vis[nx][ny]=0; } }}int main(){ int i,j,k; int sx,sy; while(scanf("%d%d%d",&n,&m,&d)!=EOF) { if(n==0||m==0||d==0) break; ok=0; for(i=0; i<n; i++) { scanf("%s",mat[i]); } memset(vis,0,sizeof(vis)); for(i=0; i<n; i++) for(j=0; j<m; j++) { if(mat[i][j]==‘S‘) { sx=i; sy=j; } else if(mat[i][j]==‘D‘) { dx=i;dy=j; } } if(jiezhi(sx,sy,0)) { vis[sx][sy]=1; dfs(sx,sy,0); } if(ok) printf("YES\n"); else printf("NO\n"); } return 0;}
HDU 1241 Oil Deposits(dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。