130. Окруженные регионы

Stanislav Gumeniuk включен в Leetcode Leetcode-Problem

2020-06-17 294 слов 2 минуты

Содержание

Автоматический перевод

Эта статья переведена автоматически с английский на русский. Оригинал доступен на английский.

Задача

Дана двумерная доска, содержащая символы ‘X’ и ‘O’ (буква O), захватите все регионы, окруженные ‘X’.

Регион захватывается путем замены всех ‘O’ на ‘X’ в этом окруженном регионе.

Пример 1

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 (Поиск в глубину)

func solve(board [][]byte) {
	a := make([][]int, len(board))
	for idx := range board {
		a[idx] = make([]int, len(board[idx]))
	}

	for idx := range board {
		if idx == 0 || idx == len(board)-1 {
			for jdx := range board[idx] {
				if board[idx][jdx] == 'O' && a[idx][jdx] == 0 {
					visit(board, a, idx, jdx)
				}
			}
		} else {
			jdx := 0
			if board[idx][jdx] == 'O' && a[idx][jdx] == 0 {
				visit(board, a, idx, jdx)
			}
			jdx = len(board[idx]) - 1
			if board[idx][jdx] == 'O' && a[idx][jdx] == 0 {
				visit(board, a, idx, jdx)
			}

		}

	}

	for idx := range board {
		for jdx := range board[idx] {
			if a[idx][jdx] != 1 {
				board[idx][jdx] = 'X'
			}
		}
	}

}

func visit(board [][]byte, a [][]int, i, j int) {
	a[i][j] = 1

	if j+1 < len(board[i]) && board[i][j+1] == 'O' && a[i][j+1] == 0 {
		visit(board, a, i, j+1)
	}
	if j-1 >= 0 && board[i][j-1] == 'O' && a[i][j-1] == 0 {
		visit(board, a, i, j-1)
	}

	if i+1 < len(board) && board[i+1][j] == 'O' && a[i+1][j] == 0 {
		visit(board, a, i+1, j)
	}
	if i-1 >= 0 && board[i-1][j] == 'O' && a[i-1][j] == 0 {
		visit(board, a, i-1, j)
	}
}