POJ-1979（搜索水题）

ゞ浴缸里的玫瑰 2022-09-26 02:17 163阅读 0赞

## 题目链接-**[POJ1979][]  ** ##

Red and Black

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;30000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;31353</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;17111</td> 
  </tr> 
 </tbody> 
</table>

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)   
The end of the input is indicated by a line consisting of two zeros.

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

Source

[Japan 2004 Domestic][]

**题目大意：给你一张地图，'@'为你的初始位置，‘.’为可以走的地方，'\#'为墙不可通过，问你从初始位置出发最多可以走多少步，走过的地方不能走第二次，起始位置也算一步。**

**题目思路：简单的bfs，输入时记录下初始位置，然后从这点开始bfs，用队列存可以走的点，进队时把改点改为'\#'，也可以用标记，然后答案+1，最后走完后输出所求的答案，时间复杂度为O(W\*H),最多每个点都进出一次队列！**

**AC代码：**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int maxn = 22;
    char Map[maxn][maxn];
    int fx[4][2]={1,0,-1,0,0,-1,0,1};
    int n,m;
    int bfs(int x,int y){
        int res=1;
        Map[x][y]='#';
        queue<pair<int,int> >q;
        q.push(make_pair(x,y));
        while(!q.empty()){
            x=q.front().first;
            y=q.front().second;
            q.pop();
            for(int i=0;i<4;i++){
                int h=x+fx[i][0],l=y+fx[i][1];
                if(h>=0&&h<n&&l>=0&&l<m&&Map[h][l]=='.'){
                    res++;
                    Map[h][l]='#';
                    q.push(make_pair(h,l));
                }
            }
        }
        return res;
    }
    int main()
    {
      while(cin>>m>>n&&(n+m)){
        int x,y;
        for(int i=0;i<n;i++)
        {
            scanf("%s",Map[i]);
            for(int j=0;j<m;j++)
               if(Map[i][j]=='@')x=i,y=j;
        }
        cout<<bfs(x,y)<<endl;
      }
      return 0;
    }

[POJ1979]: http://poj.org/problem?id=1979
[Japan 2004 Domestic]: http://poj.org/searchproblem?field=source&key=Japan+2004+Domestic