Posted onEdited onInLeetcode
,
MediumViews: Valine: Symbols count in article: 9.3kReading time ≈8 mins.
Description
Difficulty: Medium
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:
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Explanations:
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.
翻评论区发现这里面蕴藏了一个有名有姓的算法： Depth first search / Tiefensuche / 深度优先搜索
The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
classSolution{ publicvoidsolve(char[][] board){ int a = board.length; if(a == 0){ return; } int b = board[0].length; if(b == 0){ return; } for(int i=0; i<a;i++){ //left top to left down if(board[i][0] == 'O'){ board[i][0] = 'A'; change(board, i, 0, a, b); } } for(int i=0; i<a;i++){ //right top to right down if(board[i][b-1] == 'O'){ board[i][b-1] = 'A'; change(board, i, b-1, a, b); } } for(int j=0; j<b;j++){ //up left to up right if(board[0][j] == 'O'){ board[0][j] = 'A'; change(board, 0, j, a, b); } } for(int j=0; j<b;j++){ //down left to down right if(board[a-1][j] == 'O'){ board[a-1][j] = 'A'; change(board, a-1, j, a, b); } } for(int i=1; i<a-1; i++){ //change all 'O' left (means they are surround by 'X') to 'X' for(int j=1; j<b-1; j++){ if(board[i][j] == 'O'){ board[i][j] = 'X'; } } } for(int i=0; i<a; i++){ //change all 'A' to 'O' for(int j=0; j<b; j++){ if(board[i][j] == 'A'){ board[i][j] = 'O'; } } } } publicvoidchange(char[][] board, int i, int j, int a, int b){ if(i-1>=0 && board[i-1][j] == 'O'){//Up board[i-1][j] = 'A'; change(board, i-1, j, a, b); } if(i+1<a-1 && board[i+1][j] == 'O'){//down board[i+1][j] = 'A'; change(board, i+1, j, a, b); } if(j+1<b-1 && board[i][j+1] == 'O' ){//right board[i][j+1] = 'A'; change(board, i, j+1, a, b); } if(j-1>=0 && board[i][j-1] == 'O'){//left board[i][j-1] = 'A'; change(board, i, j-1, a, b); } } }
It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’[1]), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
两者的区别：
感觉一般DFS更常用一些（通过递归很容易挖深度），BFS就要借助 queue (FIFO)/deque/vector (C++: Standard Template Library STL：Sequential Container）或者Queue/LinkedList/ArrayDeque（Java）。找到一个'O'后直接找上下左右并存在Container里面，下面是整合的C++ queue版本:
voidsolve(vector<vector<char&board){ // the same as DFS int width = board.size(); if (width == 0) //Add this to prevent run-time error! return; int length = board[0].size(); if (length == 0) // Add this to prevent run-time error! return; for (int i = 0; i < length; ++i){ if (board[0][i] == 'O') bfsBoundary(board, 0, i); if (board[width-1][i] == 'O') bfsBoundary(board, width-1, i); } for (int i = 0; i < width; ++i){ if (board[i][0] == 'O') bfsBoundary(board, i, 0); if (board[i][length-1] == 'O') bfsBoundary(board, i, length-1); } for (int i = 0; i < width; ++i){ for (int j = 0; j < length; ++j){ if (board[i][j] == 'O') board[i][j] = 'X'; elseif (board[i][j] == '#') board[i][j] = 'O'; } } }
voidBFS(vector<vector<char>&board, int i, int j){ int m = board.size(); int n = board[0].size(); queue<pair<int, intq; q.push(make_pair(i, j)); while (!q.empty()) { pair<int, intelem = q.front(); //oldest element q.pop(); //delete the oldest element i = elem.first; j = elem.second; if (i >= 0 && i < m && j >=0 && j < n && board[i][j] == 'O') { board[i][j] = '#'; q.push(make_pair(i - 1, j)); //down q.push(make_pair(i + 1, j)); //up q.push(make_pair(i, j - 1)); //left q.push(make_pair(i, j + 1)); //right } } }
由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于创建单元素集合。有了这些方法，许多经典的划分问题可以被解决。 为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find(x) 返回 x 所属集合的代表，而 Union 使用两个集合的代表作为参数。