今回は paiza の「陣取りゲーム」の問題に挑戦！
「陣取りゲーム」シリーズのAランク最終問題をいよいよ解いていく！
問題概要
🧩 盤面と初期状態
-
H×Wの盤面がある - マスの種類は以下の4つ：
-
.：まだ誰の陣地でもないマス -
#：障害物（通れない） -
A：A さんの初期位置 -
B：B さんの初期位置
A と B の初期位置は それぞれ1マスずつ
-
- どちらが先攻か（
AorB）が与えられる
🔁 ゲームの進行ルール
- A さんと B さんが 交互に手番を行う
- 手番でできる操作は次の通り：
▶ 手番の操作
- 自分の陣地から上下左右に1マス移動して到達できて、まだ誰の陣地でもないマス（
.）をすべて自分の陣地にする - ただし
#（障害物）は陣地にできない - 新たに陣地にできるマスがない場合は 何もしない
🛑 ゲーム終了条件
- A・B 両方がこれ以上陣地を広げられなくなったとき
🎯 求める出力
ゲーム終了時の
- A さんの陣地数 / B さんの陣地数
- 勝者の名前
- 陣地数が多い方が勝ち
- 引き分けは起きないことが保証されている
入力例:
3 3 // H W
A // N (先攻)
A..
...
..B
出力例:
6 3
A
※ 例の最終盤面
AAA
AAB
ABB
✅OK例：
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l));
rl.on('close', () => {
// ========= 入力 =========
const [H, W] = lines[0].split(' ').map(Number);
const first = lines[1]; // 先攻 ('A' or 'B')
const grid = lines.slice(2).map(r => r.split(''));
const dy = [1, -1, 0, 0];
const dx = [0, 0, 1, -1];
// ========= キューと管理変数 =========
// 0 → A, 1 → B
const queue = [[], []];
const score = [0, 0];
const AB = ['A', 'B'];
let turn = first === 'A' ? 0 : 1; // 現在の手番
let step = 0; // 現在の距離（手番回数）
// ========= スタート地点 =========
for (let y = 0; y < H; y++) {
for (let x = 0; x < W; x++) {
if (grid[y][x] === 'A') {
queue[0].push([y, x, 0]);
score[0]++;
}
if (grid[y][x] === 'B') {
queue[1].push([y, x, 0]);
score[1]++;
}
}
}
// ========= BFS =========
while (queue[0].length > 0 || queue[1].length > 0) {
// 今のプレイヤーが動けないなら交代
if (queue[turn].length === 0) {
turn ^= 1;
continue;
}
const [y, x, dist] = queue[turn][0];
// 距離が進んだら手番交代
if (dist > step) {
step = dist;
turn ^= 1;
continue;
}
// 現在マスを処理
queue[turn].shift();
const mark = AB[turn];
for (let d = 0; d < 4; d++) {
const ny = y + dy[d];
const nx = x + dx[d];
if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
if (grid[ny][nx] !== '.') continue;
grid[ny][nx] = mark;
score[turn]++;
queue[turn].push([ny, nx, dist + 1]);
}
}
// ========= 出力 =========
console.log(score[0], score[1]);
console.log(score[0] > score[1] ? 'A' : 'B');
});
🔍コードの流れ
① 入力を受け取る
- 盤面サイズ
H, W - 先攻プレイヤー
first - 盤面
gridを読み込む
② BFS 用の準備
-
queue[0]→ プレイヤー A の探索キュー -
queue[1]→ プレイヤー B の探索キュー -
score[0],score[1]で陣地数を管理 -
turnで現在の手番（A or B）を管理 -
stepで「現在の距離（＝手番の段数）」を管理
③ スタート地点をキューに入れる
- 盤面を走査して
- A の位置を
queue[0]に距離0で追加 - B の位置を
queue[1]に距離0で追加
- A の位置を
- 初期マス分をそれぞれ
scoreに加算
④ BFS（メインループ）
A か B のどちらかが動ける限り 処理を続ける
④-1. 手番プレイヤーが動けるか確認
- 今の
turnのキューが空なら- 手番を相手に渡して
continue
- 手番を相手に渡して
④-2. 次に処理するマスの距離を確認
- キュー先頭の
distを取得 -
dist > stepなら- ここで ターンが一段進んだ ことを意味する
-
stepを更新し、手番交代
④-3. マスを処理
- キュー先頭を取り出す
- 上下左右4方向を調べる
- 中立マス
'.'を見つけたら- 現在のプレイヤーの陣地にする
- 陣地数を増やす
- 距離
dist + 1で同じプレイヤーのキューに追加
- 現在のプレイヤーの陣地にする
⑤ 探索終了
- A・B 両方のキューが空になったら BFS 終了
- 盤面は完全に塗り終わっている
⑥ 結果を出力
- A と B の陣地数を出力
- 数が多い方を勝者として出力（引き分けなし）
この解法のポイント
-
queueを 2 つに分けている - 距離（
dist）＝ 手番の段数 - 距離が進んだタイミングで手番交代
✅OK例 2：
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l));
rl.on('close', () => {
// ======================
// 入力
// ======================
const [H, W] = lines[0].split(' ').map(Number);
const first = lines[1]; // 先攻 ('A' or 'B')
const grid = lines.slice(2).map(r => r.split(''));
const dy = [1, -1, 0, 0];
const dx = [0, 0, 1, -1];
// ======================
// BFS用キューとスコア
// [y, x, プレイヤー]
// ======================
const queue = [];
const score = { A: 0, B: 0 };
// ======================
// スタート地点を
// 「先攻 → 後攻」の順でキューに入れる
// ======================
let ay, ax, by, bx;
for (let y = 0; y < H; y++) {
for (let x = 0; x < W; x++) {
if (grid[y][x] === 'A') {
ay = y; ax = x;
}
if (grid[y][x] === 'B') {
by = y; bx = x;
}
}
}
if (first === 'A') {
queue.push([ay, ax, 'A']);
queue.push([by, bx, 'B']);
} else {
queue.push([by, bx, 'B']);
queue.push([ay, ax, 'A']);
}
score.A++;
score.B++;
// ======================
// 幅優先探索（BFS）
// ======================
while (queue.length > 0) {
const [y, x, p] = queue.shift();
for (let d = 0; d < 4; d++) {
const ny = y + dy[d];
const nx = x + dx[d];
if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
if (grid[ny][nx] !== '.') continue;
grid[ny][nx] = p;
score[p]++;
queue.push([ny, nx, p]);
}
}
// ======================
// 出力
// ======================
console.log(score.A, score.B);
console.log(score.A > score.B ? 'A' : 'B');
});
🔍 コードの流れ
① 入力を受け取る
- 盤面サイズ
H, W - 先攻プレイヤー
first（'A' or 'B'） - 盤面
gridを読み込む
② BFS の準備
- 上下左右移動用の配列
dy,dxを用意 - BFS 用の 1 つのキュー
queue- 中身は
[y, x, プレイヤー]
- 中身は
- 陣地数を管理する
score（A・B）
③ A・B の初期位置を取得
- 盤面を走査して
- A の位置 (
ay,ax) - B の位置 (
by,bx)
を記録
- A の位置 (
④ スタート地点を「先攻 → 後攻」の順でキューに入れる
- 先攻プレイヤーのマスを 先に
queueに入れる - 後攻プレイヤーのマスを 後に 入れる
- 初期マスとして
score.A++score.B++
👉 この投入順が手番順を表すポイント
⑤ 幅優先探索（BFS）
- キューが空になるまで繰り返す
- キュー先頭のマスを取り出す
- 上下左右 4 方向を確認
- 盤面外 → 無視
- すでに陣地 → 無視
- 中立マス
'.'→ 現在のプレイヤーの陣地にする
- 陣地にしたら
- 陣地数を
+1 - そのマスを同じプレイヤーとしてキューに追加
- 陣地数を
👉 BFS の性質により、先に入ったプレイヤーが常に先に広がる
⑥ 探索終了
キューが空になった時点で、どちらも陣地を広げられない状態
→ ゲーム終了
⑦ 結果を出力
- A・B の陣地数を出力
- 陣地数が多い方を勝者として出力
この解法のポイント
- 幅優先探索（BFS）では、マスは距離の昇順にキューから処理される
- この性質を利用して、手番を明示的に管理しない
- キューは 1 つだけ使う
- 初期状態で
- 先攻プレイヤーのスタート地点 → 後攻プレイヤーのスタート地点
の順にキューへ入れる - BFS により
- 先にキューへ入ったプレイヤーのマスが常に同距離帯で先に処理される
- その結果、「先攻 → 後攻 → 先攻 → …」という手番順が自然に再現される
📝まとめ
2人が交互に陣地を広げる→２つの起点をもつ BFS。
🌟手番の表現方法は複数ある
✅ 方法①：キューを2つ使って手番を明示
- A 用キュー / B 用キュー
- 距離（段数）が進んだら手番交代
- ゲームっぽく直感的
👉 理解しやすく実装も安全
✅ 方法②：キュー1つ＋投入順で制御（最シンプル）
- 初期状態で、先攻 → 後攻 の順でキューに入れる
- BFS の性質により、同じ距離帯では先に入った方が必ず先に処理される
- 手番管理が不要
👉 実装がスマートな気がする
💡おまけ：🔨 OK例：最初にテストケースを通過したコード
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [H, W] = lines[0].split(' ').map(Number);
const N = lines[1];
const grid = lines.slice(2).map(line => line.split(''));
// キュー
const playerQueue = { A: [], B: [] };
// 方向管理
const dy = [1, -1, 0, 0];
const dx = [0, 0, 1, -1];
// スタート地点の A と B をキューへ追加
let count = 0;
LABEL:
for (let y = 0; y < H; y++) {
for (let x = 0; x < W; x++) {
if (grid[y][x] === 'A' || grid[y][x] === 'B') {
playerQueue[grid[y][x]].push([y, x, 0]); // y, x, 操作回数
count++;
if (count === 2) break LABEL;
}
}
}
// ターンテーブル
const AB = ['A', 'B'];
let n = N === 'A' ? 0 : 1;
let player = AB[n]; // 手番のプレイヤー
let countAB = [0, 0]; // 操作回数
let countDown = H * W - 2; // 残りの中立マス
// BFS
while (countDown > 0) {
if (playerQueue.A.length === 0 && playerQueue.B.length === 0) {
break;
}
// 空キュー対策
if (playerQueue[player].length === 0) {
n = (n + 1) % 2;
player = AB[n];
continue;
}
// ターン交代か判定
const nextCur = playerQueue[player][0][2];
if (countAB[n] < nextCur) {
countAB[n] = nextCur;
n = (n + 1) % 2;
player = AB[n];
continue;
}
//
const [y, x, cur] = playerQueue[player].shift();
const next = cur + 1;
// 4方向チェック
for (let i = 0; i < 4; i++) {
const ny = y + dy[i];
const nx = x + dx[i];
// 範囲外＆中立マスチェック
if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
if (grid[ny][nx] !== '.') continue;
grid[ny][nx] = player; // プレイヤーの陣地にする
playerQueue[player].push([ny, nx, next]); // キューに追加
countDown--; // 中立マスカウントを減らす
}
}
// 陣地の数
let A = 0;
let B = 0;
grid.forEach(row => {
A += row.filter(g => g === 'A').length;
B += row.filter(g => g === 'B').length;
});
// 結果出力
console.log(A, B)
console.log(A > B ? 'A' : 'B');
});
失敗を全部踏んだ上で、全部自力で回避した！🔨