1110: 地砖问题
题目描述
小明站在一个矩形房间里，这个房间的地面铺满了地砖，每块地砖的颜色或是红色或是黑色。小明一开始站在一块黑色的地砖上，并且小明从一块地砖可以向上下左右四个方向移动到其他的地砖上，但是他不能移动到红色地砖上，只能移动到黑色地砖上。
请你编程计算小明可以走到的黑色地砖最多有多少块。
输入
输入包含多组测试数据。
每组输入首先是两个正整数W和H，分别表示地砖的列行数。（1<=W，H<=25）
接下来H行，每行包含W个字符，字符含义如下：
‘.’表示黑地砖；
‘#’表示红地砖；
‘@’表示小明一开始站的位置，此位置是一块黑地砖，并且这个字符在每组输入中仅会出现一个。
当W=0，H=0时，输入结束。
输出
对于每组输入，输出小明可以走到的黑色地砖最多有多少块，包括小明最开始站的那块黑色地砖。
样例输入
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
样例输出
13
思路
求小明所在点的连通分量中的点数，用 DFS 或 BFS 均可。
#include<bits/stdc++.h>
using namespace std;
const int N = 25;
int w, h;
char a[N][N];
int vis[N][N], dir[4][2] = {
{
-1, 0}, {
1, 0}, {
0, 1}, {
0, -1}};
typedef struct Node {
int x, y;
}node;
int main()
{
while(scanf("%d%d", &w, &h) && (w || h)){
queue<node> q;memset(vis, 0, sizeof(vis));for(int i = 0; i < h; i++){
scanf("%s", a[i]);for(int j = 0; j < w; j++){
if(a[i][j] == '@'){
q.push({
i, j});vis[i][j] = 1;} }}int cnt = 0;node p;while(!q.empty()) {
p = q.front();q.pop();cnt++;for(int i = 0; i < 4; i++){
int x = p.x + dir[i][0], y = p.y + dir[i][1];if(x >= 0 && y >= 0 && !vis[x][y] && a[x][y] == '.'){
q.push({
x, y});vis[x][y] = 1;}}}printf("%d\n", cnt);}return 0;
}