LeetCode 37. Sudoku Solver

题目

c++

DFS,代码写的又臭又长，Faster than 85.33%

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 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,*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';
            }
        }
        
    }
};