龍の頭 （paizaランク：A相当）
白と黒の 2 色からなる画像が与えられます。
この画像は縦 H、横 W 個のピクセルが長方形状に敷き詰められるようにして構成されています。
また、この画像の左上のピクセルを P(1, 1)として、上から i 番目、左から j 番目のピクセルを P(i, j) と定義します。
あなたはこの中に黒色の長方形がいくつ存在するのかを数えたくなりました。
ただし、黒色の長方形は、長方形の左上の点 (y_0, x_0) および縦と横の長さ h, w から定義される以下のようなものを指します。
・y_0 ≦ y < y_0 + h, x_0 ≦ x < x_0 + w を満たす任意の y, x について、P(y, x) は黒
・y_0 ≧ 2 の場合、x_0 ≦ x < x_0 + w を満たす任意の x について、P(y_0 - 1, x) は白
・y_0 + h ≦ H の場合、x_0 ≦ x < x_0 + w を満たす任意の x について、P(y_0 + h, x) は白
・x_0 ≧ 2 の場合、y_0 ≦ y < y_0 + h を満たす任意の y について、P(y, x_0 - 1) は白
・x_0 + w ≦ W の場合、y_0 ≦ y < y_0 + h を満たす任意の y について、P(y, x + w) は白
解答例(JavaScript)
画像の各ピクセルについて、ある点(y_0, x_0)が、黒色領域のピクセルで、未探索だった時、そのピクセルをスタート地点として、以下の処理をする。
- 黒色領域を長方形と仮定した時の縦と横の長さ h, wを求める。
(これは幅優先探索で、黒色領域内の、最大のy座標の値y_maxと、最大のx座標の値x_maxを求め、左上の点y_0,x_0との差を取ることで求められる。) - 黒色領域の左上の点 (y_0, x_0) および縦と横の長さ h, wが、問題文で与えられた長方形の定義を満たすか調べる。
- 条件を満たしたら、黒色の長方形をカウントする。
画像の全ピクセルについて、以上の処理が終わったら、黒色の長方形の数を出力する。
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//画像は縦 H、横 W 個のピクセル
const [H, W] = lines[0].split(" ").map(Number);
//画像
const P = lines.slice(1).map(line => line.split(""));
/*探索での訪問管理、画像の白黒を01に置換*/
let visited = Array(H).fill(0).map((row, i) =>
row = Array(W).fill(-1).map((cell, j) => {
if (P[i][j] === "W") {
return 1;//白なら1探索済
} else {
return 0;//黒なら0未探索
}
}));
let count = 0;//黒色長方形の数
/* 画像の全てのピクセルについて、順に
長方形の左上の点 (y_0, x_0)として調べる */
for (let y_0 = 0; y_0 < H; y_0++) {
for (let x_0 = 0; x_0 < W; x_0++) {
//(y_0, x_0)が白色、または、探索済ならスキップする
if (visited[y_0][x_0] === 1) continue;
/* 黒色領域を長方形と仮定して、縦と横の長さ h, w を求める */
/*(y_0, x_0)から黒の領域内を探索して、一番大きい座標の値
である、y_max,x_maxを求める。*/
let [y_max, x_max] = [y_0, x_0];//探索開始座標から
//幅優先探索(y_max,x_maxを求める)
let q = [[y_0, x_0]];//キュー
visited[y_0][x_0] = 1;//開始点訪問済に
//探索
while (q.length > 0) {
const [y, x] = q.shift();
//上下左右に移動
const move = [[-1, 0], [0, 1], [1, 0], [0, -1]];
move.forEach(v => {
const [s, t] = [v[0], v[1]];
let ny = y + t;
let nx = x + s;
//移動先が、画像内 かつ 黒色で未探索だったら
if (0 <= ny && ny <= H - 1 && 0 <= nx && nx <= W - 1 &&
visited[ny][nx] === 0) {
q.push([ny, nx]);//キューへ
visited[ny][nx] = 1;//訪問済
//最大値更新
if (ny > y_max) y_max = ny;
if (nx > x_max) x_max = nx;
}
});
} // while
//黒色領域を長方形と仮定したときの縦と横の長さ h, wを求める
const h = y_max - y_0 + 1;
const w = x_max - x_0 + 1;
/* 黒色領域の左上の点 (y_0, x_0) および縦と横の長さ h, wが
長方形の定義を満たすか */
let flag = true;//長方形の定義を満たすか
/* y_0 ≦ y < y_0 + h, x_0 ≦ x < x_0 + w を満たす
任意の y, x について、P(y, x) は黒 */
for (let y = y_0; y < y_0 + h; y++) {
for (let x = x_0; x < x_0 + w; x++) {
if (P[y][x] === "W") {
//黒色の長方形でない
flag = false;
break;
}
}
if (!flag) break;
}
if (!flag) continue;
/* y_0 ≧ 2 の場合、x_0 ≦ x < x_0 + w を満たす
任意の x について、P(y_0 - 1, x) は白 */
if (y_0 >= 1) {
for (let x = x_0; x < x_0 + w; x++) {
if (P[y_0 - 1][x] === "B") {
//黒色の長方形でない
flag = false;
break;
}
}
if (!flag) continue;
}
/* y_0 + h ≦ H の場合、x_0 ≦ x < x_0 + w を満たす
任意の x について、P(y_0 + h, x) は白 */
if (y_0 + h < H) {
for (let x = x_0; x < x_0 + w; x++) {
if (P[y_0 + h][x] === "B") {
//黒色の長方形でない
flag = false;
break;
}
}
}
if (!flag) continue;
/* x_0 ≧ 2 の場合、y_0 ≦ y < y_0 + h を満たす
任意の y について、P(y, x_0 - 1) は白 */
if (x_0 >= 1) {
for (let y = y_0; y < y_0 + h; y++) {
if (P[y][x_0 - 1] === "B") {
//黒色の長方形でない
flag = false;
break;
}
}
if (!flag) continue;
}
/* x_0 + w ≦ W の場合、y_0 ≦ y < y_0 + h を満たす
任意の y について、P(y, x + w) は白 */
if (x_0 + w < W) {
for (let y = y_0; y < y_0 + h; y++) {
if (P[y][x_0 + w] === "B") {
//黒色の長方形でない
flag = false;
break;
}
}
}
if (!flag) continue;
/* 条件を満たしたら、黒色の長方形をカウントする。 */
count += 1;
} // for x_0
} // for y_0
//黒色の長方形の数を出力
console.log(count);