Submission #2198324

---

Source Code Expand

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

const long long MOD = (long long)1e9 + 7;

vector<int> sq(26, -1);
vector<int> sq2bit(25);

bool isOK(int board, int sq) {
    //小さい順に見ているという前提のもとでboard状態のときにiに置けるかどうか

    //置かれている
    if (board & sq2bit[sq]) {
        return false;
    }

    if (5 <= sq && sq < 20) {
        //上下端の行ではない場合,上下の片方にだけ置かれているとダメ
        bool up = board & sq2bit[sq - 5];
        bool down = board & sq2bit[sq + 5];
        if ((up && !down) || (!up && down)) {
            return false;
        }
    }

    if ((sq % 5 != 0) && (sq % 5 != 4)) {
        //左右端の列ではない場合,左右の片方にだけ置かれているとダメ
        bool left = board & sq2bit[sq - 1];
        bool right = board & sq2bit[sq + 1];
        if ((left && !right) || (!left && right)) {
            return false;
        }
    }

    return true;
}

vector<int> memo(1 << 25, -1);

int solve(int board, int num) {
    //boardが盤面の状態, numが今見ている数字
    if (memo[board] != -1) {
        return memo[board];
    }

    if (num == 26) {
        return 1;
    }

    //位置が指定されているか
    if (sq[num] != -1) {
        return memo[board] = (isOK(board, sq[num]) ? solve(board | sq2bit[sq[num]], num + 1) : 0);
    }

    //指定されていない
    int ok_num = 0;
    for (int sq = 0; sq < 25; sq++) {
        if (isOK(board, sq)) {
            ok_num += solve(board | sq2bit[sq], num + 1);
            ok_num %= MOD;
        }
    }
    return memo[board] = ok_num;
}

int main() {
    for (int i = 0; i < 25; i++) {
        int x;
        cin >> x;
        sq[x] = i;
    }

    for (int i = 0; i < 25; i++) {
        sq2bit[i] = (1 << i);
    }

    cout << solve(0, 1) << endl;
}

Submission Info

Judge Result