109徐守佳

用户名：dotcpp0787174

访问量：938

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	922
经　　验	3466
参赛次数	1
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

[信息学奥赛一本通T1551-维护序列] 线段树
浏览：15

[信息学奥赛一本通T1550-花神游历各国] 区间更新负优化
浏览：15

[蓝桥杯2022年第十三届决赛真题-最大数字] 贪心+dfs
浏览：51

你可能喜欢

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

[蓝桥杯2017年第八届真题-九宫幻方] DFS

　　作者: 109徐守佳　　　　发表时间：2024-09-13 23:08:41 浏览：23　|　评论：1　

原题链接：蓝桥杯2017年第八届真题-九宫幻方

## 思路:先找出未用的数字有哪些,再进行深搜找出全排列的数,然后放入九宫格中,最后进行检测看是否符合题意
```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N = 3 * 1e6 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;
const int MA = 15;

bool st[MA]; //标记数字是否被用
int g[MA][MA]; //存储九宫格数字
int note[MA][MA]; //保存初始九宫格状态的副本
int Ans[MA][MA]; //保存答案九宫格副本
int path[MA]; //路径数组
int sum = 0,ans = 0; 
bool flag; //用于判断是否有多解
bool check() //判断九宫格每一行、每一列和每一条对角线的和是否相同
{
    int state = 0;
    for(int i=1;i<=3;i++)
    {
        state += g[i][1];
    }
    int soure = state; 
    for(int i=1;i<=3;i++)
    {
        state -= g[i][2];
    }
    if(state!=0) return false;
    state = soure;
    for(int i=1;i<=3;i++)
    {
        state -= g[i][3];
    }
    if(state!=0) return false;
    state = soure;
    for(int i=1;i<=3;i++)
    {
        state -= g[1][i];
    }
    if(state!=0) return false;
    state = soure;
    for(int i=1;i<=3;i++)
    {
        state -= g[2][i];
    }
    if(state!=0) return false;
    state = soure;
    for(int i=1;i<=3;i++)
    {
        state -= g[3][i];
    }
    if(state!=0) return false;
    state = soure;
    for(int i=1;i<=3;i++)
    {
        state -= g[i][i];
    }
    if(state!=0) return false;
    state = soure;
    for(int i=1;i<=3;i++)
    {
        state -= g[i][4-i];
    }
    if(state!=0) return false;
    state = soure;
    return true;
}
//搜索
void dfs(int u)
{
    if(u > sum) return;
    if(ans>1)
    {
        flag = false; //解超过1个置为false
        return;
    }
    if(u == sum)
    {
        int k = 0;
        for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=3;j++)
            {
                if(g[i][j] == 0)
                {
                    g[i][j] = path[k++]; 
					//给待检测的九宫格用路径数组赋值
                }
            }
        }
        if(check())
        {
            ans++; 找到解,可行解+1
            flag = true;
            memcpy(Ans,g,sizeof Ans); //copy给ans数组
            memcpy(g,note,sizeof g); //还原九宫格的初始状态
            return;
        }
        memcpy(g,note,sizeof g);//还原九宫格的初始状态
        return;
    }
    for(int i=1;i<=9;i++) //类似于全排列问题搜索出所有组合数
    {
        if(!st[i])
        {
            st[i] = true;
            path[u] = i;
            dfs(u+1);
            st[i] = false;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
        {
            cin>>g[i][j];
            if(g[i][j]==0) sum++;
            st[g[i][j]] = 1; //这个数字已用
        }
        memcpy(note,g,sizeof note); //copy给note数组备用
    dfs(0);
    if(flag)
    {
        for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=3;j++)
            {
                cout<<Ans[i][j]<<' ';
            }
            cout<<endl;
        }
    }
    else cout<<"Too Many"<<endl;
    return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

yxy

%%% orz

2024-09-17 01:02:10

109徐守佳

TA的其他文章

你可能喜欢

C语言训练-阿姆斯特朗数（C语言代码）

众数问题（C++代码）

点我有惊喜！你懂得！

C语言训练-邮票组合问题* （C语言代码）......

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

[蓝桥杯2017年第八届真题-九宫幻方] DFS

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C二级辅导-同因查找（C语言代码）

C二级辅导-公约公倍（C语言代码）

输出九九乘法表（C语言代码）

109徐守佳

TA的其他文章

你可能喜欢

C语言训练-阿姆斯特朗数 （C语言代码）

众数问题 （C++代码）

点我有惊喜！你懂得！

C语言训练-邮票组合问题* （C语言代码）......

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

[蓝桥杯2017年第八届真题-九宫幻方] DFS

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C二级辅导-同因查找 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

输出九九乘法表 （C语言代码）

C语言训练-阿姆斯特朗数（C语言代码）

众数问题（C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

　　评论区

C二级辅导-同因查找（C语言代码）

C二级辅导-公约公倍（C语言代码）

输出九九乘法表（C语言代码）