#1197583 (D) No.86 TVザッピング(2)

• 問題: No.86 TVザッピング(2)
• ユーザー: ゴリポン先生
• 提出日時: 2026-11-07 14:59:15
• 言語: D (dmd 2.113.0)
• 結果: AC
• 実行時間: 1 ms / 5,000 ms
• コード長: 3,246 bytes
• コンパイル時間: 4,097 ms
• コンパイル使用メモリ: 190,920 KB
• 実行使用メモリ: 9,864 KB
• 最終ジャッジ日時: 2026-11-07 14:59:27
• 合計ジャッジ時間: 7,445 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 33

ソースコード

module main;
// https://kmjp.hatenablog.jp/entry/2014/12/05/0930 より
// 2次元グリッド、巡回路、累積和
import std;

int[][] sumH, sumV;

int getSumH(int y, int l, int r)
{
	// 横方向、A[y][l]～A[y][r]がすべて有効か？有効でないなら適当な負の値を返す。
	if (sumH[y][r + 1] - sumH[y][l] == r + 1 - l) return r + 1 - l;
	else return -100_000;
}

int getSumV(int x, int t, int b)
{
	// 縦方向、A[t][x]～A[b][x]がすべて有効か？有効でないなら適当な負の値を返す。
	if (sumV[b + 1][x] - sumV[t][x] == b + 1 - t) return b + 1 - t;
	else return -100_000;
}

void main()
{
	// 入力
	int N, M;
	readln.chomp.formattedRead("%d %d", N, M);
	auto A = new string[](N);
	foreach (ref a; A)
		a = readln.chomp;
	// 答えの計算
	// 有効なチャンネル数を数え上げしつつ、
	// 左端・右端・上端・下端の位置を求める
	int total = 0;
	int left = M - 1, right = 0, top = N - 1, bottom = 0;
	foreach (y; 0 .. N) {
		foreach (x; 0 .. M) {
			if (A[y][x] != '.')
				continue;
			total++;
			left = min(left, x);
			right = max(right, x);
			top = min(top, y);
			bottom = max(bottom, y);
		}
	}
	// 高さと幅は2以上でなければならない
	if (right - left < 1 || bottom - top < 1) {
		writeln("NO");
		return;
	}
	// 累積和を作っておく
	sumH = new int[][](N + 1, M + 1);
	sumV = new int[][](N + 1, M + 1);
	foreach (y; 0 .. N) foreach (x; 0 .. M) {
		sumH[y][x + 1] = sumH[y][x] + (A[y][x] == '.');
	}
	foreach (y; 0 .. N) foreach (x; 0 .. M) {
		sumV[y + 1][x] = sumV[y][x] + (A[y][x] == '.');
	}

	bool ok = false;
	// 長方形ルートかどうかチェック
	int sum = 0;
	// 上下の辺の有効チャンネル数
	sum += getSumH(top, left, right) + getSumH(bottom, left, right);
	// 左右の辺の有効チャンネル数
	sum += getSumV(left, top, bottom) + getSumV(right, top, bottom);
	sum -= 4;	// 4つ角を二重カウントしているので、その分減らす
	if (sum == total) ok = true;
	// 1回右折する点が内部にあるかチェック
	foreach (y; top + 1 .. bottom) {
		foreach (x; left + 1 .. right) {
			if (A[y][x] != '.')
				continue;
			// 右上が欠けるケース
			sum = getSumH(top, left, x) + getSumH(y, x, right) + getSumH(bottom, left, right);
			sum += getSumV(left, top, bottom) + getSumV(x, top, y) + getSumV(right, y, bottom);
			sum -= 6;
			if (sum == total) ok = true;
			// 右下が欠けるケース
			sum = getSumH(top, left, right) + getSumH(y, x, right) + getSumH(bottom, left, x);
			sum += getSumV(left, top, bottom) + getSumV(x, y, bottom) + getSumV(right, top, y);
			sum -= 6;
			if (sum == total) ok = true;
			// 左上が欠けるケース
			sum = getSumH(y, left, x) + getSumH(top, x, right) + getSumH(bottom, left, right);
			sum += getSumV(left, y, bottom) + getSumV(x, top, y) + getSumV(right, top, bottom);
			sum -= 6;
			if (sum == total) ok = true;
			// 左下が欠けるケース
			sum = getSumH(top, left, right) + getSumH(y, left, x) + getSumH(bottom, x, right);
			sum += getSumV(left, top, y) + getSumV(x, y, bottom) + getSumV(right, top, bottom);
			sum -= 6;
			if (sum == total) ok = true;
		}
	}
	// 答えの出力
	writeln(ok ? "YES" : "NO");
}