PythonでXに囲まれた領域を捕獲する：DFSを使った盤面探索アルゴリズム

XとOが含まれる2次元のボードが与えられたとき、Xによって完全に囲まれたすべての領域を「捕獲」する問題を考えます。ここでの捕獲とは、囲まれた領域内にあるOをすべてXへ変更することを指します。

たとえば、次のようなボードがあるとします。

この問題を解いた後の出力は以下のようになります。中央のOはXに完全に囲まれているためXへ変換されますが、左下のOはボードの端に接しているため、囲まれていないとしてそのまま残ります。

解法のアプローチ

この問題のポイントは、「ボードの端（境界）に接しているOは決して捕獲されない」という性質を利用することです。以下の手順で解いていきます。

1. ボードが存在しない場合は、空のボードを返します。
2. 各行について、左端のセルが「O」なら make_one を呼び出し、右端のセルが「O」なら同様に make_one を呼び出します。
3. 各列について、上端のセルが「O」なら make_one を呼び出し、下端のセルが「O」なら同様に make_one を呼び出します。
4. 最後に全セルを走査し、「O」は「X」に変換し、一時的なマークである「1」は元の「O」に戻します。

なぜ境界から探索するのか

境界線上にあるOや、そこから連結しているOは外部につながっているため、Xに囲まれていません。そこで、まず境界から到達できるすべてのOを一時的な値「1」でマークします。その後、マークされていない残りのOだけが「真に囲まれた領域」なので、それらをXへ変換し、最後にマークした「1」を元のOへ復元すれば完成です。

make_one 関数の動作

• 座標 (i, j) がボードの範囲外、セルが「X」、あるいはすでに「1」でマークされている場合は、何もせずに戻ります。
• それ以外の場合は、現在のセルを「1」に書き換えます。
• 上下左右の4方向に対して、再帰的に make_one を呼び出します。

これは典型的な深さ優先探索（DFS）による連結成分の探索であり、時間計算量・空間計算量はともに O(m × n)（m は行数、n は列数）となります。

実装例

class Solution(object):
   def solve(self, board):
      if not board:
         return board
      for i in range(len(board)):
         if board[i][0]=='O':
            self.make_one(board,i,0)
         if board[i][len(board[0])-1] == 'O':
            self.make_one(board,i,len(board[0])-1)
      for i in range(len(board[0])):
         if board[0][i]=='O':
            self.make_one(board,0,i)
         if board[len(board)-1][i] == 'O':
            self.make_one(board,len(board)-1,i)
      for i in range(len(board)):
         for j in range(len(board[i])):
            if board[i][j]=='O':
               board[i][j]='X'
            elif board[i][j]=='1':
               board[i][j]='O'
      return board
   def make_one(self, board,i,j):
      if i<0 or j<0 or i>=len(board) or j>=len(board[0]) or board[i][j]=='X' or board[i][j]=='1':
         return
      board[i][j]='1'
      self.make_one(board,i+1,j)
      self.make_one(board,i-1,j)
      self.make_one(board,i,j+1)
      self.make_one(board,i,j-1)
ob1 = Solution()
print(ob1.solve([["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]))

入力

[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

出力

[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]

このように、境界からDFSで到達可能なOを先にマークしておくことで、囲まれた領域だけを正確に識別し、効率よく捕獲することができます。