The title
Analysis of the
Note: The algorithm introduced below, in addition to the search set, DFS and BFS are very basic algorithm content, is also very easy to understand, writing is relatively fixed, readers need to write more, find and record their own problems, I also wrote several times or even in the process of writing the solution of this problem, found their own problems.
This problem can be solved using a classic algorithm called Flood fill, as defined below from Wikipedia.
Flood Fill algorithm is a classical algorithm that extracts several connected points from a region and separates them from other adjacent regions (or dyes them into different colors). It gets its name from the idea that a flood spreads from one area to all it can reach. In GNU Go and Minesweeping, the Flood Fill algorithm is used to calculate areas that need to be cleared.
“Flood” I looked it up. As a verb it is “to Flood; “Full of” means “flood” as a noun. Here’s a brief explanation of the algorithm:
- A number of connected points are extracted from an area to distinguish it from other adjacent areas
Spread out from a point, find the points that connect to it, it’s not a sophisticated algorithm, it’s really a depth-first walk from a point, do a depth-first walk, or a breadth-first walk, find a contiguous area, and for this problem, The idea is to do a depth-first or breadth-first walk, starting with a “land” cell and marking all the adjacent cells as if an “island” had been found.
Note: “marked” here means that through depth-first or breadth-first traversal, I find a new cell that is connected to the starting cell and is considered “marked” or “visited.”
Then the conditions for each “depth-first traverse” or “breadth-first traverse” are:
1, this grid is land 1, if it is water 0, there is no way to talk about “island”;
2, the grid before can’t be found in the process of the “island” performed “depth-first traversal” or “breadth-first traversal” operation, and the marked grid (the other words too man, you can figure, not knowing is not your problem, is my expression problem, directly see code will clear a lot).
Method 1: Depth-first traversal
The illustration
Code implementation 1:
/** * depth-first traversal */
public class Solution {
// x-1,y
// x,y-1 x,y x,y+1
// x+1,y
// Directions array, which represents the offset of the horizontal and vertical coordinates relative to the current position in four directions. This is a common trick. On the lower left to the right
private static final int[][] directions = {{-1.0}, {0, -1}, {1.0}, {0.1}};
// Mark an array that marks whether the coordinates of the grid have been accessed
private boolean[][] marked;
// The number of rows in the grid
private int rows;
// The number of columns in the grid
private int cols;
private char[][] grid;
public int numIslands(char[][] grid) {
rows = grid.length;
if (rows == 0) {
return 0;
}
cols = grid[0].length;
this.grid = grid;
marked = new boolean[rows][cols];
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// If it is a point in an island and has not been visited
// perform depth-first traversal
if(! marked[i][j] && grid[i][j] =='1') { count++; dfs(i, j); }}}return count;
}
// Depth-first traversal starts at coordinates (I,j)
private void dfs(int i, int j) {
marked[i][j] = true;
// Get the coordinates of the four directions
for (int k = 0; k < 4; k++) {
int newX = i + directions[k][0];
int newY = j + directions[k][1];
// If not out of bounds, unvisited, and on land
if (inArea(newX, newY) && grid[newX][newY] == '1'&&! marked[newX][newY]) { dfs(newX, newY); }}}// Encapsulate the inArea method to make the semantics clearer
private boolean inArea(int x, int y) {
// Don't forget the equal sign
return x >= 0 && x < rows && y >= 0 && y < cols;
}
public static void main(String[] args) {
Solution solution = new Solution();
char[][] grid1 = {
{'1'.'1'.'1'.'1'.'0'},
{'1'.'1'.'0'.'1'.'0'},
{'1'.'1'.'0'.'0'.'0'},
{'0'.'0'.'0'.'0'.'0'}};
int numIslands1 = solution.numIslands(grid1);
System.out.println(numIslands1);
char[][] grid2 = {
{'1'.'1'.'0'.'0'.'0'},
{'1'.'1'.'0'.'0'.'0'},
{'0'.'0'.'1'.'0'.'0'},
{'0'.'0'.'0'.'1'.'1'}};
intnumIslands2 = solution.numIslands(grid2); System.out.println(numIslands2); }}Copy the codeCode implementation 2:
class Solution {
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') { ++num_islands; dfs(grid, r, c); }}}returnnum_islands; }}Copy the codeComplexity analysis
- Time complexity: O(MN), where M and N are the number of rows and columns respectively.
- Spatial complexity: O(MN), in the worst case, the entire grid is land, depth first search depth up to MN.
Method two: breadth-first traversal
In addition to depth-first traversal, you can also use breadth-first traversal, where you don’t have to backtrack. Breadth-first traversal requires a secondary queue.
The illustration
import java.util.LinkedList;
/** * method 2: breadth-first traversal */
public class Solution2 {
private int rows;
private int cols;
public int numIslands(char[][] grid) {
// x-1,y
// x,y-1 x,y x,y+1
// x+1,y
int[][] directions = {{-1.0}, {0, -1}, {1.0}, {0.1}};
rows = grid.length;
if (rows == 0) {
return 0;
}
cols = grid[0].length;
boolean[][] marked = new boolean[rows][cols];
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// If it is a point in an island and has not been visited
// start breadth-first traversal at coordinates (I,j)
if(! marked[i][j] && grid[i][j] =='1') {
count++;
LinkedList<Integer> queue = new LinkedList<>();
// Tip: convert coordinates to a number
// Otherwise, use an array. In Python, use a tuple
queue.addLast(i * cols + j);
// Note: this should be marked as accessed
marked[i][j] = true;
while(! queue.isEmpty()) {int cur = queue.removeFirst();
int curX = cur / cols;
int curY = cur % cols;
// Get the coordinates of the four directions
for (int k = 0; k < 4; k++) {
int newX = curX + directions[k][0];
int newY = curY + directions[k][1];
// If it's not out of bounds, not visited, and still land, I continue to queue, remembering that the tag has already been visited
if (inArea(newX, newY) && grid[newX][newY] == '1' && !marked[newX][newY]) {
queue.addLast(newX * cols + newY);
// When queued, mark it as visited immediately. The semantics are clear: once queued, you will traverse it sooner or later
// Instead of marking the queue when it exits
// [special attention] If you do not write this sentence correctly, the code will time out seriously
marked[newX][newY] = true;
}
}
}
}
}
}
return count;
}
private boolean inArea(int x, int y) {
// Don't forget the details
return x >= 0 && x < rows && y >= 0 && y < cols;
}
public static void main(String[] args) {
Solution2 solution2 = new Solution2();
char[][] grid1 = {
{'1'.'1'.'1'.'1'.'0'},
{'1'.'1'.'0'.'1'.'0'},
{'1'.'1'.'0'.'0'.'0'},
{'0'.'0'.'0'.'0'.'0'}};
int numIslands1 = solution2.numIslands(grid1);
System.out.println(numIslands1);
char[][] grid2 = {
{'1'.'1'.'0'.'0'.'0'},
{'1'.'1'.'0'.'0'.'0'},
{'0'.'0'.'1'.'0'.'0'},
{'0'.'0'.'0'.'1'.'1'}};
intnumIslands2 = solution2.numIslands(grid2); System.out.println(numIslands2); }}Copy the codeCode implementation 4:
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if(! nr)return 0;
int nc = grid[0].size();
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0';
queue<pair<int.int>> neighbors;
neighbors.push({r, c});
while(! neighbors.empty()) { auto rc = neighbors.front(); neighbors.pop();int row = rc.first, col = rc.second;
if (row - 1> =0 && grid[row-1][col] == '1') {
neighbors.push({row-1, col});
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.push({row+1, col});
grid[row+1][col] = '0';
}
if (col - 1> =0 && grid[row][col-1] = ='1') {
neighbors.push({row, col-1});
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] = ='1') {
neighbors.push({row, col+1});
grid[row][col+1] = '0';
}
}
}
}
}
returnnum_islands; }};Copy the codeComplexity analysis
- Time complexity: O(MN), where MMAnd N are the number of rows and columns, respectively.
- Spatial complexity: O(min (M,N)) O(\min(M, N)) O(min(M,N)), in the worst case, the entire grid is land and the queue size can reach $\min(M, N)$.
Method three: Use and look up sets
The idea behind using look-up sets to solve this problem is simple:
1. If it is “land”, try merging with your surroundings.
2. If the current is a “body of water”, I merge all the “bodies of water” together. For this purpose, I set up a virtual node that means “all the bodies of water are connected to this virtual node”.
Note:
1. For point 1 above: If the current is “land”, try to merge with the surrounding “, in this case “surrounding” does not need to be “depth first” and “breadth first”, the direction is all around. In fact, just go “right” and “down”, for the simple reason that you can imagine a “4” and “2” algorithm execution flow in your head (or watch the animation I show below) and you can see that “4” is not necessary;
2. For the second point above: since I set “virtual node”, when I returned “number of islands”, it should be the number of connected components -1. Do not forget to remove the “water area” component represented by “virtual node”, and the remaining number of connected components is “number of islands”.
The illustration
Code implementation 5:
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) - >int:
class UnionFind:
def __init__(self, n) :
self.count = n
self.parent = [i for i in range(n)]
self.rank = [1 for _ in range(n)]
def get_count(self) :
return self.count
def find(self, p) :
whilep ! = self.parent[p]: self.parent[p] = self.parent[self.parent[p]] p = self.parent[p]return p
def is_connected(self, p, q) :
return self.find(p) == self.find(q)
def union(self, p, q) :
p_root = self.find(p)
q_root = self.find(q)
if p_root == q_root:
return
if self.rank[p_root] > self.rank[q_root]:
self.parent[q_root] = p_root
elif self.rank[p_root] < self.rank[q_root]:
self.parent[p_root] = q_root
else:
self.parent[q_root] = p_root
self.rank[p_root] += 1
self.count -= 1
row = len(grid)
#, sentenced to
if row == 0:
return 0
col = len(grid[0])
def get_index(x, y) :
return x * col + y
# Note: We don't have to try all four directions like DFS and BFS, just look to the right and below
directions = [(1.0), (0.1)]
# Open up one more space and assign water "0" to this virtual boss
dummy_node = row * col
# The extra space is the virtual space
uf = UnionFind(dummy_node + 1)
for i in range(row):
for j in range(col):
# If it's water, connect to that virtual space
if grid[i][j] == '0':
uf.union(get_index(i, j), dummy_node)
if grid[i][j] == '1':
# down to the right if they're both land, that's "1", they're going to merge
for direction in directions:
new_x = i + direction[0]
new_y = j + direction[1]
if new_x < row and new_y < col and grid[new_x][new_y] == '1':
uf.union(get_index(i, j), get_index(new_x, new_y))
Don't forget to subtract the virtual node
return uf.get_count() - 1
if __name__ == '__main__':
grid = [['1'.'1'.'1'.'1'.'0'],
['1'.'1'.'0'.'1'.'0'],
['1'.'1'.'0'.'0'.'0'],
['0'.'0'.'0'.'0'.'0']]
solution = Solution()
result = solution.numIslands(grid)
print(result)
Copy the codeThere’s one caveat here: You can fix this problem without creating marked arrays, but there are a few things you should know.
- For the input of the algorithm, a lot of times you don’t mind modifying the input, unless you’re being asked to modify the input;
- moreover
markedArrays don’t have to save this space, space is getting less and less valuable now, and it can be reclaimed when the program is done. When we write algorithms, we should strive for optimal time complexity and readable code.