Submission #1493875

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;
using llng = long long;
template<typename T> using v = vector<T>;
template<typename T> using vv = v<v<T> >;

const int MOD = 1e9+7;
int x[5][5];
v<bool> used(26, false);

bool valid(int p) {
    int i = p/5, j = p%5;
    if (2 <= i) {
        if (x[i-2][j] < x[i-1][j] && x[i-1][j] < x[i][j]) return false;
        if (x[i-2][j] > x[i-1][j] && x[i-1][j] > x[i][j]) return false;
    }
    if (2 <= j) {
        if (x[i][j-2] < x[i][j-1] && x[i][j-1] < x[i][j]) return false;
        if (x[i][j-2] > x[i][j-1] && x[i][j-1] > x[i][j]) return false;
    }
    return true;
}

int dfs(int p) {
    if (p == 25) return 1;

    int i = p/5, j = p%5;

    if (x[i][j] != 0) {
        if (!valid(p)) return 0;
        else return dfs(p+1);
    }
    int ret = 0;
    for (int k=1; k<=25; k++) if (!used[k]) {
        used[k] = true;
        x[i][j] = k;
        if (valid(p)) (ret += dfs(p+1)) %= MOD;
        x[i][j] = 0;
        used[k] = false;
    }
    return ret;
}

int main() {
    int count;
    for (int i=0; i<5; i++) for (int j=0; j<5; j++) {
        cin >> x[i][j];
        if (x[i][j] > 0) { used[x[i][j]] = true; count++; }
    }
    if (!(count >= 17)) return 0;

    cout << dfs(0) << endl;
    return 0;
}

Submission Info

Judge Result