题目
c
DFS ,代码写的又臭又长，Faster than 85.33%
代码语言：javascript复制class Solution {
public:
set<int> a[10][10];
set<pair<int,int>> e;
int b[10][10];
int c[10][10];
int judge(int i,int j,int x)
{
for(int k=0;k<9;k )
{
if(k==j) continue;
if(c[i][k]==x)
return -1;
}
for(int k=0;k<9;k )
{
if(k==i) continue;
if(c[k][j]==x)
return -1;
}
for(int k=i/3;k<(i/3) * 3 3;k )
{
for(int p=j/3;p<(j/3)*3 3;p )
{
if(k==i&&p==j) continue;
if(c[k][p]==x) return -1;
}
}
return 1;
}
void change(int i,int j,int x)
{
for(int k=0;k<9;k )
{
if(k==j) continue;
if(c[i][k]==0)
{
if(a[k][j].count(x)==1){
e.insert(make_pair(i,k));
a[i][k].erase(x);
}
}
}
for(int k=0;k<9;k )
{
if(k==i) continue;
if(c[k][j]==0)
{
if(a[k][j].count(x)==1){
e.insert(make_pair(k,j));
a[k][j].erase(x);
}
}
}
for(int k=i/3;k<(i/3) * 3 3;k )
{
for(int p=j/3;p<(j/3)*3 3;p )
{
if(k==i&&p==j) continue;
if(c[k][p]==0)
{
if(a[k][j].count(x)==1){
e.insert(make_pair(k,p));
a[k][p].erase(x);
}
}
}
}
}
int fun()
{
int x=0,y=0;
int m=999999;
for(int i=0;i<9;i )
{
for(int j=0;j<9;j )
{
if(c[i][j]!=0)
{
if(a[i][j].size()==0)
return -1;
if(m>a[i][j].size())
{
m=a[i][j].size();
x=i;
y=j;
}
}
}
}
if(c[x][y]!=0)
return 1;
set<int>::const_iterator iter;
int tag=0;
for(iter = a[x][y].begin();iter!=a[x][y].end();iter )
{
int n=c[x][y];
c[x][y]=*iter;
int ans = judge(x,y,*iter);
if(ans==-1)
{
c[x][y]=n;
continue;
}
else
{
e.clear();
change(x,y,*iter);
tag=1;
if(fun()==-1)
{
tag=0;
set<pair<int,int>>::const_iterator iter2;
for(iter2 = e.begin();iter2!=e.end();iter2 )
{
a[(*iter2).first][(*iter2).second].insert(*iter);
}
continue;
}
}
}
if(tag==0)
return -1;
return 1;
}
void solveSudoku(vector<vector<char>>& board) {
for(int i=0;i<9;i )
{
for(int j=0;j<9;j )
{
if(board[i][j]!='.')
c[i][j]=board[i][j]-'0';
else
c[i][j]=0;
if(c[i][j]!=0)
{
b[i][j]=1;
a[i][j].insert(c[i][j]);
}
else
{
b[i][j]=9;
for(int k=1;k<=9;k )
{
a[i][j].insert(k);
}
}
}
}
for(int i=0;i<9;i )
{
for(int j=0;j<9;j )
{
if(c[i][j]!=0) continue;
for(int k=0;k<9;k )
{
if(k==j) continue;
if(c[i][k]!=0)
{
a[i][j].erase(c[i][k]);
}
}
for(int k=0;k<9;k )
{
if(k==i) continue;
if(c[k][j]!=0)
{
a[i][j].erase(c[k][j]);
}
}
for(int k=i/3;k<(i/3) * 3 3;k )
{
for(int p=j/3;p<(j/3)*3 3;p )
{
if(k==i&&p==j) continue;
if(c[k][p]!=0)
{
a[i][j].erase(c[k][p]);
}
}
}
}
}
fun();
for(int i=0;i<9;i )
{
for(int j=0;j<9;j )
{
board[i][j]=c[i][j] '0';
}
}
}
};
