Largest Region Connected Cells in Grid

    Tiếp tục series, hôm nay chúng ta cùng làm một bài về DFS (duyệt theo chiều sâu) nhé!

Bài toán mình lấy trên Hackerrank, cho ma trận n hàng, m cột. Tìm đường đi dài nhất trên ma trận (có thể đi dọc, ngang và chéo).

Input:
4
4
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0
Output:
5

Về DFS thì chúng ta đều biết có thể tiến hành theo giải thuật đệ quy hoặc Stack đều được (đệ quy và Stack đều có tính chất đảo ngược), mình xin trình bày theo đệ quy nhé!

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

int nr, nc;
bool mark[10][10];
int dr[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dc[] = {1, 1, 1, 0, -1, -1, -1, 0};
void DFSRecursion(int n, int m, vector<vector<int>> matrix, int r, int c, int &count){
    mark[r][c] = true;
    for(int k = 0; k < 8; k++){
        nr = r + dr[k];
        nc = c + dc[k];
        if(nr >= 0 && nr < n && nc >= 0 && nc < m && matrix[nr][nc] && !mark[nr][nc])
        {
            count++;
            DFSRecursion(n, m, matrix, nr, nc, count);
        }
    }
}

int ConnectedCell(vector<vector<int>> matrix, int n, int m){
    int result = 1;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(matrix[i][j] && !mark[i][j])
            {
                int count = 1;
                DFSRecursion(n, m, matrix, i, j, count);
                if(count > result)
                    result = count;
            }
        }
    }
    return result;
}

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

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

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

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

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

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

    int result = ConnectedCell(matrix, n, m);

    fout << result << "\n";

    fout.close();

    return 0;
}

Ok, hẹn gặp lại các bạn ở bài viết sau!