https://leetcode.com/problems/surrounded-regions/
Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
Example:1
2
3
4X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:1
2
3
4X X X X
X X X X
X X X X
X O X X
Explanation:
Surrounded regions shouldn’t 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.
Traversal of 2D grid, DFS1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80// class Pair<U, V> {
// public U first;
// public V second;
// public Pair(U first, V second) {
// this.first = first;
// this.second = second;
// }
// }
class Solution {
private int ROW=0;
private int COL=0;
public void solve(char[][] board) {
if(board==null||board.length==0) return;
this.ROW=board.length;
this.COL=board[0].length;
// Step 1). construct the list of border cells
List<Integer[]> borders=new LinkedList<>();
for(int r=0;r<this.ROW;r++){
borders.add(new Integer[]{r,0});
borders.add(new Integer[]{r,this.COL-1});
}
for(int c=0;c<this.COL;c++){
borders.add(new Integer[]{0,c});
borders.add(new Integer[]{this.ROW-1,c});
}
// Step 2). mark the escaped cells
for(Integer[] pair:borders) DFS(board,pair[0],pair[1]);
// Step 3). flip the cells to their correct final states
for(int r=0;r<this.ROW;r++){
for(int c=0;c<this.COL;c++){
if(board[r][c]=='O') board[r][c]='X';
if(board[r][c]=='E') board[r][c]='O';
}
}
}
private void DFS(char[][] board,int row,int col){
if(row<0||row>=ROW||col<0||col>=COL||board[row][col]!='O') return;
board[row][col] = 'E';
int[][] d={{0,1},{1,0},{0,-1},{-1,0}};
for(int[] i:d) DFS(board,row+i[0],col+i[1]);
// DFS(board,row-1,col);
// DFS(board,row+1,col);
// DFS(board,row,col-1);
// DFS(board,row,col+1);
}
//-----------------------------------------------------------------------------
private void BFS(char[][] board,int row,int col){
LinkedList<Integer[]> queue=new LinkedList<>();
queue.offer(new Integer[]{row,col});
while(!queue.isEmpty()){
Integer[] pair=queue.poll();
int r=pair[0],c=pair[1];
if(board[r][c]!='O') continue;
board[r][c]='E';
if(c<this.COL-1) queue.offer(new Integer[]{r,c+1});
if(c>0) queue.offer(new Integer[]{r,c-1});
if(r<this.ROW-1) queue.offer(new Integer[]{r+1,c});
if(r>0) queue.offer(new Integer[]{r-1,c});
}
}
private void DFS_Iteration(char[][] board,int row,int col){
LinkedList<Integer[]> queue=new LinkedList<>();
queue.push(new Integer[]{row,col});
while(!queue.isEmpty()){
Integer[] pair=queue.pop();
int r=pair[0],c=pair[1];
if(board[r][c]!='O') continue;
board[r][c]='E';
if(c<this.COL-1) queue.offer(new Integer[]{r,c+1});
if(c>0) queue.offer(new Integer[]{r,c-1});
if(r<this.ROW-1) queue.offer(new Integer[]{r+1,c});
if(r>0) queue.offer(new Integer[]{r-1,c});
}
}
}
From BFS to DFS
In the above implementation of BFS, the fun part is that we could easily convert the BFS strategy to DFS by changing one single line of code. And the obtained DFS implementation is done in iteration, instead of recursion.
The key is that instead of using the queue data structure which follows the principle of FIFO (First-In First-Out), if we use the stack data structure which follows the principle of LIFO (Last-In First-Out), we then switch the strategy from BFS to DFS.
Specifically, at the moment we pop an element from the queue, instead of popping out the head element, we pop the tail element, which then changes the behavior of the container from queue to stack. Here is how it looks like.