AOJ 2058 : Moduic Squares
問題リンク:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2058
問題概要:
3*3のsquareと1つの値modがあたえられる
squareの各列の和%modとsquareの各行の和%modとsquareの対角線の和%modがすべて等しいものの数を出力せよ
使用した言語:C++
解法:
実際に全通り試した
map怖い
コード:
#include<iostream> #include<algorithm> #include<vector> #include<bitset> #include<map> #include<cassert> #include<deque> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; int ans; map<vector<int>,bool> exist; bool check(vector<int>& box); void dfs(int p,vector<int>& box,int bit) { if(p == 10) { ans += check(box)?1:0; return; } if(box[p]) { dfs(p+1,box,bit); return; } /* if(exist[box]) return; exist[box] = true; */ for(int j=1;j<=10;j++) { if((bit >> j) & 1) continue; box[p] = j; dfs(p+1,box,bit|(1<<j)); box[p] = 0; } } int main() { while(1) { vector<int> box(10); ans = 0; exist.clear(); int bit = 0; bool F = true; rep(i,10) { cin >> box[i]; bit |= (1 << box[i]); if(box[i] != -1) F = false; } if(F) break; bit &= (((1<<20)-1)-1); dfs(0,box,bit); cout <<ans << endl; } return 0; } bool check(vector<int>& g) { int module = g[9]; int sum = (g[0]+g[1]+g[2])%module; if((g[3]+g[4]+g[5])%module != sum || (g[6]+g[7]+g[8])%module != sum) return false; if((g[0]+g[3]+g[6])%module != sum || (g[1]+g[4]+g[7])%module != sum || (g[2]+g[5]+g[8])%module != sum) return false; if((g[0]+g[4]+g[8])%module != sum || (g[2]+g[4]+g[6])%module != sum) return false; return true; }