[白俊C+]1388床飾り

質問する
亨沢は建築家です.今、亨沢は亨沢のボーイフレンドの祈勲の家を完成したばかりだ.亨沢は祈勲の部屋の床の装飾を設計して、今とても好奇心があっていくつかの板が必要です.板には大きさ1の幅、正数の長さがあります.祈勲の部屋は長方形で、壁と平行な正方形に分かれています.
「-」と「|」からなる床装飾の形状が示されます.2つの"-"が隣接している場合、同じ行で2つは同じ板で、2つの"|"が隣接しており、同じ列で2つは同じ板である.
プログラムを書いて、祈勲の部屋の床を飾るのに必要な板の数を出力します.
入力
第1行目は、部屋の床の縦方向の大きさNおよび横方向の大きさMを与える.2行目からN行にM文字があります.これは床の装飾形状で、「-」と「|」だけで構成されています.NとMは50以下の自然数である.
しゅつりょく
最初の行に問題の答えを出力します.
https://www.acmicpc.net/problem/1388
に答える
問題カテゴリはグラフィック理論,DFS,BFSであり,これだけを見て盲目的にキューやスタックで実現してはならない.
問題では、横板(-)は横方向のナビゲーションのためにコードを記述する必要があり、縦板(|)は通過した板を検査する必要がある.
すべての板の位置をチェックします.
すなわち,板がすべてつながっているわけではなく,不規則であり,すべての床パターンを解析する必要があるため,DFS,BFSを盲目的に用いてアクセスすることは不整合である.

find:すべての板をチェックします.

垂直、水平:横、縦の板はすべて1つで、すべて検査します.
find関数で次の位置に移動すると、すでに1つの板に接続されている場合は、その位置をスキップできます.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int n, m, ** wood, res = 0;
bool** visited;
void vertical(int x, int y);
void horizontal(int x, int y);

void find() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j]) {
				if (wood[i][j] == 0)
					vertical(i, j);
				else
					horizontal(i, j);
				res++;
			}
		}
	}
}

void vertical(int x, int y) { //가로
	visited[x][y] = true;
	if (0 <= y - 1 && wood[x][y - 1] == 0 && !visited[x][y - 1]) // ←
		vertical(x, y - 1);
	if (y + 1 <= m - 1 && wood[x][y + 1] == 0 && !visited[x][y + 1]) // →
		vertical(x, y + 1);
}


void horizontal(int x, int y) { //세로
	visited[x][y] = true;
	if (0 <= x - 1 && wood[x - 1][y] == 1 && !visited[x - 1][y]) // ↑
		horizontal(x - 1, y);
	if (x + 1 <= n - 1 && wood[x + 1][y] == 1 && !visited[x + 1][y]) // ↓
		horizontal(x + 1, y);
}

int main(char c) {
	scanf("%d%d", &n, &m);
	wood = new int* [n];
	visited = new bool* [n];
	for (int i = 0; i < n; i++) {
		wood[i] = new int[m];
		visited[i] = new bool[m];
		scanf("%c", &c);
		for (int j = 0; j < m; j++) {
			scanf("%c", &c);
			if (c == '-')
				wood[i][j] = 0;
			else
				wood[i][j] = 1;
			visited[i][j] = false;
		}
	}

	find();

	printf("%d", res);

	return 0;
}