专栏首页算法修养LeetCode 37. Sudoku Solver

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT 1004 Counting Leaves

    1004. Counting Leaves (30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B ...

    ShenduCC
  • HDU 1875 畅通工程再续(kruskal)

    畅通工程再续 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

    ShenduCC
  • pta 习题集 5-2 找出不是两个数组共有的元素 (5分)

    给定两个整型数组,本题要求找出不是两者共有的元素。 输入格式: 输入分别在两行中给出两个整型数组,每行先给出正整数NN(≤20≤20),随后是NN个整数,...

    ShenduCC
  • P1972 [SDOI2009]HH的项链

    题目背景 无 题目描述 HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。...

    attack
  • UVA 1030 - Image Is Everything【模拟+思维+迭代更新】

    题目链接:uva 1030 - Image Is Everything 题目大意:有一个最大为n*n*n的立方体的一个不规整立体,由若干个1*1*1的小正方体构...

    Angel_Kitty
  • HDU-6008-Worried School

    ACM模版 描述 ? 题解 简单的模拟题,题意不是特别容易翻译,但是模拟的规则十分简单,和 WFWF 晋级资格相似,大致是一共 X+Y=GX + Y = G 个...

    f_zyj
  • 2018年第九届蓝桥杯B组题解

    按着题目把这些数转换成8字节的二进制数就可以了,负数的二进制是补码。可以自己写个函数实现一下,实际效果图:

    Ch_Zaqdt
  • 【CodeForces 699B】One Bomb

    枚举每个位置如果c[i]+r[j]-(本身是不是*)==总*数,则该位置即为答案。

    饶文津
  • BZOJ 1188: [HNOI2007]分裂游戏(multi-nim)

    Description 聪聪和睿睿最近迷上了一款叫做分裂的游戏。该游戏的规则试:共有n个瓶子,标号为0,1,2.....n-1,第i个瓶子中 装有p[i]颗巧...

    attack
  • 2017 清北学堂 Day 6终极考试报告

    预计分数: 100+70+70 = 240 实际假分数 : 40+80+70= 190  in cena(好吧不得不承认这个分数,,,,,,=.=) 实际真分数...

    attack

扫码关注云+社区

领取腾讯云代金券