Submission #2414211

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

long long a[5][5], dp[1 << 22], mod = 1000000007; bool used[26];
vector<int>G; vector<pair<int, int>>s; pair<int, int>Z[26];

int main() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) { cin >> a[i][j]; Z[a[i][j]] = make_pair(i, j); if (a[i][j] == 0) s.push_back(make_pair(i, j)); used[a[i][j]] = true; }
	}
	for (int i = 1; i <= 25; i++) { if (used[i] == false) G.push_back(i); }
	dp[0] = 1;
	for (int i = 0; i < (1 << G.size()); i++) {
		int c[5][5], cnt = 0;
		for (int j = 0; j < 5; j++) { for (int k = 0; k < 5; k++) { c[j][k] = a[j][k]; if (c[j][k] == 0) c[j][k] = 26; } }
		for (int j = 0; j < G.size(); j++) { if ((i / (1 << j)) % 2 == 1) { c[s[j].first][s[j].second] = 0; cnt++; } }

		int L1 = 1, L2 = 25; if (cnt >= 1) L1 = G[cnt - 1] + 1; if (cnt < G.size()) L2 = G[cnt] - 1;
		for (int l = L1; l <= L2; l++) {
			int j = Z[l].first, k = Z[l].second;
			if (j >= 1 && j <= 3) {
				if (((c[j - 1][k] <= l) ^ (l >= c[j + 1][k])) == true) dp[i] = 0;
			}
			if (k >= 1 && k <= 3) {
				if (((c[j][k - 1] <= l) ^ (l >= c[j][k + 1])) == true) dp[i] = 0;
			}
		}

		for (int l = 0; l < s.size(); l++) {
			int j = s[l].first, k = s[l].second;
			if (c[j][k] != 26) continue;
			if (j >= 1 && j <= 3) {
				if (((c[j - 1][k] <= G[cnt]) ^ (G[cnt] >= c[j + 1][k])) == true) continue;
			}
			if (k >= 1 && k <= 3) {
				if (((c[j][k - 1] <= G[cnt]) ^ (G[cnt] >= c[j][k + 1])) == true) continue;
			}
			dp[i + (1 << l)] += dp[i];
			dp[i + (1 << l)] %= mod;
		}
	}
	cout << dp[(1 << s.size()) - 1] << endl;
	return 0;
}

Submission Info

Judge Result