盤の端からたどって囲まれた空き地だけを埋める

グラフ問題 113

土と水のマスが並んだ盤で、盤の端につながっていない水のまとまりを土で埋めた盤を返します。囲まれた所を探すのではなく、端から届く水に印を付けて、残りを埋める練習です。

海外で定番の問題リスト 4 本には入っていません

問題

畑の区画を表す盤を、行の文字列の並び board で受け取ります。各マスは "X" (土) か "O" (水) です。上下左右で隣り合う水どうしは、同じ水たまりに属します。

畑の外は川で、盤の端の水は川へ流れ出せます。水たまりのうち、どのマスも盤の端に無い (盤の端の水と上下左右でつながっていない) 物は流れ出せないので、土で埋めます。埋めたあとの盤を、同じ形の行の文字列の並びで返す関数を書いてください。

盤の端につながっている水たまりは、そのまま残します
斜めにしか隣り合っていない水どうしは、つながっていないものとします
行の数と列の数は、どちらも 1 以上 50 以下です。どの行も同じ長さです

入力と出力の例

例 1

まん中の 3 マスの水たまりは、端に届かないので埋めます。上の行の右から 2 つ目の水は盤の端にあるので残ります。

board = ["XXOX", "XXXX", "XOOX", "XOXX", "XXXX"]

["XXOX", "XXXX", "XXXX", "XXXX", "XXXX"]

例 2

右下の水たまりは、右の端の水とつながっているので残ります。左上の 1 マスだけが埋まります。

board = ["XXXXX", "XOXXX", "XXXOO", "XXXOX"]

["XXXXX", "XXXXX", "XXXOO", "XXXOX"]

例 3

1 行だけの盤では、どのマスも端にあるので、何も埋まりません。

board = ["OXO"]

["OXO"]

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「X と O の盤で、X に囲まれた O の領域を全部 X に書き換えてください」
囲まれた領域を 1 つずつ調べる書き方を出すと、「逆から考えられませんか？囲まれていない方が見つけやすくないですか？」と聞かれます
LeetCode では盤をその場で書き換えますが、ここでは書き換えた盤を返す形にしています

「囲まれている」の決め方 (端にあるマスとつながっていない) を最初に確かめておくと、端から探す考えにすぐ進めます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「グラフ探索と幅優先探索」に、この型の要点を表とコードでまとめています。

グラフ探索は、つながりを近い順か奥からたどります。迷路、最短の手数、講座を受ける順のような問題が同じ形です。

まず考える手順

段 1

水たまりを 1 つずつたどり、端のマスを含むかを調べて、含まなければ埋める書き方がまず浮かびます。動きますが、たどりながら「端に届いたか」を持ち回る必要があり、たどった水たまりをあとでもう一度埋めに回る手間もあります。

段 2

裏から考えます。残る水は「盤の端の水から、水をたどって届くマス」です。そこで、盤の 4 辺のマスを始めとして、水のマスをたどり、届いたマスに印 (たとえば "S") を付けます。

段 3

印を付け終えたら、盤を 1 回見て、印の付いていない水 "O" を土 "X" に、印 "S" を水 "O" に戻します。埋めるかどうかを、マスごとにその場で決められます。

段 4

たどるのは、自分で持つスタックで行います。再帰で書くと、盤が全部水のとき呼び出しが 2500 段まで深くなるためです。受け取った行は文字列で書き換えられないので、まず 1 字ずつの並びに直してから印を付けます。

解答

Python

def surround_regions(board):
    h = len(board)
    w = len(board[0])
    g = [list(s) for s in board]
    todo = []
    for r in range(h):
        todo.append((r, 0))
        todo.append((r, w - 1))
    for c in range(w):
        todo.append((0, c))
        todo.append((h - 1, c))
    # 端から届く水に印 S を付ける
    while todo:
        r, c = todo.pop()
        if not (0 <= r < h and
                0 <= c < w):
            continue
        if g[r][c] != "O":
            continue
        g[r][c] = "S"
        todo += [(r + 1, c),
                 (r - 1, c),
                 (r, c + 1),
                 (r, c - 1)]
    return ["".join(row)
            .replace("O", "X")
            .replace("S", "O")
            for row in g]

JavaScript

function surroundRegions(
  board,
) {
  const h = board.length;
  const w = board[0].length;
  const g = board.map(
    (row) => [...row]);
  const todo = [];
  for (let r = 0; r < h; r++) {
    todo.push([r, 0]);
    todo.push([r, w - 1]);
  }
  for (let c = 0; c < w; c++) {
    todo.push([0, c]);
    todo.push([h - 1, c]);
  }
  // 端から届く水に印 S を付ける
  while (todo.length) {
    const [r, c] = todo.pop();
    if (r < 0 || r >= h ||
      c < 0 || c >= w) {
      continue;
    }
    if (g[r][c] !== "O") {
      continue;
    }
    g[r][c] = "S";
    todo.push(
      [r + 1, c], [r - 1, c],
      [r, c + 1], [r, c - 1]);
  }
  return g.map((row) => row
    .join("")
    .replaceAll("O", "X")
    .replaceAll("S", "O"));
}

Go

import "strings"

func surroundRegions(
	board []string,
) []string {
	h := len(board)
	w := len(board[0])
	g := make([][]byte, h)
	for r := range board {
		g[r] = []byte(board[r])
	}
	todo := [][2]int{}
	for r := 0; r < h; r++ {
		todo = append(todo,
			[2]int{r, 0},
			[2]int{r, w - 1})
	}
	for c := 0; c < w; c++ {
		todo = append(todo,
			[2]int{0, c},
			[2]int{h - 1, c})
	}
	// 端から届く水に印 S を付ける
	for len(todo) > 0 {
		p := todo[len(todo)-1]
		todo = todo[:len(todo)-1]
		r, c := p[0], p[1]
		if r < 0 || r >= h ||
			c < 0 || c >= w {
			continue
		}
		if g[r][c] != 'O' {
			continue
		}
		g[r][c] = 'S'
		todo = append(todo,
			[2]int{r + 1, c},
			[2]int{r - 1, c},
			[2]int{r, c + 1},
			[2]int{r, c - 1})
	}
	out := []string{}
	for _, row := range g {
		s := strings.ReplaceAll(
			string(row), "O", "X")
		out = append(out,
			strings.ReplaceAll(
				s, "S", "O"))
	}
	return out
}

置き換えは、先に O を X に、次に S を O にする順です。逆にすると、印を戻した水まで土にしてしまいます。

計算量

時間は O(m × n) です。m と n は行と列の数です。印を付けるのは、どのマスも 1 回までで、積まれる回数も上下左右からの 4 回までです。最後の置き換えも全部のマスを 1 回ずつ見ます
使う記憶は O(m × n) です。書き換えるための盤の写しと、スタックに積むマスです

よくある間違い

端の水を始めにしない。囲まれた水たまりを内側から探すと、端に届くかを調べ終えるまで埋めるか決められず、書き方がややこしくなります
置き換えの順を逆にする。 S を O に戻してから O を X にすると、残すはずの水まで全部土になります
斜めにもたどる。斜めでつながる水は別の水たまりです。斜めにたどると、囲まれた水たまりを端とつながったと見て残してしまいます
1 行や 1 列の盤で困る。どのマスも端にあるので、全部の水が残ります。4 辺を始めにする書き方なら、そのまま正しく動きます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def surround_regions(board: list[str]) -> list[str]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(surround_regions(["XXOX", "XXXX", "XOOX", "XOXX", "XXXX"]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します