Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public int numEnclaves(int[][] grid) {
- int n = grid.length;
- int m = grid[0].length;
- int[][] visited = new int[n][m];
- // step-1 check the boundary characters
- // traversing through boundary 0th col, last row, last col, 0th row
- for(int i=0; i<n; i++)
- {
- for(int j=0; j<m; j++)
- {
- // 0th col
- if(grid[i][0] == 1 && visited[i][0] != 1)
- {
- dfs(grid, visited, i, 0, n, m);
- }
- // last col
- else if(grid[i][m-1] == 1 && visited[i][m-1] != 1)
- {
- dfs(grid, visited, i, m-1, n, m);
- }
- // 0th row
- else if(grid[0][j] == 1 && visited[0][j] != 1)
- {
- dfs(grid, visited, 0, j, n, m);
- }
- // last row
- else if(grid[n-1][j] == 1 && visited[n-1][j] != 1)
- {
- dfs(grid, visited, n-1, j, n, m);
- }
- }
- }
- int countLandCells = 0;
- for(int i=0; i<n; i++)
- {
- for(int j=0; j<m; j++)
- {
- if(grid[i][j] == 1)
- countLandCells++;
- // reverting back as we marked 'Y' for temporary purpose
- else if(grid[i][j] == 2)
- grid[i][j] = 1;
- }
- }
- return countLandCells;
- }
- int[] deltaRow = {-1, 1, 0, 0};
- int[] deltaCol = {0, 0, 1, -1};
- public void dfs(int[][] grid, int[][] visited, int row, int col, int n, int m)
- {
- visited[row][col] = 1;
- // Mark this cell as visited and temporary number as 2 to prevent it from being changed
- // as these are boundary land cells
- grid[row][col] = 2;
- for(int i=0; i<4; i++)
- {
- int nRow = row + deltaRow[i];
- int nCol = col + deltaCol[i];
- if(nRow >= 0 && nCol >= 0 && nRow < n && nCol < m)
- {
- // checking if neighbour cell is land cell
- if(visited[nRow][nCol] == 0 && grid[nRow][nCol] == 1)
- {
- dfs(grid, visited, nRow, nCol, n, m);
- }
- }
- }
- }
- }
RAW Paste Data
Copied
