[TIOJ] 1235. 富翁種花

題目連結:http://tioj.infor.org/problems/1235

---

比較trivial的數獨，轉成正常數獨後，就暴搜吧XD

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

struct pos{
	int x,y;
	pos(){}
	pos(int a,int b){x=a;y=b;}
};

int sudoku[9][9];
bitset<9> ori[9];
vector<pos> need;
bool solve(int);
inline bool check(int,int);
inline int toid(char);
inline char toch(char);

int main(){
	char ss[15];
	for(int i=0;i<9;i++){
		gets(ss);
		for(int j=0;j<9;j++){
			if(ss[j]=='*'){
				sudoku[i][j]=0;
				need.push_back(pos(i,j));
				ori[i][j]=1;
			}else{
				sudoku[i][j] = toid(ss[j]);
				ori[i][j]=0;
			}
		}
	}
	solve(0);
	return 0;
}

inline int toid(char a){
	switch(a){
		case 'R':return 1;
		case 'O':return 2;
		case 'Y':return 3;
		case 'G':return 4;
		case 'B':return 5;
		case 'I':return 6;
		case 'P':return 7;
		case 'L':return 8;
		case 'W':return 9;
	}
}
inline char toch(int a){
	char oo[] = "*ROYGBIPLW";
	return oo[a];
}

inline bool check(int x,int y){
	int arr[10];
	for(int i=0;i<10;i++)arr[i]=0;
	for(int i=0;i<9;i++){
		if(sudoku[x][i]==0)continue;
		arr[sudoku[x][i]]++;
		if(arr[sudoku[x][i]]>1)return 0;
	}
	for(int i=0;i<10;i++)arr[i]=0;
	for(int i=0;i<9;i++){
		if(sudoku[i][y]==0)continue;
		arr[sudoku[i][y]]++;
		if(arr[sudoku[i][y]]>1)return 0;
	}
	for(int i=0;i<10;i++)arr[i]=0;
	x/=3;
	y/=3;
	for(int i=x*3;i<(x+1)*3;i++){
		for(int j=y*3;j<(y+1)*3;j++){
			if(sudoku[i][j]==0)continue;
			arr[sudoku[i][j]]++;
			if(arr[sudoku[i][j]]>1)return 0;
		}
	}
	return 1;
}

bool solve(int x){
	if(x==need.size()){
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++)if(ori[i][j])printf("%c",toch(sudoku[i][j]));
			putchar('\n');
		}
		return 1;
	}
	pos cur=need[x];
	for(int i=0;i<9;i++){
		sudoku[cur.x][cur.y]=i+1;
		bool oao = check(cur.x,cur.y);
		if(oao)	oao=solve(x+1);
		if(oao) return 1;
	}
	sudoku[cur.x][cur.y]=0;
	return 0;
}