130. Surrounded Regions

题目

给定一个 m*n 的矩阵 board，这个矩阵由 X 和 O 组成，捕获四个方向都被 X 所包围的区域。
捕获的方式是将被包围的区域填充成 X。

image.png

解析

如何判断一块区域是否被 x包围。

1. 如果 O 出现在最外一圈，则该区域以及与该区域相连的任何区域都不可能被包围。
   基于此，按照一般顺序遍历某一个区域是否可以被覆盖。先假设该区域可以被覆盖，最终该区域是否可以被覆盖，要看其领接区域是否可以被覆盖。即
   f((x,y)) = notboarder((x,y)) & f((x-1, y)) & f((x, y-1)) & f(x+1, y) & f(x, y+1)

这里有一个特殊情况，当某一个区域被标记为不可包围时，首先将其标记为 N，这样方便后续判断直接跳过。

伪代码

for x<row
  for y<col
    if f(board, x,y)
      board[x,y] = X

f(board, x ,y) surd

if board[x,y] == 'X'
  return true
if board[x,y] == 'O' && (x == 0 || x == row || y == 0 || y = col)
  csetN(board, x,y)
  return false
board[x,y] = 'X'
if ! f(board, x-1,y) && f(board, x, y-1) &&f (board, x+1, y) && f(board, x, y+1)
 board[x,y] = 'N'
 return false

代码

上边思路是错的，解不出来

看别人的解法

正解

一块区域是否被包围，取决于这块区域是否和最外层的 O 连通。所以只需要将和最外层 O 连通的 O 保持不变，然后将未和最外层 O 连通的单元 置为 X 即可。
为了保证不混淆
(1)将最外层 O 置为 N
(2)将和 N 连接的O 置为 N
(3)重新遍历矩阵，将 O 置为 X，将 N置为 O

for j<col
  setn(board, 0, j)
  setn(board, row,j)
for i<row
  setn(board, i, 0)
  setn(board, i, 1)

for i<row
  for j<col
    if board[x][y] == 'N'
      board[x][y] = 'O'
      continue
    if board[x][y] == 'O'
      board[x][y] = 'X'

setn(board, x , y)

if x<0 || x>row || y < 0 || y > col
  return
if board[x][y] != 'O'
  return
board[x][y] = 'N'
setn(board, x+1, y)
setn(board, x-1, y)
setn(board, x, y+1)
setn(board, x, y-1)

代码

func solve(board [][]byte)  {
    row := len(board) - 1
    col := len(board[0]) -1
    
    for y:=0; y<=col; y++ {
        setn(board, 0, y)
        setn(board, row, y)
    }
    
    for x:=0; x<=row; x++ {
        setn(board, x, 0)
        setn(board, x, col)
    }
    
    for x:=0; x<=row; x++{
        for y:=0; y<=col; y++ {
            if board[x][y] == 'N' {
                board[x][y] = 'O'
                continue
            }
            if board[x][y] == 'O' {
                board[x][y] = 'X'
            }
        }
    }
}


func setn(board [][]byte , x int, y int) {
    row := len(board) - 1
    col := len(board[0]) - 1
    if x < 0 || y < 0 || x > row || y > col {
        return
    }
    if board[x][y] != 'O' {
        return 
    }
    board[x][y] = 'N'
    setn(board, x-1, y)
    setn(board, x+1, y)
    setn(board, x, y-1)
    setn(board, x, y+1)
}

image.png