# 2022-06-04

## 1091. Shortest Path in Binary Matrix

### Description

Given an `n x n` binary matrix `grid`, return the length of the shortest clear path in the matrix. If there is no clear path, return `-1`.

A clear path in a binary matrix is a path from the top-left cell (i.e., `(0, 0)`) to the bottom-right cell (i.e., `(n - 1, n - 1)`) such that:

• All the visited cells of the path are `0`.

• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

``````Input: grid = [[0,1],[1,0]]
Output: 2``````

Example 2:

``````Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4``````

Example 3:

``````Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1``````

Constraints:

• `n == grid.length`

• `n == grid[i].length`

• `1 <= n <= 100`

• `grid[i][j] is 0 or 1`

### Solution

#### Approach #0

``````var (
dx = []int{-1, -1, -1, 0, 1, 1, 1, 0}
dy = []int{-1, 0, 1, 1, 1, 0, -1, -1}
)

func shortestPathBinaryMatrix(grid [][]int) int {
if grid[0][0] == 1 {
return -1
}
m, n := len(grid), len(grid[0])
if m == 1 && n == 1 && grid[0][0] == 0 {
return 1
}
queue := [][]int{{0, 0}}
depth := 1
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
x, y := queue[i][0], queue[i][1]
for j := 0; j < 8; j++ {
xx, yy := x+dx[j], y+dy[j]
if xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] == 0 {
if xx == m-1 && yy == n-1 {
return depth + 1
}
grid[xx][yy] = 1
queue = append(queue, []int{xx, yy})
}
}
}
queue = queue[size:]
depth += 1
}
return -1
}``````

## 130. Surrounded Regions

### Description

Given an `m x n` matrix `board` containing `'X'` and `'O'`, capture all regions that are 4-directionally surrounded by `'X'`.

A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region.

Example 1:

``````Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.``````

Example 2:

``````Input: board = [["X"]]
Output: [["X"]] ``````

Constraints:

• `m == board.length`

• `n == board[i].length`

• `1 <= m, n <= 200`

• `board[i][j]` is `'X'` or `'O'`.

### Solution

#### Approach #0: BFS

``````var (
dx = []int{0, 1, 0, -1}
dy = []int{1, 0, -1, 0}
)

func solve(board [][]byte) {
m, n := len(board), len(board[0])
var queue [][]int
for i := 0; i < n; i++ {
if board[0][i] != 'X' {
board[0][i] = '-'
queue = append(queue, []int{0, i})
}
if board[m-1][i] != 'X' {
board[m-1][i] = '-'
queue = append(queue, []int{m - 1, i})
}
}
for i := 1; i < m-1; i++ {
if board[i][0] != 'X' {
board[i][0] = '-'
queue = append(queue, []int{i, 0})
}
if board[i][n-1] != 'X' {
board[i][n-1] = '-'
queue = append(queue, []int{i, n - 1})
}
}
for len(queue) > 0 {
x, y := queue[0][0], queue[0][1]
queue = queue[1:]
for i := 0; i < 4; i++ {
xx, yy := x+dx[i], y+dy[i]
if xx >= 0 && xx < m && yy >= 0 && yy < n && board[xx][yy] == 'O' {
queue = append(queue, []int{xx, yy})
board[xx][yy] = '-'
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if board[i][j] == '-' {
board[i][j] = 'O'
} else {
board[i][j] = 'X'
}
}
}
}``````

#### Approach #1: DFS

``````var (
dx = []int{0, 1, 0, -1}
dy = []int{1, 0, -1, 0}
)

func solve(board [][]byte) {
m, n := len(board), len(board[0])
var dfs func(board [][]byte, x, y int)
dfs = func(board [][]byte, x, y int) {
if x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O' {
return
}
board[x][y] = '-'
for i := 0; i < 4; i++ {
xx, yy := x+dx[i], y+dy[i]
dfs(board, xx, yy)
}
}
for i := 0; i < n; i++ {
dfs(board, 0, i)
dfs(board, m-1, i)
}
for i := 1; i < m-1; i++ {
dfs(board, i, 0)
dfs(board, i, n-1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if board[i][j] == '-' {
board[i][j] = 'O'
} else {
board[i][j] = 'X'
}
}
}
}

``````

## 797. All Paths From Source to Target

### Description

Given a directed acyclic graph (DAG) of `n` nodes labeled from `0` to `n - 1`, find all possible paths from node `0` to node `n - 1` and return them in any order.

The graph is given as follows: `graph[i]` is a list of all nodes you can visit from node `i` (i.e., there is a directed edge from node `i` to node `graph[i][j]`).

Example 1:

``````Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.``````

Example 2:

``````Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]``````

Constraints:

• `n == graph.length`

• `2 <= n <= 15`

• `0 <= graph[i][j] < n`

• `graph[i][j] != i` (i.e., there will be no self-loops).

• All the elements of `graph[i]` are unique.

• The input graph is guaranteed to be a DAG.

### Solution

#### Approach #0: DFS

``````func allPathsSourceTarget(graph [][]int) (ans [][]int) {
n:=len(graph)

var dfs func(index int, cur []int)
dfs = func(index int, cur []int) {
cur=append(cur, index)
for _,i:=range graph[index] {
if i+1==n {
c:=make([]int,len(cur))
copy(c,cur)
c=append(c,i)
ans=append(ans,c)
continue
}
dfs(i,cur)
}
}
var cur []int
dfs(0,cur)
return
}``````

#### Approach #1: BFS

``````func allPathsSourceTarget(graph [][]int) (ans [][]int) {
n := len(graph)
queue := [][]int{{0}}
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
l := queue[i]
last := len(l) - 1
if l[last] == n-1 {
a := make([]int, len(l))
copy(a, l)
ans = append(ans, a)
continue
}
for _, e := range graph[l[last]] {
a := make([]int, len(l))
copy(a, l)
a = append(a, e)
queue = append(queue, a)
}
}
queue = queue[size:]
}
return
}``````

Last updated