首页 > 代码库 > DFS
DFS
poj1979:http://poj.org/problem?id=1979
1 #include<cstdio> 2 #include<cstring> 3 int dir[4][2]={0,1,0,-1,1,0,-1,0}; 4 int n,m; 5 char p[25][25]; 6 int cnt=0; 7 void dfs(int x,int y) 8 { 9 if(x<0||x>=n||y<0||y>=m||p[x][y]==‘#‘) return ; 10 p[x][y]=‘#‘; 11 cnt++; 12 for(int i=0;i<4;i++) 13 dfs(x+dir[i][0],y+dir[i][1]); 14 return; 15 } 16 int main() 17 { 18 while(scanf("%d%d",&m,&n)&&(n||m)) 19 { 20 cnt=0; 21 int sx,sy; 22 for(int i=0;i<n;i++) 23 { 24 scanf("%s",p[i]); 25 for(int j=0;j<m;j++) 26 { 27 if(p[i][j]==‘@‘) sx=i,sy=j; 28 } 29 } 30 dfs(sx,sy); 31 printf("%d\n",cnt); 32 } 33 }
poj1970:http://poj.org/problem?id=1970
1 #include<cstdio> 2 #include<cstring> 3 int dir[4][2]={0,1,1,0,1,1,-1,1}; 4 int p[22][22]; 5 int k; 6 int dfs(int x,int y) 7 { 8 for(int i=0;i<4;i++) //四种方式 9 { 10 11 int ok=1; 12 int dx=x,dy=y; // 13 for(int j=0;j<4;j++) //接着走四步 14 { 15 dx=dx+dir[i][0]; 16 dy=dy+dir[i][1]; 17 if(dx<1||dx>19||dy<1||dy>19||p[dx][dy]!=k) 18 { 19 ok=0; 20 break; 21 } 22 } 23 if(ok&&p[x-dir[i][0]][y-dir[i][1]]!=k&&p[dx+dir[i][0]][dy+dir[i][1]]!=k) 24 { 25 printf("%d\n%d %d\n",k,x,y); 26 return 1; 27 } 28 } 29 return 0; 30 } 31 int main() 32 { 33 int t; 34 scanf("%d",&t); 35 while(t--) 36 { 37 for(int i=1;i<=19;i++) 38 for(int j=1;j<=19;j++) 39 scanf("%d",&p[i][j]); 40 int flag=0; 41 for(int i=1;i<=19&&flag!=1;i++) 42 for(int j=1;j<=19&&flag!=1;j++) 43 if(p[i][j]!=0) 44 { 45 k=p[i][j]; 46 if(dfs(i,j)) flag=1; 47 } 48 if(!flag) puts("0"); 49 } 50 return 0; 51 }
DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。