Implementing solution of HackerRank's Connected Cells Question

user_15792344 0
Viewed 535

Consider a matrix where each cell contains either a 0 or a 1. Any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. In the following grid, all cells marked X are connected to the cell marked Y.

XXX
XYX  
XXX

If one or more filled cells are also connected, they form a region. Note that each cell in a region is connected to zero or more cells in the region but is not necessarily directly connected to all the other cells in the region.

Given an nXm matrix, find and print the number of cells in the largest region in the matrix. Note that there may be more than one region in the matrix.

For example:

Sample Input:

5 4
0 0 1 1
0 0 1 0
0 1 1 0
0 1 0 0
1 1 0 0

OUTPUT: 8

I tried to Solved this Question and below is what I have tried. The problem is that My dfs search in the matrix is never completed. It is terminated after some steps. I don't know where am I getting wrong?

#include<bits/stdc++.h>
using namespace std;

bool isValid (int row, int column, int n, int m, bool** visited){
  if(row<0 || row>n-1 || column<0 || column>m-1){
    return false;
  }
  if(visited[row][column]==true){
    return false;
  }

  return true;
}

int countConnectedCells(int** arr, int n, int m, bool** visited, int row, int column){

  visited[row][column]=1;
  int current_maximum=0;

  
  if(arr[row][column]==1){

    current_maximum=1;

    //Down
    if(isValid(row+1,column, n, m, visited)){
      current_maximum+=countConnectedCells(arr, n, m, visited, row+1, column);
    }

    //Right
    if(isValid(row,column+1, n, m, visited)){
      current_maximum+=countConnectedCells(arr, n, m, visited, row, column+1);
    }

    //Left
    if(isValid(row,column-1, n, m, visited)){
      current_maximum+=countConnectedCells(arr, n, m, visited, row, column-1);
    }

     //Upward
    if(isValid(row-1,column, n, m, visited)){
      current_maximum+=countConnectedCells(arr, n, m, visited, row-1, column);
    }
    
    //UpwardLeft
    if(isValid(row-1,column-1, n, m, visited)){
      current_maximum+=countConnectedCells(arr, n, m, visited, row-1, column-1);
    }

    //UpwardRight
    if(isValid(row-1,column+1, n, m, visited)){
      current_maximum+=countConnectedCells(arr, n, m, visited, row-1, column+1);
    }

     //DownwardRight
    if(isValid(row+1,column+1, n, m, visited)){
      current_maximum+=countConnectedCells(arr, n, m, visited, row+1, column+1);
    }

    //DownLeft
    if(isValid(row+1,column-1, n, m, visited)){
      current_maximum+=countConnectedCells(arr, n, m, visited, row+1, column-1);
    }

  }

   return current_maximum;
}

int main(){
  int n, m;
  cin>>n>>m;
  int **arr;
  bool **visited;

  int maximum=0;

  /* allocate the array */
  arr = (int** )malloc(n * sizeof *arr);
  for (int i=0; i<n; i++)
  {
    arr[i] = (int*)malloc(m * sizeof *arr[i]);
  }

  /* allocate the visited array */
  visited = (bool** )malloc(n * sizeof *visited);
  for (int i=0; i<n; i++)
  {
    visited[i] = (bool*)malloc(m * sizeof *visited[i]);
  }


  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin>>arr[i][j];
    }
  }

  /* dfs call on each cell that has value 1 and is unvisited*/
  for(int row=0; row<n; row++){
    for(int column=0; column<m; column++){
      if(arr[row][column]==1&&isValid(row,column, n, m, visited))
      maximum = max(maximum, countConnectedCells(arr, n, m, visited, row, column));
    }
  }
  cout<<maximum<<endl;

  /* deallocate the array */
  for (int i=0; i<n; i++)
  {
    free(arr[i]);
  }

}

EDIT: QUESTION LINK

depth-first-search algorithm c++
1 Answers

Explanation

The problem is that you're resetting your current_max too early. It shouldn't be done once you reach the bottom of your recursion stack, but rather when you finish all your recursion calls.

So, introduce a local variable uint32_t current_maximum in your countConnectedCells(). Remove your global variables used for holding the current and global max. So, countConnectedCells can look as below:

