Code : GCD on a grid

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

int solve(vector<vector<int>> &mat) {
    int row = mat.size(), col = mat[0].size();

    vector<int> choices;
    int mx = __gcd(mat[0][0], mat[row - 1][col - 1]);
    for (int num = 1; num * num <= mx; num++) {
        if ((mx % num) == 0) {
            choices.push_back(num);
            choices.push_back(mx / num);
        }
    }
    sort(choices.begin(), choices.end(), greater<int>());
    vector<vector<bool>> dp(row + 1, vector<bool>(col + 1, 0));

    for (int &g : choices) {
        for (int i = 0; i < row; i++) {
            dp[i].assign(col, false);
        }
        dp[0][0] = (mat[0][0] % g) == 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (!dp[i][j]) {
                    continue;
                }
                if (i + 1 < row && (mat[i + 1][j] % g) == 0) {
                    dp[i + 1][j] = true;
                }
                if (j + 1 < col && (mat[i][j + 1] % g) == 0) {
                    dp[i][j + 1] = true;
                }
            }
        }
        if (dp[row - 1][col - 1]) {
            return g;
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int row, col;
        cin >> row >> col;
        vector<vector<int>> mat(row, vector<int>(col, 0));
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                cin >> mat[i][j];
            }
        }
        cout << solve(mat) << "\n";
    }
}