[TIOJ] 1235. 富翁種花
題目連結:http://tioj.infor.org/problems/1235
比較trivial的數獨,轉成正常數獨後,就暴搜吧XD
比較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;
}
留言
張貼留言