uint32_t countConnectedCells(int** arr, int n, int m, bool** visited, int row, int column) {

  visited[row][column]=1;
  uint32_t current_maximum = 0;

  if(arr[row][column]==1) {
    current_maximum = 1;

    //Down
    if(isValid(row+1,column, n, m, visited)) {
        current_maximum += countConnectedCells(arr, n, m, visited, row+1, column);
    }

    //Right
    if(isValid(row,column+1, n, m, visited)) {
        current_maximum += countConnectedCells(arr, n, m, visited, row, column+1);
    }

    //Left
    if(isValid(row,column-1, n, m, visited)) {
        current_maximum += countConnectedCells(arr, n, m, visited, row, column-1);
    }

     //Upward
    if(isValid(row-1,column, n, m, visited)) {
        current_maximum += countConnectedCells(arr, n, m, visited, row-1, column);
    }
    
    //UpwardLeft
    if(isValid(row-1,column-1, n, m, visited)) {
        current_maximum += countConnectedCells(arr, n, m, visited, row-1, column-1);
    }

    //UpwardRight
    if(isValid(row-1,column+1, n, m, visited)) {
        current_maximum += countConnectedCells(arr, n, m, visited, row-1, column+1);
    }

     //DownwardRight
    if(isValid(row+1,column+1, n, m, visited)) {
        current_maximum += countConnectedCells(arr, n, m, visited, row+1, column+1);
    }

    //DownLeft
    if(isValid(row+1,column-1, n, m, visited)) {
        current_maximum += countConnectedCells(arr, n, m, visited, row+1, column-1);
    }
  }

  return current_maximum;
}

Then, in your main() change your for loop calculating the maximum area such that for each starting cell, your countConnectedCells returns an area with that cell as a starting one, and then update your max value here:

...
/* dfs call on each cell that has value 1 and is unvisited*/
uint32_t maximum = 0;
for(int row=0; row<n; row++){
    for(int column=0; column<m; column++){
      if(arr[row][column]==1&&isValid(row,column, n, m, visited))
          maximum = std::max(maximum, countConnectedCells(arr, n, m, visited, row, column));
    }
}
cout<<maximum<<"\n";
...

After doing this, the solution works just fine (all the tests pass).

Improvement

Actually, you don't need to introduce an additional bool array because you can re-use your initial array for marking visited cells. You should also use std::vector for your matrix so that not to allocate/deallocate your array manually. There are further improvements that you can - please check my code below:

#include <bits/stdc++.h>

using namespace std;

uint32_t connectedCell0(uint32_t i, uint32_t j, std::vector<std::vector<uint32_t>> &matrix) {
    uint32_t n = matrix.size();
    uint32_t m = matrix[0].size();
    if (i < 0 || i >= n || j < 0 || j >= m || !matrix[i][j]) {
        return 0;
    }
    
    //mark as visited
    matrix[i][j] = 0;
    return 1 + connectedCell0(i, j + 1, matrix) +
           connectedCell0(i, j - 1, matrix) +
           connectedCell0(i - 1, j - 1, matrix) +
           connectedCell0(i - 1, j, matrix) +
           connectedCell0(i - 1, j + 1, matrix) +
           connectedCell0(i + 1, j - 1, matrix) +
           connectedCell0(i + 1, j, matrix) +
           connectedCell0(i + 1, j + 1, matrix);
}

// Complete the connectedCell function below.
uint32_t connectedCell(std::vector<std::vector<uint32_t>> &matrix) {
    uint32_t maxArea = 0;
    for (uint32_t i = 0; i < matrix.size(); i++) {
        for (uint32_t j = 0; j < matrix[i].size(); j++) {
            if (matrix[i][j]) {
                maxArea = max(maxArea, connectedCell0(i, j, matrix));
            }
        }
        std::cout << endl;
    }

    return maxArea;
}

int main() {
    ofstream fout(getenv("OUTPUT_PATH"));

    uint32_t n;
    std::cin >> n;
    std::cin.ignore(numeric_limits<streamsize>::max(), '\n');

    uint32_t m;
    std::cin >> m;
    std::cin.ignore(numeric_limits<streamsize>::max(), '\n');

    std::vector<std::vector<uint32_t>> matrix(n);
    for (uint32_t i = 0; i < n; i++) {
        matrix[i].resize(m);

        for (uint32_t j = 0; j < m; j++) {
            std::cin >> matrix[i][j];
        }

        std::cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    uint32_t result = connectedCell(matrix);

    fout << result << "\n";

    fout.close();

    return 0;
}
user_10553950
Related