Submission #1258157

---

Source Code Expand

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

#define REP(i,n) for(int i=0,_n=(int)(n); i < _n; i++)

typedef long long ll;
const ll MOD = 1000000007;

int nextInt() {
  int x; scanf("%d", &x); return x;
}

int t[5][5];
bool used[26];
ll dp[1 << 20];
vector<int> zr, zc;

bool illegal(int a, int b, int c) {
  if (a == 0 || b == 0 || c == 0) return false;
  return (a < b && b < c) || (a > b && b > c);
}

bool localCheck0(int v, int p1, int p2) {
  if (p1 >= 1 && p2 >= 1) {
    if (v < p1 && p1 < p2) return false;
    if (v > p1 && p1 > p2) return false;
    return true;
  }
  return true;
}
bool localCheck1(int p1, int v, int p2) {
  if (p1 >= 1 && p2 >= 1) {
    if (p1 < v && v < p2) return false;
    if (p1 > v && v > p2) return false;
    return true;
  }
  p1 = p1 == 0 ? v+1 : p1 == -1 ? v-1 : p1;
  p2 = p2 == 0 ? v+1 : p2 == -1 ? v-1 : p2;

  if (p1 < v && v < p2) return false;
  if (p1 > v && v > p2) return false;
  return true;
}
bool localCheck2(int p1, int p2, int v) {
  if (p1 >= 1 && p2 >= 1) {
    if (p1 < p2 && p2 < v) return false;
    if (p1 > p2 && p2 > v) return false;
    return true;
  }
  return true;
}

int main2() {
  REP(i, 5) REP(j, 5) t[i][j] = nextInt();
  memset(used, 0, sizeof(used));
  zr.clear();
  zc.clear();
  int N = 0;

  bool ok = true;
  REP(i, 3) REP(j, 5) if (ok && illegal(t[i][j], t[i+1][j], t[i+2][j])) ok = false;
  REP(i, 5) REP(j, 3) if (ok && illegal(t[i][j], t[i][j+1], t[i][j+2])) ok = false;
  if (!ok) {
    cout << 0 << endl;
    return 0;
  }

  REP(i, 5) REP(j, 5) {
    if (t[i][j] != 0) {
      used[t[i][j]] = true;
    } else {
      zr.push_back(i);
      zc.push_back(j);
      N++;
    }
  }
  if (N == 0) {
    cout << 1 << endl;
    return 0;
  }

  vector<int> red;
  for (int i = 1; i <= 25; i++) if (!used[i]) red.push_back(i);
  red.push_back(26); // sentinel

  memset(dp, 0, sizeof(dp));
  dp[0] = 1;
  for (int set = 0; set < (1 << N); set++) {
    if (dp[set] == 0) continue;

    // 今から置こうとしている数
    int on = __builtin_popcount(set);
    int n = red[ on ];

    // 埋める。今置こうとしている数 n より小さい数であることを意味する
    REP(i, N) if (set >> i & 1) {t[zr[i]][zc[i]] = -1;}

    REP(i, N) if (!(set >> i & 1)) {
      int r = zr[i];
      int c = zc[i];
      t[r][c] = n;

      bool valid = true;
      if (            r+2 < 5) valid = valid && localCheck0(t[r][c], t[r+1][c], t[r+2][c]);
      if (0 <= r-1 && r+1 < 5) valid = valid && localCheck1(t[r-1][c], t[r][c], t[r+1][c]);
      if (0 <= r-2           ) valid = valid && localCheck2(t[r-2][c], t[r-1][c], t[r][c]);
      if (            c+2 < 5) valid = valid && localCheck0(t[r][c], t[r][c+1], t[r][c+2]);
      if (0 <= c-1 && c+1 < 5) valid = valid && localCheck1(t[r][c-1], t[r][c], t[r][c+1]);
      if (0 <= c-2           ) valid = valid && localCheck2(t[r][c-2], t[r][c-1], t[r][c]);

      // if (N == 6) {
      //   cout << endl;
      //   cout << "set=" << set << ", valid=" << valid << endl;
      //   REP(i, 5) {
      //     REP(j, 5) cout << t[i][j] << " ";
      //     cout << endl;
      //   }
      // }

      if (valid) {
        for (int f = n+1; f < red[on + 1]; f++) {
          REP(r, 5) REP(c, 5) if (t[r][c] == f) {
            if (            r+2 < 5) valid = valid && localCheck0(t[r][c], t[r+1][c], t[r+2][c]);
            if (0 <= r-1 && r+1 < 5) valid = valid && localCheck1(t[r-1][c], t[r][c], t[r+1][c]);
            if (0 <= r-2           ) valid = valid && localCheck2(t[r-2][c], t[r-1][c], t[r][c]);
            if (            c+2 < 5) valid = valid && localCheck0(t[r][c], t[r][c+1], t[r][c+2]);
            if (0 <= c-1 && c+1 < 5) valid = valid && localCheck1(t[r][c-1], t[r][c], t[r][c+1]);
            if (0 <= c-2           ) valid = valid && localCheck2(t[r][c-2], t[r][c-1], t[r][c]);
          }
        }
      }

      if (valid) {
        (dp[set | (1 << i)] += dp[set]) %= MOD;
      }

      t[r][c] = 0;
    }

    // 戻す
    REP(i, N) if (set >> i & 1) {t[zr[i]][zc[i]] = 0;}
  }

  ll ans = dp[(1 << N) - 1] % MOD;
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws) main2();
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int nextInt()’:
./Main.cpp:10:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x); return x;
                         ^

Judge Result