Submission #433924

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <cstring>
#include <cctype>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <complex>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for(int i = a; i < (int)b; i++)
#define FOREQ(i,a,b) for(int i = a; i <= (int)b; i++)
#define FOREACH(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define ALL(c) (c).begin(), (c).end()
#define SZ(c) (c).size()
template <class T> void pp(T v) { FOREACH(it, v) cout << *it << ' '; cout << endl ; }
template <class T> void pp(T v, int n) { REP(i,n) cout<<v[i]<< ' '; cout << endl; }
template <class T> inline void chmax(T &a, const T b) { a = max(a, b); }
template <class T> inline void chmin(T &a, const T b) { a = min(a, b); }
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef complex<double> P;
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef unsigned uint;
const int INF = 1<<28;
const double EPS = 1.0e-9;
static const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
#undef MOD_CALC
#ifdef MOD_CALC
const ll MOD = 1000 * 1000 * 1000 + 7 ; // 1000000007
inline void chadd(ll &a, const ll b) { a = (a + b) % MOD;}
inline ll add(const ll a, const ll b){ return (a + b) %  MOD;}
inline void chsub(ll &a, const ll b) { a = (a - b + MOD) % MOD;}
inline ll sub(const ll a, const ll b){ return (a - b + MOD) % MOD; }
inline void chmul(ll &a, const ll b) { a = (a * b) %  MOD;}
inline ll mul(const ll a, const ll b){ return (a * b) %  MOD;}
#endif
int brd[5][5];
vector<pint> rem_pos;
vector<int> rem_num;
vector<bool> used;
int num = 0;
bool brd_check() {
    REP(h,3) REP(w,5) {
        if(brd[h][w] < brd[h+1][w] && brd[h+1][w] < brd[h+2][w]) return false;
        if(brd[h][w] > brd[h+1][w] && brd[h+1][w] > brd[h+2][w]) return false;
    }
    REP(w,3) REP(h,5) {
        if(brd[h][w] < brd[h][w+1] && brd[h][w+1] < brd[h][w+2]) return false;
        if(brd[h][w] > brd[h][w+1] && brd[h][w+1] > brd[h][w+2]) return false;
    }
    return true;
}
int dfs(const int depth) {
    int ans = 0;
    if(depth == num) {
        if(brd_check()) ans++;
        return ans;
    }
    REP(i, num) {
        if(used[i] == false) {
            used[i] = true;
            brd[rem_pos[depth].first][rem_pos[depth].second] = rem_num[i];
            ans += dfs(depth+1);
            brd[rem_pos[depth].first][rem_pos[depth].second] = 0;
            used[i] = false;
        }
    }
    return ans;
}
int main(void)
{
    vector<int> exist(5*5+1, 0);
    REP(i,5) REP(j,5) {
        cin>>brd[i][j];
        if(brd[i][j] == 0) {
            rem_pos.push_back(make_pair(i, j));
        } else {
            exist[brd[i][j]] = 1;
        }
    }
    for(int i = 1; i <= 25; i++) {
        if(exist[i] == 0) rem_num.push_back(i);
    }
    //cout << rem_num.size() << endl;
    //cout << rem_pos.size() << endl;
    num = rem_pos.size();
    if(num > 8) {
        cout << 0 << endl;
        return 0;
    }
    used = vector<bool>(num, false);
    int ans = dfs(0);
    //cout << "Answer=";
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result