結果

問題 No.157 2つの空洞
コンテスト
ユーザー data9824
提出日時 2015-05-12 04:06:25
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,429 bytes
コンパイル時間 511 ms
コンパイル使用メモリ 60,372 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 23:38:09
合計ジャッジ時間 1,444 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <limits>
#include <cmath>

using namespace std;

int w, h;
char c[20][20];

void fill(int x, int y, char filling) {
	c[x][y] = filling;
	if (x > 0 && c[x - 1][y] == '.') {
		fill(x - 1, y, filling);
	}
	if (x < w - 1 && c[x + 1][y] == '.') {
		fill(x + 1, y, filling);
	}
	if (y > 0 && c[x][y - 1] == '.') {
		fill(x, y - 1, filling);
	}
	if (y < h - 1 && c[x][y + 1] == '.') {
		fill(x, y + 1, filling);
	}
}

int main() {
	cin >> w >> h;
	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) {
			cin >> c[x][y];
		}
	}
	bool found = false;
	for (int y = 0; y < h && !found; ++y) {
		for (int x = 0; x < w && !found; ++x) {
			if (c[x][y] == '.') {
				fill(x, y, '1');
				found = true;
			}
		}
	}
	found = false;
	for (int y = 0; y < h && !found; ++y) {
		for (int x = 0; x < w && !found; ++x) {
			if (c[x][y] == '.') {
				fill(x, y, '2');
				found = true;
			}
		}
	}
	int result = numeric_limits<int>::max();
	for (int y0 = 0; y0 < h; ++y0) {
		for (int y1 = 0; y1 < h; ++y1) {
			for (int x0 = 0; x0 < w; ++x0) {
				for (int x1 = 0; x1 < w; ++x1) {
					if (c[x0][y1] != '#' && c[x1][y0] != '#' && c[x0][y1] != c[x1][y0]) {
						int broken = (y0 == y1) ? max<int>(0, abs(x1 - x0) - 1)
								: (x0 == x1) ? max<int>(0, abs(y1 - y0) - 1)
								: abs(x1 - x0) + abs(y1 - y0) - 1;
						result = min(result, broken);
					}
				}
			}
		}
	}
	cout << result << endl;
	return 0;
}
0