SRM315 div1 medium
テストケース見たら最大でも288通りしかないことがわかったので、深さ優先で全探索。
数字が埋まっていても数独としては成り立っていない場合を忘れ一回resubmit。
#include <string> #include <vector> using namespace std; class SillySudoku { public: vector<string> group; vector<string> board; int rec(int pos) { if(pos==16) return 1; else { int y=pos/4,x=pos%4,r=0; bool isEmpty=(board[y][x]=='-'); if(!isEmpty) { vector<bool> used(5,false); for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(i==y || j==x || group[i][j]==group[y][x]) { if(i!=y || j!=x) { char c=board[i][j]; if(c!='-') used[c-'0']=true; } } if(used[board[y][x]-'0']) return 0; else return rec(pos+1); } else { vector<bool> used(5,false); for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(i==y || j==x || group[i][j]==group[y][x]) { char c=board[i][j]; if(c!='-') used[c-'0']=true; } for(int cur=1;cur<5;cur++) if(!used[cur]) { board[y][x]=cur+'0'; r+=rec(pos+1); } board[y][x]='-'; return r; } } } int countWays(vector <string> _board) { board=_board; group.push_back("AABB"); group.push_back("AABB"); group.push_back("CCDD"); group.push_back("CCDD"); return rec(0); } };