Submission #434040

---

Source Code Expand

#include <iostream>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <algorithm>
#include <functional>
#include <limits.h>
#include <bitset>

#include <tuple>
#include <unordered_map>

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int INF = 1 << 29;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int board[6][6];

int check() {
  // cout << "-------------------" << endl;
  // for (int i = 0; i < 5; i++){
  // 	for (int j = 0; j < 5; j++){
  // 		cout << board[i][j] << " ";
  // 	}
  // 	cout << endl;
  // }
  // cout << "-------------------" << endl;

  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 3; j++) {
      if ((board[i][j] < board[i][j + 1] and
           board[i][j + 1] < board[i][j + 2]) or
          (board[i][j] > board[i][j + 1] and
           board[i][j + 1] > board[i][j + 2])) {
        return 0;
      }
    }
  }
  for (int j = 0; j < 5; j++) {
    for (int i = 0; i < 3; i++) {
      if ((board[i][j] < board[i + 1][j] and
           board[i + 1][j] < board[i + 2][j]) or
          (board[i][j] > board[i + 1][j] and
           board[i + 1][j] > board[i + 2][j])) {
        return 0;
      }
    }
  }
  return 1;
}

ll res;
vector<pii> zero;
bool cand[30];
void dfs(int cnt) {
  if (cnt == zero.size()) {
    res += check();
    res %= MOD;
    return;
  }
  pii p = zero[cnt];
  for (int i = 1; i <= 25; i++) {
    if (!cand[i]) {
      board[p.first][p.second] = i;
      cand[i] = true;
      dfs(cnt + 1);
      cand[i] = false;
      board[p.first][p.second] = 0;
    }
  }
  return;
}

int main() {
  // int sum = 0;
  for (int i = 0; i < 30; i++){
  	cand[i] = false;
  }
  res = 0;
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
      cin >> board[i][j];
      cand[board[i][j]] = true;
      if (board[i][j] == 0) {
        zero.push_back(mp(i, j));
      }
    }
  }
  if (zero.size() >= 10) {
    return 0;
  }
  dfs(0);
  res %= MOD;
  cout << res << endl;
  return 0;
}

Submission Info

Judge Result