Question

一道C++题目，ACM入门题！求解

海内存知己
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB
Total submit users: 49, Accepted users: 34
Problem 12612 : No special judgement
Problem description
小明是个很开朗的孩子，参加过很多的活动，在学校的人际关系非常好，他的朋友也特别多,可以说是遍布全校。但是在升国旗的时候，大家是按班级排队的。为简单起见，小明的朋友用"."表示，不是小明的朋友用"X"表示
....
XXX.
XX..
...X
像这种情况，小明的朋友都是连在一起的，我们认为小明的朋友只被分成了1部分。 你能算出他的朋友一共被分成几个部分吗？

Input
每组测试数据的第1行是一个整数m(0 < m ≤ 50)，表示方阵是大小m*m，接下来的m行，每行有m个字符，"."表示小明的朋友，"X"表示不是小明的朋友。读入直到文件的结束。

Output
求小明的朋友被分成几部分，每行一个整数。

Sample Input
2
..
XX
3
...
XXX
...
4
....
XXX.
XX..
....
Sample Output
1
2
1

Answer 1

遍历一遍, 将遍历过的朋友'.'标记成非朋友'X'就行了.

#include <iostream>
using namespace std;
char arr[50][50];
void search (int x, int y, int m)
{
	//search up
	if (x > 0 && arr[x-1][y] == '.'){
		arr[x-1][y] = 'X';
		search(x-1, y, m);
	}
	//search down
	if (x < m - 1 && arr[x+1][y] == '.'){
		arr[x+1][y] = 'X';
		search(x+1, y, m);
	}
	//search left
	if (y > 0 && arr[x][y-1] == '.'){
		arr[x][y-1] = 'X';
		search(x, y-1, m);
	}
	//search right
	if (y < m - 1 && arr[x][y+1] == '.'){
		arr[x][y+1] = 'X';
		search(x, y+1, m);
	}
}
int main()
{
	int m, ans;
	while (!(cin >> m).eof()) {
		for (int i = 0; i < m; ++ i)
			for (int j = 0; j < m; ++ j)
				cin >> arr[i][j];
		ans = 0;
		for (int i = 0; i < m; ++ i)
			for (int j = 0; j < m; ++ j)
				if (arr[i][j] == '.'){
					arr[i][j] = 'X';
					++ ans;
					search(i, j, m);
				}
		cout << ans << endl;
	}
	return 0;
}

追问

不好意思没讲清楚， 就是想问一下什么叫做连在一起？

追答

以一个点(x, y)为参考, 如果这个点的值是'.', 其上下左右若有'.', 则它们是连在一起的.

Answer 2

这么简单的题，便利一遍不就得了，复杂点儿的就是不仅要计算一排的，也要计算一列的和斜着的