题意：

image.png

解题思路：

  1. 思路：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。
  2. 1. 从边界出发，对图递归dfs搜索，如果找到O, 则替换成#号作为占位符；
  3. 2. 递归结束后，将剩下的O（除边界外的）替换成X，将第一步替换的#号还原成O；

PHP代码实现：

  1. class Solution {
  3.     private $row,$col;
  4.     /**
  5.      * @param String[][] $board
  6.      * @return NULL
  7.      */
  8.     function solve(&$board) {
  9.         if (empty($board)) return;
  10.         $this->row = count($board);
  11.         $this->col = count($board[0]);
  13.         for ($i = 0; $i < $this->row; $i++) {
  14.             for ($j = 0; $j < $this->col; $j++) {
  15.                 $isEdge = $i == 0 || $j == 0 || $i == $this->row - 1 || $j == $this->col - 1;
  16.                 if ($isEdge && $board[$i][$j] == 'O') $this->dfs($board, $i, $j);
  17.             }
  18.         }
  19.         for ($i = 0; $i < $this->row; $i++) {
  20.             for ($j = 0; $j < $this->col; $j++) {
  21.                 if ($board[$i][$j] == 'O') $board[$i][$j] = 'X';
  22.                 if ($board[$i][$j] == '#') $board[$i][$j] = 'O';
  23.             }
  24.         }
  25.         return;
  26.     }
  28.     function dfs(&$board, $i, $j) {
  29.         if ($i < 0 || $j < 0 || $i >= $this->row 
  30.             || $j >= $this->col || $board[$i][$j] == 'X' || $board[$i][$j] == '#') {
  31.             return;
  32.         }
  33.         $board[$i][$j] = '#';
  34.         $this->dfs($board, $i - 1, $j);
  35.         $this->dfs($board, $i + 1, $j);
  36.         $this->dfs($board, $i, $j - 1);
  37.         $this->dfs($board, $i, $j + 1);
  38.     }
  39. }

GO代码实现：

  1. func solve(board [][]byte)  {
  2.     if board == nil || len(board) == 0 {
  3.         return
  4.     }
  5.     for i := 0; i < len(board); i++ {
  6.         for j := 0; j < len(board[0]); j++ {
  7.             isEdge := i == 0 || j == 0 || i == len(board) - 1 || j == len(board[0]) - 1
  8.             if isEdge && board[i][j] == 'O' {
  9.                 dfs(board, i, j)
  10.             }
  11.         }
  12.     }
  14.     for i := 0; i < len(board); i++ {
  15.         for j := 0; j < len(board[0]); j++ {
  16.             if board[i][j] == 'O' {
  17.                 board[i][j] = 'X'
  18.             }
  19.             if board[i][j] == '#' {
  20.                 board[i][j] = 'O'
  21.             }
  22.         }
  23.     }
  24. }
  26. func dfs(board [][]byte, i, j int) {
  27.     if i < 0 || j < 0 || i >= len(board) ||
  28.         j >= len(board[0]) || board[i][j] == 'X' || board[i][j] == '#' {
  29.         return
  30.     }
  31.     board[i][j] = '#'
  32.     dfs(board, i - 1, j)
  33.     dfs(board, i + 1, j)
  34.     dfs(board, i, j - 1)
  35.     dfs(board, i, j + 1)
  36. }