Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- class Pair
- {
- int first;
- int second;
- int step;
- Pair(int first, int second, int step)
- {
- this.first = first;
- this.second = second;
- this.step = step;
- }
- }
- class Solution {
- // similar to Distance of nearest cell having 1
- public void islandsAndTreasure(int[][] grid) {
- ArrayList<ArrayList<Integer>> res = new ArrayList<>();
- int n = grid.length;
- int m = grid[0].length;
- Queue<Pair> q = new LinkedList<>();
- // visited array to mark which all land cells are visited
- boolean[][] visited = new boolean[n][m];
- // distance matrix that will store the nearest distance of 0's from land cells
- int[][] distance = new int[n][m];
- // step-1 adding all those indices into queue where we have as 0's and mark them visited
- for(int i=0; i<n; i++)
- {
- for(int j=0; j<m; j++)
- {
- if(grid[i][j] == 0)
- {
- q.add(new Pair(i,j,0));
- visited[i][j] = true;
- distance[i][j] = 0;
- }
- else if(grid[i][j] == -1)
- distance[i][j] = -1;
- }
- }
- int[] deltaRow = {-1,1,0,0};
- int[] deltaCol = {0,0,1,-1};
- // step-2 traverse the stored indices in queue and check for neighbour 0's
- while(!q.isEmpty())
- {
- Pair pair = q.poll();
- int row = pair.first;
- int col = pair.second;
- int step = pair.step;
- for(int i=0; i<4; i++)
- {
- int nRow = row + deltaRow[i];
- int nCol = col + deltaCol[i];
- if(nRow >=0 && nRow < n && nCol >= 0 && nCol < m)
- {
- // expand to land cells
- if(visited[nRow][nCol] == false && grid[nRow][nCol] == 2147483647)
- {
- q.add(new Pair(nRow, nCol, step+1));
- visited[nRow][nCol] = true;
- distance[nRow][nCol] = step+1;
- }
- }
- }
- }
- for(int i=0; i<n; i++)
- {
- for(int j=0; j<m; j++)
- {
- grid[i][j] = distance[i][j];
- }
- }
- }
- }
RAW Paste Data
Copied
