LeetCode 1162. Map analysis

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:

  1. Use a priority queue to join first on all land (1);
  2. while handles the priority queue, encounters an ocean (0) that covers the ocean with a land value of + 1 and enlists it;
  3. 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;
	}
}

Tags: Java github Programming network

Posted on Sun, 29 Mar 2020 10:18:28 -0700 by tsilenzio