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"); }