source: https://leetcode.com/problems/as-far-from-land-as-possible/description/
As Far from Land as Possible
Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.
The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 – x1| + |y0 – y1|.
Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
class Solution { public int maxDistance(int[][] grid) { int n = grid.length; Queue<int[]> next = new LinkedList<>(); Set<String> visited = new HashSet<>(); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==1){ int[] t= new int[]{i, j}; visited.add(i+":"+j); next.offer(t); } } } int[] x = {0, 0, 1, -1}; int[] y = {1, -1, 0, 0}; int level = 0; //perform bfs while(!next.isEmpty()){ int size = next.size(); for(int i=0;i<size;i++){ int[] pos = next.poll(); //update the distance of the current cell from th nearest land grid[pos[0]][pos[1]] = grid[pos[0]][pos[1]] + level; //check adjacent cells for(int k=0;k<x.length;k++){ int r = pos[0] + x[k]; int c = pos[1] + y[k]; //if it is not visited yet and is water if(isValid(grid, r, c, visited)){ int[] t = new int[]{r, c}; visited.add(r+":"+c); next.add(t); } } } level++; } return level-1>0?level-1:-1; } private boolean isValid(int[][] grid, int r, int c, Set<String> visited){ return r>=0 && r<grid.length && c>=0 && c<grid[0].length && grid[r][c]==0 && !visited.contains(r+":"+c); } } |