POJ-1979（搜索水题）-蒲公英云

POJ-1979（搜索水题）

题目链接-POJ1979

Red and Black

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 31353		Accepted: 17111

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

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;
}