Connected Cells in a Grid

  • + 0 comments

    C++ solution using backtracking(similar to rat in a maze)

    int maze(vector<vector<int>> &matrix,int i,int j){
        if(i>=0 && i<matrix.size() && j>=0 &&
         j<matrix[0].size() && matrix[i][j]!=0){
            matrix[i][j]--;
            return (1+maze(matrix,i-1,j)+maze(matrix,i+1,j)+
            maze(matrix,i,j-1)+maze(matrix,i,j+1)+maze(matrix,i-1,j-1)+
            maze(matrix,i-1,j+1)+maze(matrix,i+1,j-1)+
            maze(matrix,i+1,j+1));
        }
        else{
            return 0;
        }
    }
    
    int connectedCell(vector<vector<int>> matrix) {
        vector<int>v;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++){
                if(matrix[i][j]==1){
                    v.push_back(maze(matrix,i,j));
                }
            }
        }
        sort(v.begin(),v.end());
        if(v.empty()) return 0;
        else return v[v.size()-1];
    }