题目描述
是aoj 不是atcoder
原文是日志 大概题意是 H*W的果园种满了苹果、梨、蜜柑三种果树,
如果把上下左右看成是连接状态那么请问果园可以划分成几个区域
输入
多组数据
第一行输入两个数值 H W 代表果园的长和宽
然后输入H行W列的char数组 代表苹果、梨、蜜柑(@ # * 表示 )
0 0 表示输入结束
输出
每行输出一个答案 表示果园可以划分成多少个相同水果区域
Sample Input
10 10
####*****@
@#@@@@#*#*
@##***@@@*
#****#*@**
##@*#@@*##
*@@@@*@@@#
***#@*@##*
*@@@*@@##@
*@*#*@##**
@****#@@#@
0 0
Output for the Sample Input
33
算法1
解法
DFS BFS 并查集均可 入门模板
类似
poj 1979 Red and Black
C++ 代码
#include <iostream>
using namespace std;
const int N = 110;
char arr[N][N];
int H, W;
int cnt = 0;
int addx[4] = { 1,-1,0,0 };
int addy[4] = { 0,0,1,-1 };
void dfs( int x, int y,char p)
{
arr[x][y] = '0';
for (int i = 0; i < 4; i++) {
int newx = x + addx[i];
int newy = y + addy[i];
if (newx >= 0 && newx < H && newy >= 0 && newy < W && arr[newx][newy] == p) {
dfs(newx, newy, p);
}
}
}
int main()
{
while (cin >> H >> W, W != 0) {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> arr[i][j];
}
}
cnt = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (arr[i][j] != '0') {
cnt++;
dfs(i, j, arr[i][j]);
}
}
}
cout << cnt << endl;
}
return 0;
}