【CCPC】hdu 5547 Sudoku【dfs】

以你之姓@ 2022-08-10 03:44 106阅读 0赞

题目：[hdu 5547 Sudoku][]

题意：给你一个4\*4的数独，让你填其中未知的数  
坑点  
1：虽然斜线不用满足每个格子唯一，但是4\*4的格子分成4个，每个2\*2的格子必须满足数独  
2：答案不唯一的输出所有的情况，即暴力搜索的时候要回溯。

ac代码：

#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <map>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    const int N = 6;
    int mp[N][N];
    
    bool solve(int val ,int pel, int x)
    {
        bool flag[5];
        memset(flag,false,sizeof(flag));
        for(int i=0 ;i<4; ++i)
        {
            if(mp[val][i]!=-1)
                flag[ mp[val][i] ] = true;
            if(mp[i][pel]!=-1)
                flag[ mp[i][pel] ] = true;
        }
        int va = val /2,pe = pel / 2;
        for(int i = va*2; i<=va*2+1; ++i)
        {
            for(int j=pe*2; j<=pe*2+1; ++j)
            {
                if(mp[i][j]!=-1)
                    flag[ mp[i][j] ] = true;
            }
        }
        if(flag[ x ] == false)
            return true;
        return false;
    }
    void print()
    {
        for(int i=0;i<4;++i)
        {
            for(int j=0;j<4;++j)
                printf("%d",mp[i][j]);
            puts("");
        }
    }
    void dfs(int cal, int pel)
    {
    //    printf("you: %d %d %d\n",cal,pel,mp[cal][pel]);
        if(cal==4 && pel == 0)
        {
            print();return ;
        }
        int cal_next = cal,pel_next = pel;
        if(pel==3)
            ++cal_next,pel_next = 0;
        else   //注意些深搜代码不能想当然，逻辑一定要写清楚
            ++pel_next;
        if(mp[cal][pel] == -1)
        {
            for(int i=1;i<=4;++i)
            {
                if(solve(cal,pel,i)){
    //                printf("you: %d %d %d\n",cal,pel,i);
                    mp[cal][pel] = i;
                    dfs(cal_next, pel_next);
                }
            }
            mp[cal][pel] = -1;
        }
        else
            dfs(cal_next,pel_next);
    }
    int main()
    {
        freopen("Input.txt","r",stdin);
    //    freopen("OUt.txt","w",stdout);
        int T;
        scanf("%d",&T);
        for(int cas = 1; cas <=T; ++cas)
        {
            string s[5];
            for(int i=0;i<4;++i)
                cin>>s[i];
            for(int i=0; i<4; ++i)
            {
                for(int j=0; j<4; ++j)
                {
                    char c = s[i][j];
                    if(c!='*')
                        mp[i][j] = (c-'0');
                    else
                        mp[i][j] = -1;
                }
            }
            printf("Case #%d:\n",cas);
            dfs(0,0);
        }
        return 0;
    }

[hdu 5547 Sudoku]: http://acm.hdu.edu.cn/showproblem.php?pid=5547