Aizu - 0118 (DFS)

梦里梦外; 2022-03-12 11:46 104阅读 0赞

タナカ氏が HW アールの果樹園を残して亡くなりました。果樹園は東西南北方向に H × W の区画に分けられ、区画ごとにリンゴ、カキ、ミカンが植えられています。タナカ氏はこんな遺言を残していました。

果樹園は区画単位でできるだけ多くの血縁者に分けること。ただし、ある区画の東西南北どれかの方向にとなりあう区画に同じ種類の果物が植えられていた場合は、区画の境界が分からないのでそれらは 1 つの大きな区画として扱うこと。

例えば次のような 3 × 10 の区画であれば ('リ'はリンゴ、'カ'はカキ、'ミ'はミカンを表す)

![06e2e89f1456440ea922e3c35f8138dc_v_1551353488][]

同じ樹がある区画の間の境界を消すと次のようになり、

![b3cbb27032c86ca044bd03e50507096b_v_1551353488][]

結局 10 個の区画、つまり 10 人で分けられることになります。

雪が降って区画の境界が見えなくなる前に分配を終えなくてはなりません。あなたの仕事は果樹園の地図をもとに分配する区画の数を決めることです。

果樹園の地図を読み込み、分配を受けられる血縁者の人数を出力するプログラムを作成してください。

## Input ##

複数のデータセットが与えられます。各データセットは空白で区切られた H, W (H, W ≤ 100) を含む行から始まり、続いて H × W の文字からなる H 行の文字列が与えられます。この文字列には、リンゴを表す '@'、カキを表す '\#'、ミカンを表す '\*'、の 3 文字しか現れません。

入力はゼロが２つの行で終わります。データセットの数は 20 を超えません。

## Output ##

各データセットごとに、分配を受ける人数を１行に出力してください。

## Sample Input ##

10 10
    ####*****@
    @#@@@@#*#*
    @##***@@@*
    #****#*@**
    ##@*#@@*##
    *@@@@*@@@#
    ***#@*@##*
    *@@@*@@##@
    *@*#*@##**
    @****#@@#@
    0 0

## Output for the Sample Input ##

解题思路:

深度优先搜索,查找有多少个连通块。

由于涉及到多次查询,所以每次查询前要清空Visited数组。

#include <iostream>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    const int MAXN = 110;
    int H, W;
    char TGMAp[MAXN][MAXN];
    bool TGVisited[MAXN][MAXN];
    int TGmoveX[4] = { 0,0,1,-1 };
    int TGmoveY[4] = { 1,-1,0,0 };
    void DFS_TG(int x, int y,char ch) {
    	TGVisited[x][y] = true;
    	for (int i = 0; i < 4; ++i) {
    		int tgnewX = x + TGmoveX[i];
    		int tgnewY = y + TGmoveY[i];
    		if (tgnewX >= 0 && tgnewX < H && tgnewY >= 0 && tgnewY < W && !TGVisited[tgnewX][tgnewY] && TGMAp[tgnewX][tgnewY] == ch) {
    			DFS_TG(tgnewX, tgnewY,ch);
    		}
    	}
    }
    int main() {
    	while (cin >> H >> W) {
    		memset(TGVisited, false, sizeof(TGVisited));
    		int TGKinds = 0;
    		if(H == 0 && W == 0) break;
    		for (int i = 0; i < H; ++i) {
    			for (int j = 0; j < W; ++j) {
    				cin >> TGMAp[i][j];
    			}
    		}
    		for (int i = 0; i < H; ++i) {
    			for (int j = 0; j < W; ++j) {
    				if (!TGVisited[i][j]) {
    					DFS_TG(i, j, TGMAp[i][j]);
    					TGKinds++;
    				}
    			}
    		}
    		cout << TGKinds << endl;
    	}
    
    	return 0;
    }

[06e2e89f1456440ea922e3c35f8138dc_v_1551353488]: https://vj.2vjd.cn/06e2e89f1456440ea922e3c35f8138dc?v=1551353488
[b3cbb27032c86ca044bd03e50507096b_v_1551353488]: https://vj.2vjd.cn/b3cbb27032c86ca044bd03e50507096b?v=1551353488