首页 > 代码库 > 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 }
View Code

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 }
View Code

 

DFS