X Total Shapes Solution Java

X Total Shapes Solution Java

  March 06, 2021    

---

Idea is to use DFS and count one DFS iteration as a connected Xs

 

 Code:

  int dir[][] = {{0,1},{0,-1},{1,0},{-1,0}};
    public int xShape(char[][] grid)
    {
        int n =grid.length;
        int m = grid[0].length;
        int count = 0;
        boolean visited[][] = new boolean[n][m];
        for(int i=0;i<n;++i) {
            for(int j=0;j<m;++j){
                if(!visited[i][j] && grid[i][j] == 'X')
                {
                   ++count;
                   markNeighboursVisited(grid, i, j, n, m, visited);
                }
            }
        }
        return count;
    }
    public void markNeighboursVisited(char grid[][], int i, int j, int n,
    int m, boolean visited[][]) {
        visited[i][j] = true;
        for(int itr=0;itr<4;++itr) {
            int nextI = i+dir[itr][0];
            int nextJ = j+dir[itr][1];
            if(isSafeToMove(nextI, nextJ, n, m, visited) && grid[i][j] =='X') {
                markNeighboursVisited(grid, nextI, nextJ, n, m, visited);
            }
        }
    }
    boolean isSafeToMove(int i, int j, int n, int m, boolean visited[][]) {
        if(i<0 || j<0 || i>=n || j>=m || visited[i][j]) return false;
        return true;
    }