ACM-红与黑

问题描述

        有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入数据

        包括多个数据集合。每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。 W 和 H 都不超过 20。在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘ .’：黑色的瓷砖； 2）‘ #’：白色的瓷砖； 3）‘ @’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

        当在一行中读入的是两个零时，表示输入结束。

输出要求

        对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

输入样例

6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0

输出样例

45

解题思路

        这个题目可以描述成给定一点，计算它所在的连通区域的面积。需要考虑的问题包括矩阵的大小，以及从某一点出发向上下左右行走时，可能遇到的三种情况：出了矩阵边界、遇到’.’、遇到’#’。 设 f(x, y)为从点(x,y)出发能够走过的黑瓷砖总数，则

f(x, y) = 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1)

        这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。

参考程序

#include <iostream> using namespace std; int W,H; char z[21][21]; int f(int x,int y){ // 如果走出矩阵范围 if(x < 0 || x >= W || y < 0 || y >= H){ return 0; } if(z[x][y] == '#'){ return 0; }else { z[x][y]='#';// 将走过的瓷砖做标记 return 1 + f(x-1,y) + f(x+1,y) + f(x,y-1) + f(x,y+1); } } int main() { int i,j,num,startX,startY; while(cin >> H >> W){ if(!H && !W){ break; } for(i=0;i<W;i++){ for(j=0;j<H;j++){ cin >> z[i][j]; if(z[i][j] == '@'){ startX = i; startY = j; } } } cout<< f(startX,startY)<<endl; } return 0; }