## My LeetCode: https://leetcode-cn.com/u/ituring/

## My LeetCode brush Title source [GitHub]: https://github.com/izhoujie/Algorithmcii

## LeetCode 1162. Map analysis

# subject

You now have a Map (Grid) grid of size N x N on which each Zone (Cell) is marked with 0 and 1.Among them, 0 represents the ocean and 1 represents the land. Do you know which ocean area is farthest from the land area?Please return to the distance of the ocean to the nearest land area.

The distance we are talking about here is Manhattan Distance: (x0, y0) and (x1, y1) The distance between these two areas is |x0 - x1| + |y0 - y1|.

If we only have land or oceans on our map, go back to -1.

Example 1:

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

Example 2:

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

Tips:

- 1 <= grid.length == grid[0].length <= 100
- grid[i][j] is either 0 or 1

Source: LeetCode

Links: https://leetcode-cn.com/problems/as-far-from-land-as-possible

Copyright shall be owned by the withholding network.For commercial reprinting, please contact the official authorization. For non-commercial reprinting, please indicate the source.

## Solving problems

First of all, I can understand the meaning of the topic. I think it's already amazing... At least I haven't understood it for half a day at first - ||

The first idea for this kind of problem is BFS, DFS and so on. This problem can be solved by BFS and DFS. BFS is easier to understand and understand.

There is also a dynamic programming solution that is not easy to understand, but the code is simpler and most efficient.

### Ideas 1-BFS

Steps:

- Use a priority queue to join first on all land (1);
- while handles the priority queue, encounters an ocean (0) that covers the ocean with a land value of + 1 and enlists it;
- At the end of the while cycle, the last ocean block processed is the farthest distance, and its array value of -1 is sufficient.

BFS: Comparing images means water circle, the meaning of surrounding a city in the countryside

DFB: Guan Gong's Wine Chops Huaxiong, Walks thousands of miles on a single ride, My own image memory of DFS

### Idea 2-dp Dynamic Planning

1-Traverse from upper left corner to lower right corner first;

2-Traversal from the lower right corner to the upper left corner;

Details: To be added...

## Sample algorithm source

package leetcode; import java.util.ArrayDeque; /** * @author ZhouJie * @date 2020 March 29, 2000 9:45:11 p.m. * @Description: 1162. Map Analysis * */ public class LeetCode_1162 { } class Solution_1162 { /** * @author: ZhouJie * @date: 2020 March 29, 2003 11:31:43 p.m. * @param: @param grid * @param: @return * @return: int * @Description: 1-BFS，All land acts as the starting point, begins to diffuse, and uses a priority queue; * */ public int maxDistance_1(int[][] grid) { ArrayDeque<int[]> deque = new ArrayDeque<int[]>(); int m = grid.length; int n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { deque.offer(new int[] { i, j }); } } } int[] last = null; boolean noSea = true; // Four search directions int[] dx = new int[] { 1, -1, 0, 0 }; int[] dy = new int[] { 0, 0, 1, -1 }; while (!deque.isEmpty()) { last = deque.poll(); int x0 = last[0]; int y0 = last[1]; for (int i = 0; i < 4; i++) { int x = x0 + dx[i]; int y = y0 + dy[i]; if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 0) { continue; } grid[x][y] = grid[x0][y0] + 1; noSea = false; deque.offer(new int[] { x, y }); } } return noSea || last == null ? -1 : grid[last[0]][last[1]] - 1; } /** * @author: ZhouJie * @date: 2020 March 29, 2000 11:31:40 p.m. * @param: @param grid * @param: @return * @return: int * @Description: 2-Dynamic programming, based on the concept of Manhattan distance, that is, distance is always the sum of distance up-front and left-front, or under-front and right-front. * The grid is dp twice, once from the upper left corner to the lower right corner and once from the lower right corner to the upper left corner. * */ public int maxDistance_2(int[][] grid) { int m = grid.length; int n = grid[0].length; boolean noLand = true; // dp from upper left to lower right, marked with noLand for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { noLand = false; continue; } if (grid[i][j] == 0) { grid[i][j] = m + n; } if (i > 0) { grid[i][j] = Math.min(grid[i][j], grid[i - 1][j] + 1); } if (j > 0) { grid[i][j] = Math.min(grid[i][j], grid[i][j - 1] + 1); } } } int distance = 0; // dp from bottom right to top left, calculating distance for (int i = m - 1; i > -1; i--) { for (int j = n - 1; j > -1; j--) { if (grid[i][j] != 1) { if (i < m - 1) { grid[i][j] = Math.min(grid[i][j], grid[i + 1][j] + 1); } if (j < n - 1) { grid[i][j] = Math.min(grid[i][j], grid[i][j + 1] + 1); } distance = Math.max(distance, grid[i][j]); } } } return noLand ? -1 : --distance; } }