A 2D array, m, is an n x n matrix where each cell contains either the value 0 or

Question

A 2D array, m, is an n x n matrix where each cell contains either the value 0 or the value 1. Any two cells (x1, y 1 and (x2 y2) in m fall into the same group if x1-x2l Ly1-y2l 1 and both cells contain the value 1 Complete the countGroups function in your editor. It has 2 parameters 1. An n x n 2D array of integers, m, where the value of each element m where 0 s j n) is a binary integer (i.e., a 0 or 1) 2. An array of q integers, t, where the value of each element tk (where 0 s k q) is a group size for which you must find the number of groups in m Your function must go through each of the q integers in array t and, for each tk (where Osk

Explanation / Answer

COPY AND PASTE THE FOLLOWING PIECE OF CODE

    /* Size of matrix */
    private static int ROW, COL;

  
   
    private static int DFS(int M[][], int row, int col, boolean visited[][])
    {
        // These arrays are used to get row and column numbers
        // of 8 neighbors of a given cell
        int rowNbr[] = new int[] {-1, -1, -1, 0, 0, 1, 1, 1};
        int colNbr[] = new int[] {-1, 0, 1, -1, 1, -1, 0, 1};

        // Mark this cell as visited
        visited[row][col] = true;

        // Recur for all connected neighbours
      
        int count = 1;
        for (int k = 0; k < 8; ++k) {
            if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited) ) {
               count = count + DFS(M, row + rowNbr[k], col + colNbr[k], visited);
            }
        }
        return count;
    }
  
  
  
public static int[] countGroups(int[][] M, int[] t) {
       ROW = M.length;
       COL = M[0].length;

       /* Make a bool array to mark visited cells.
         * Initially all cells are unvisited
       */
       boolean visited[][] = new boolean[ROW][COL];
       int[] groupCountBySize = new int[(ROW*COL) + 1];
      
        /* Initialize count as 0 and travese through the all cells of given matrix */
        for (int i = 0; i < ROW; ++i)
            for (int j = 0; j < COL; ++j)
                if (M[i][j]==1 && !visited[i][j]) {  
                   /*
                   * If a cell with value 1 is not visited yet, then
                   * new group found, Visit all cells in this group and increment group count
                     * */
                    int groupSize = DFS(M, i, j, visited);
                    groupCountBySize[groupSize]++;
                }
    
        int[] retArr = new int[t.length];
        for (int i=0; i<t.length; i++) {
           retArr[i] = groupCountBySize[t[i]];
        }
        return retArr;
   }
  
  
private static boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
        /* row number is in range, column number is in range
         * and value is 1 and not yet visited
         */
        return (row >= 0) && (row < ROW) &&
               (col >= 0) && (col < COL) &&
               (M[row][col]==1 && !visited[row][col]);
    }

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.