過去ログ

いちごみるく

というわけというで１マスごとに再帰で30秒
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define endl "\n"

long long N, M, subM;
int Board[7][7];
long long dfs(const int &d) {
if (d == ((N - 1)* (N - 1) - 1)) {
return 1;
}
int x = d / (N - 1) + 1;
int y = d % (N - 1) + 1;
long long ret = 0;
rep(i, N) {
int num = i + 1;
bool b = true;
rep(j, N) {
if (num == Board[x][j]) {
b = false;
break;
}
}
if (!b) { continue; }
rep(j, N) {
if (num == Board[j][y]) {
b = false;
break;
}
}
if (!b) { continue; }
Board[x][y] = num;
ret += dfs(d + 1);
Board[x][y] = 0;
}
return ret;
}
int main() {
cin >> N;
clock_t start = clock();
M = 1;
rep(i, N) {
M *= (i + 1);
}
subM = M / N;
rep(i, N) {
Board[0][i] = i + 1;
Board[i][0] = i + 1;
}
long long ans = M * subM;
ans *= dfs(0);
cout << ans << endl;
clock_t end = clock();
const double time = static_cast<double>(end - start);
printf("time %d[ms]\n", (int)time);
}

　　 2月17日（水） 22:55:37　　　　50163

過去問題一覧へ戻る