Topic describes

This is “1162. Map Analysis” on Leetcode, and the difficulty is “Medium.”

You now have a grid of size 0 and each cell on it is marked with and.

Where represents the ocean, represents the land, please find an ocean cell, this ocean cell to its nearest land cell is the largest distance.

The distance we’re talking about here is the Manhattan distance: the distance between these two cells.

If there is only land or sea on the grid, go back.

Example 1:

Input: [[1,0,1],[0,0, 1]] Output: 2 Explanation: The distance between the ocean cell (1, 1) and all the land cells is maximized, with a maximum distance of 2.

Example 2:

Input: [[1,0,0],[0,0,0]] Output: 4 Explanation: The distance between the ocean cell (2, 2) and all the land cells is maximized, with a maximum distance of 4.

Tip:

  • 1 <= grid.length == grid[0].length <= 100
  • Grid [I][j

Monophyletic BFS

Usually, we use BFS to find the shortest circuit, which is aimed at the following scenario: starting from a specific starting point, find the shortest distance to a specific end point.

This is a special kind of “single source shortest circuit” problem, which is essentially to find the shortest path from a specific “source point” to a specific “junction point” on a graph with edge weight of.

For this problem, using the “single source shortest circuit” approach, we need to do a BFS for each “ocean” position: find the nearest land distance of each “ocean”, and then take all the distances as the answer.

The worst-case scenario of a single BFS requires the entire matrix to be scanned with a complexity of.

At the same time, at most one area of the ocean needs to be BFS, so this approach has a complexity of, and can be filled directly.

PS. The data range is, theoretically, there must be a timeout, but this problem data is weak, Java 2021/06/28 can pass.

Some details: For convenience, when using the hash table to record the distance, we converted the two-dimensional coordinates into the corresponding one-dimensional subscript and stored it as the key.

Code:

class Solution { int n; int[][] grid; public int maxDistance(int[][] _grid) { grid = _grid; n = grid.length; int ans = -1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 0) { ans = Math.max(ans, bfs(i, j)); } } } return ans; } / / single BFS: solving the sea position (x, y) the nearest land distance int BFS (int x, int y) {int [] [] dirs = new int [] [] {{1, 0}, {1, 0}, {0, 1}, {0, 1}}; Deque<int[]> d = new ArrayDeque<>(); Map<Integer, Integer> map = new HashMap<>(); d.addLast(new int[]{x, y}); map.put(x * n + y, 0); while (! d.isEmpty()) { int[] poll = d.pollFirst(); int dx = poll[0], dy = poll[1]; int step = map.get(dx * n + dy); if (grid[dx][dy] == 1) return step; for (int[] di : dirs) { int nx = dx + di[0], ny = dy + di[1]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; int key = nx * n + ny; if (map.containsKey(key)) continue; d.addLast(new int[]{nx, ny}); map.put(key, step + 1); } } return -1; }}
  • Time complexity:
  • Space complexity:

Multi-source BFS

This is actually an introduction to multi-source BFS.

Different from the “single source shortest”, the “multi-source shortest” problem is to find the shortest path from “multiple source points” to “one or more sinks”.

In terms of implementation, the core part of the search, “multi-source BFS” is no different from “single-source BFS.”

And by establishing “virtual source points,” we can turn the “multi-source BFS” problem back into the “single-source BFS” problem.

What do you mean?

In our case, the problem asks us to find the maximum value from each “ocean” area to the nearest “land” area.

We can invert the “source/origin” and “terminal/end” : starting from each “land” area, multiple “land” areas simultaneously spread one circle at a time, and each “ocean” area is first covered by the corresponding number of turns, is the distance of the “ocean” area from the nearest “land” area.

But how does this relate to “single-source BFS”?

We can imagine the existence of a “virtual source point” with edges equal to all “real source points” (land), then the shortest circuit between any “ocean” region and the “nearest land” region is equivalent to the shortest circuit with the “virtual source point” :

In the implementation, we don’t need to actually create the virtual source point, we just need to enqueue all the “real source points” before BFS.

This process is equivalent to popping the “virtual source point” from the queue, enqueuing the point it can reach (the real source point), and then doing regular BFS.

Some details: ImplementationFor convenience, when performing regular BFS, if an “ocean” area is accessed, it is covered by the “nearest land” to it, change the value to the minimum distance. This way we only need to consider the “ocean” areas where the value is still equal (representing areas that have not been updated).

Code:

class Solution { public int maxDistance(int[][] grid) { int n = grid.length; Deque<int[]> d = new ArrayDeque<>(); Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { d.add(new int[]{i, j}); map.put(i * n + j, 0); } } } int ans = -1; Int [] [] dirs = new int [] [] {{1, 0}, {1, 0}, {0, 1}, {0, 1}}; while (! d.isEmpty()) { int[] poll = d.poll(); int dx = poll[0], dy = poll[1]; int step = map.get(dx * n + dy); for (int[] di : dirs) { int nx = dx + di[0], ny = dy + di[1]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (grid[nx][ny] ! = 0) continue; grid[nx][ny] = step + 1; d.add(new int[]{nx, ny}); map.put(nx * n + ny, step + 1); ans = Math.max(ans, step + 1); } } return ans; }}
  • Time complexity:
  • Space complexity:

conclusion

Today we introduced the “multi-source BFS” problem, which we can turn back into the “single-source BFS” problem by creating “virtual source points.”

All we need to do is enqueue all the “real source points” and then BFS.

It seems that there is not much difference between the two, but its essence is that the conventional Flood Fill is used to transform multiple simple BFS into one BFS through the source/terminal conversion, which can effectively reduce the time complexity of our algorithm.

The last

This is the No.1162 of our series “Spawn through LeetCode”. The series started on January 01, 2012, and as of the start date there were 1,916 questions on LeetCode.

In this series of articles, in addition to explaining how to solve the problem, I will present the most concise code possible. If the general solution is involved, there will be a corresponding code template.

In order to facilitate the classmate can carry on the debugging and submit code on a computer, I established the relevant warehouse: https://github.com/SharingSou… .

In the repository address, you’ll find links to the series’ solutions, the code for the series, links to the original LeetCode problems, and other preferred solutions.