[白俊C+]21115ギャラリー

質問する

ギャラリーの地図はM*Nの正方形のグリッドで表示できます.正方形の中には壁からなるものもあれば、空の空間からなるものもあります.下図のように壁をグレー、空白を白で表示します.

ギャラリーに絵を掛けます.図の長さは正方形の辺の長さの2倍です.空き地に隣接する壁に絵を掛けるしかないに違いない.これらの絵は重ならない.ライブラリ内のマップが指定されている場合は、保留可能な最大ピクチャ数を出力するプログラムを作成します.

入力

1行目はギャラリーの縦長Mと横長Nを与える.(1≦M,N≦1000)次のM行にはそれぞれN文字があります.文字は「X」または「.」です.「X」は壁です.空白を表す.
入力されたすべてのデータのうち、少なくとも1行目と最後の行、1列目と最後の列は壁です.

しゅつりょく

最大画像数を出力します.
https://www.acmicpc.net/problem/2115

に答える

グラフを探索する必要もありません.
すべての空きスペースでは、上下左右が壁で構成されています.
連続する2つの賞を見つければいいです.

空白領域を右に移動し、空白領域が見つかったときの真上に壁がある場合は、cntの数を増やします.
空白でない場合や壁がない場合(上に空白がある場合)、cntを2で割る.
他の3つの方向も同じです

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int m, n;
bool** gallery;

void init() {
	scanf("%d%d", &m, &n);
	gallery = new bool* [m];
	for (int i = 0; i < m; i++) {
		gallery[i] = new bool[n];
		char _;
		scanf("%c", &_);
		for (int j = 0; j < n; j++) {
			scanf("%c", &_);
			if (_ == 'X')
				gallery[i][j] = false;
			else if (_ == '.')
				gallery[i][j] = true;
		}
	}
}

void func() {
	int res = 0;

	for (int k = 1; k < m - 1; k++) { // → 방향 윗벽 탐색
		int cnt = 0;
		for (int l = 1; l < n - 1; l++) {
			if (gallery[k][l] && !gallery[k - 1][l])
				cnt++;
			else{
				res += cnt / 2;
				cnt = 0;
			}
		}
		res += cnt / 2;
	}
	for (int k = 1; k < m - 1; k++) { // → 방향 아랫벽 탐색
		int cnt = 0;
		for (int l = 1; l < n - 1; l++) {
			if (gallery[k][l] && !gallery[k + 1][l])
				cnt++;
			else{
				res += cnt / 2;
				cnt = 0;
			}
		}
		res += cnt / 2;
	}
	for (int k = 1; k < n - 1; k++) { // ↓ 방향 왼벽탐색
		int cnt = 0;
		for (int l = 1; l < m - 1; l++) {
			if (gallery[l][k] && !gallery[l][k - 1])
				cnt++;
			else{
				res += cnt / 2;
				cnt = 0;
			}
		}
		res += cnt / 2;
	}
	for (int k = 1; k < n - 1; k++) { // ↓ 방향 오른벽탐색
		int cnt = 0;
		for (int l = 1; l < m - 1; l++) {
			if (gallery[l][k] && !gallery[l][k + 1])
				cnt++;
			else{
				res += cnt / 2;
				cnt = 0;
			}
		}
		res += cnt / 2;
	}

	printf("%d", res);
}


int main(void) {
	init();
	func();

	return 0;
}