HDOJ 1312 DFS&BFS

雨点打透心脏的1/2处 2022-03-31 03:57 168阅读 0赞

# Red and Black #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7337 Accepted Submission(s): 4591**

Problem Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.  
Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.  
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.  
'.' - a black tile '\#' - a red tile '@' - a man on a black tile(appears exactly once in a data set)

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

6 9 ....\#. .....\# ...... ...... ...... ...... ...... \#@...\# .\#..\#.

11 9 .\#......... .\#.\#\#\#\#\#\#\#. .\#.\#.....\#. .\#.\#.\#\#\#.\#. .\#.\#..@\#.\#. .\#.\#\#\#\#\#.\#. .\#.......\#. .\#\#\#\#\#\#\#\#\#. ...........

11 6 ..\#..\#..\#.. ..\#..\#..\#.. ..\#..\#..\#\#\# ..\#..\#..\#@. ..\#..\#..\#.. ..\#..\#..\#..

7 7 ..\#.\#.. ..\#.\#.. \#\#\#.\#\#\# ...@... \#\#\#.\#\#\# ..\#.\#.. ..\#.\#..

0 0

Sample Output

45 59 6 13

广度搜索，需要用到队列：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //bfs
     2 #include<stdio.h>
     3 int map[100][100];
     4 int queue[10000][2];//队列
     5 int sx[4]={
           0,1,0,-1};
     6 int sy[4]={
           1,0,-1,0};
     7 int h,w;
     8 int ans;
     9 void bfs(int x,int y)
    10 {
    11     int rear=0,front=0;
    12     queue[rear][0]=x;//enter queue
    13     queue[rear][1]=y;
    14     rear++;
    15     while(front<rear)
    16     {
    17         for(int t=0;t<4;t++)
    18         {
    19             x=queue[front][0]+sx[t];
    20             y=queue[front][1]+sy[t];
    21             if(map[x][y]=='.'&&x>=1&&x<=w&&y>=1&&y<=h)
    22             {
    23                 queue[rear][0]=x;
    24                 queue[rear][1]=y;
    25                 map[x][y]='#';
    26                 rear++;
    27                 ans++;
    28             }
    29         }
    30         front++;
    31     }
    32     
    33 }
    34 int main()
    35 {
    36     int i,j;
    37     int x,y;
    38     while(scanf("%d%d",&h,&w)!=EOF)
    39     {
    40         if(!h&&!w)break;
    41         ans=0;
    42         for(i=1;i<=w;i++)
    43         {
    44             getchar();
    45             for(j=1;j<=h;j++)
    46             {
    47                 scanf("%c",&map[i][j]);
    48                 if(map[i][j]=='@')
    49                     x=i,y=j;
    50             }
    51         }
    52         bfs(x,y);
    53         printf("%d\n",++ans);
    54     }
    55     return 0;
    56 }

深度搜索：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 int map[30][30];
     3 int t,n,m;
     4 int sx[4]={
           0,0,-1,1};
     5 int sy[4]={-1,1,0,0};
     6 void dfs(int h,int l)//深度搜索
     7 {
     8     int i,hx,hy;
     9     t++;
    10     map[h][l]='@';
    11     for(i=0;i<4;i++)
    12     {
    13         hx=h+sx[i];
    14         hy=l+sy[i];
    15         if(hx>=1&&hx<=m&&hy>=1&&hy<=n&&map[hx][hy]=='.')
    16             dfs(hx,hy);
    17     }
    18 }
    19 int main()
    20 {
    21     int a,b,x,y;
    22     while(scanf("%d%d",&n,&m)!=EOF)
    23     {
    24         if(n==0&&m==0)break;
    25         for(a=1;a<=m;a++)
    26         {
    27             getchar();
    28             for(b=1;b<=n;b++)
    29             {
    30                 scanf("%c",&map[a][b]);
    31                 if(map[a][b]=='@')
    32                 {
    33                     x=a;
    34                     y=b;
    35                 }
    36             }
    37         }
    38         t=0;
    39         dfs(x,y);
    40         printf("%d\n",t);
    41     }
    42     return 0;
    43 }

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220331/af027b732acc46208c67f943343a4102.png