Submission #1176029

---

Source Code Expand

#include <cstdio>
#include <algorithm>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(i, n) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(i, n) REP(j, m) printf("%d%c", a[i][j], j + 1 == m ? '\n' : ' '); puts("")

//------------------------------------------------------------------------------
int num_of_bits(int bits)
{
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

//------------------------------------------------------------------------------
const int MOD = 1000000007;
const int N = 25;
const int DP_MAX = 1 << 20;

typedef pair<int, int> P;

int x[5][5];

int M;
// dp bit position => next position ([i, j])
P pos[N];
// dp bit count => next value (v)
int vs[N];
// position ([i, j]) => dp bit value
int bit[5][5];
// positions of used values
P xpos[N];

int dp[DP_MAX];

void init() {
  M = 0;
  REP(i, N) vs[i] = i + 1;
  REP(i, 5) REP(j, 5) {
    if (x[i][j] == 0) {
      pos[M] = P(i, j);
      bit[i][j] = 1 << M;
      M++;
    } else {
      vs[x[i][j] - 1] = 0;
      xpos[x[i][j]] = P(i, j);
    }
  }
  int m = 0;
  REP(i, N) if (vs[i] > 0) vs[m++] = vs[i];
}

int next_v(int i) {
  return vs[num_of_bits(i)];
}

int prev_v(int i) {
  if (i == 0) return 0;
  else return vs[num_of_bits(i) - 1];
}

bool used(int i, int a, int b, int v) {
  if (0 < x[a][b] && x[a][b] < v) return true;
  if (i & bit[a][b]) return true;
  return false;
}

bool valid_at(int i, int a, int b, int v) {
  if (0 < a && a < 4)
    if (used(i, a - 1, b, v) != used(i, a + 1, b, v))
      return false;
  if (0 < b && b < 4)
    if (used(i, a, b - 1, v) != used(i, a, b + 1, v))
      return false;
  return true;
}

bool valid(int i, int j) {
  int v0 = prev_v(i);
  int v1 = next_v(i);
  FOR(v, v0 + 1, v1 - 1) {
    P xp = xpos[v];
    int xa = xp.first, xb = xp.second;
    if (!valid_at(i, xa, xb, v)) return false;
  }
  P p = pos[j];
  int a = p.first, b = p.second;
  if (!valid_at(i, a, b, v1)) return false;
  return true;
}

void solve() {
  init();
  int S = 1 << M;
  dp[0] = 1;
  FOR(i, 1, S - 1) {
    REP(j, M) if (i >> j & 1) {
      int i0 = i & ~(1 << j);
      if (valid(i0, j)) dp[i] = (dp[i] + dp[i0]) % MOD;
    }
  }
  printf("%d\n", dp[S - 1]);
}

void input() {
  REP(i, 5) REP(j, 5) scanf("%d", &x[i][j]);
}

int main() {
  input();
  solve();
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void input()’:
./Main.cpp:112:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(i, 5) REP(j, 5) scanf("%d", &x[i][j]);
                                            ^

Judge Result