时间戳

首页 > 解决方案 > HackerRank 的 Connected Cells 问题的实现解决方案

c++ - HackerRank 的 Connected Cells 问题的实现解决方案

问题描述

考虑一个矩阵，其中每个单元格包含 0 或 1。任何包含 1 的单元格都称为填充单元格。如果两个单元在水平、垂直或对角线上彼此相邻，则称它们是连接的。在下面的网格中，所有标记为 X 的单元格都连接到标记为 Y 的单元格。

XXX
XYX  
XXX

如果一个或多个填充单元也连接起来，它们形成一个区域。请注意，区域中的每个单元都连接到该区域中的零个或多个单元，但不一定直接连接到该区域中的所有其他单元。

给定一个 nXm 矩阵，找出并打印矩阵中最大区域的单元格数。请注意，矩阵中可能有多个区域。

例如：

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

我试图解决这个问题，下面是我尝试过的。问题是我在矩阵中的 dfs 搜索从未完成。它在一些步骤后终止。我不知道我哪里错了？

#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]);
  }

}

编辑： 问题链接

标签： c++algorithmdepth-first-search

解决方案

解释

问题是你current_max过早地重置你的。一旦你到达递归堆栈的底部，就不应该这样做，而是当你完成所有递归调用时。

所以，uint32_t current_maximum在你的countConnectedCells(). 删除用于保存当前和全局最大值的全局变量。因此，countConnectedCells可以如下所示：

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;
}

然后，在您main()更改for循环计算最大面积时，对于每个起始单元格，您countConnectedCells返回一个以该单元格作为起始单元格的区域，然后在此处更新您的最大值：

...
/* 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";
...

这样做之后，解决方案就可以正常工作（所有测试都通过了）。

改进

实际上，您不需要引入额外的bool数组，因为您可以重复使用初始数组来标记已访问的单元格。您还应该使用std::vector您的矩阵，以免手动分配/取消分配您的数组。您可以进行进一步的改进 - 请查看下面的代码：

#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;
}

推荐阅读