首页 > 其他分享 >蓝桥杯填九宫幻方

蓝桥杯填九宫幻方

时间:2024-04-04 17:05:03浏览次数:19  
标签:填充 int 幻方 蓝桥 回溯 path include 九宫

通过回溯算法对未输入得数字进行全排列后,依次填入格子,判断是否符合条件。

可以更改幻方的大小,来填充任意幻方

#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
int board[3][3];//保存输入的幻方
int ans[3][3][3];//填充后符合条件的幻方
int tmp[3][3];//幻方高度,(多少个答案)
bool vist[9]={0};//临时变量来保存幻方,不能让输入的幻方board变化
int anstop=0;//记录该数字是否已填充
int nums[10];//保存输入幻方没有的数字
int N=0;//记录nums的元素个数
int path[10];//记录回溯元素
int pathtop=0;//回溯数组path的元素个数
void check()//判断填充幻方是否符合条件
{
    int i,j;
    int k=0;
    for(i=0;i<3;i++)//填充临时幻方tmp
    {
        for(j=0;j<3;j++)
        {
            if(board[i][j]==0)//填充没有输入的数字
                tmp[i][j]=path[k++];
            else
                tmp[i][j]=board[i][j];
        }
    }
    //幻方tmp的3行
    int a=tmp[0][0]+tmp[0][1]+tmp[0][2];
    int b=tmp[1][0]+tmp[1][1]+tmp[1][2];
    int c=tmp[2][0]+tmp[2][1]+tmp[2][2];
    //3列
    int d=tmp[0][0]+tmp[1][0]+tmp[2][0];
    int e=tmp[0][1]+tmp[1][1]+tmp[2][1];
    int f=tmp[0][2]+tmp[1][2]+tmp[2][2];
    //对角线
    int g=tmp[0][0]+tmp[1][1]+tmp[2][2];
    int h=tmp[0][2]+tmp[1][1]+tmp[2][0];
    if(a==b&&b==c&&c==d&&d==e&&e==f&&f==g&&g==h)
    {
        for(i=0;i<3;i++)
        {
            for(j=0;j<3;j++)
            {
                ans[i][j][anstop]=tmp[i][j];//符合条件,填入记录答案幻方ans
            }
        }
        anstop++;//答案个数++
    }
}
void backtracking()
{
    if(pathtop==N)//已经把nums的所有元素进行全排列
    {
        if(anstop>1)//答案个数多余2个,无需往后判断
        {
            printf("too many");
            exit(0);
        }
        check();//把path中的所有元素填入是否
        return;
    }
    int i;
    for(i=0;i<N;i++)//把nums的所有元素进行全排列
    {
        if(!vist[i])
        {
            path[pathtop++]=nums[i];
            vist[i]=1;
            backtracking();
            vist[i]=0;
            pathtop--;
        }
    }
}
int main(int argc, char *argv[])
{
  int i,j; 
  int hash[10]={0};
  for(i=0;i<3;i++)
  {
    for(j=0;j<3;j++)
    {
      scanf("%d",&board[i][j]);
      hash[board[i][j]]++;
    }
  }
  for(i=1;i<10;i++)//记录未输入的数字 
  {
    if(!hash[i])
      nums[N++]=i;
  }
  backtracking();
  for(i=0;i<3;i++)//输出答案 
  {
      for(j=0;j<3;j++)
          printf("%d ",ans[i][j][0]);
      printf("\n");
  }
  return 0;
}

标签:填充,int,幻方,蓝桥,回溯,path,include,九宫
From: https://blog.csdn.net/m0_73061507/article/details/137376186

相关文章

  • 蓝桥杯——翻硬币
    题目小明正在玩一个"翻硬币"的游戏。桌上放着排成一排的若干硬币。我们用*表示正面,用o表示反面(是小写字母,不是零)。比如,可能情形是:**oo***oooo;如果同时翻转左边的两个硬币,则变为:oooo***oooo。现在小明的问题是:如果已知了初始状态和要达到的目标状态每次只能同时翻转......
  • 2024SMU蓝桥训练1补题
    B-航班时间思路:地理知识--时差计算-东加西减。此处去程和返程方向相反,时差相加必然抵消。那么就可以知道实际飞行时间ps:这题有点奇怪,本地跑不过样例,交上去是AC。本地跑过样例,交上去RE,WA。RE好像是因为输入的格式不够严格..D-飞机降落思路:全排列枚举ordfs--dfs类似之前电科......
  • 第十三届蓝桥杯 C/C++ 大学 A 组 排列距离 康托和逆康托展开
    偏个题:算阶乘int可以到12,longlong可以到20(12和20,好记)背景知识康托展开原理n个数字或者字符全排列(每个元素只用一次),从小到大按照字典序排列好,从0开始给他们编号,从字符串映射到编号就是康托展开。从最高位向低位计算:若取小于最高位的数字,则后面任意取都是小于这个排列的若......
  • 2015年蓝桥杯六届省赛大学B组真题
    2015年蓝桥杯六届省赛大学B组真题1.奖券数目 #include <iostream>using namespace std;int ans;bool check(int i){  while(i){    if(i%10==4)return false;    i/=10;  }  return true;}int main(){  int ans=0;  for(int i=10......
  • 2017省赛蓝桥杯B组
    2017省赛蓝桥杯B组5.购物单查看代码查看代码 #include<iostream>usingnamespacestd;intmain(){//请在此输入您的代码doublesum=180.90*0.88+10.25*0.65+56.14*0.9+104.65*0.9+100.30*0.88+297.15*0.5+26.75*0.65+130.62*0.5+240.28*0.58+270.62*0.8+115.8......
  • Luogu P8710 [蓝桥杯 2020 省 AB1] 网络分析 题解 [ 绿 ] [ 带权并查集 ]
    原题分析本题由于从一个节点发信息,同一个集合内的所有点都会收到信息,显然是一道要求维护各节点间关系的题,因此采用并查集的数据结构进行求解。但由于维护关系的同时还要维护权值,所以采用带权并查集,它是一种能维护某个节点与其祖宗节点之间关系的数据结构。带权并查集找父亲的......
  • 洛谷:P8671 [蓝桥杯 2018 国 AC] 约瑟夫环
    时间限制1.00s     内存限制256.00MB     难易度:普及+/提高【题目描述】n 个人的编号是1∼n,如果他们依编号按顺时针排成一个圆圈,从编号是 1 的人开始顺时针报数。(报数是从 1 报起)当报到 k 的时候,这个人就退出游戏圈。下一个人重新从 1 开始报......
  • 纯小白蓝桥杯备赛笔记--DAY9(搜索)
    文章目录三道例题学会DFS剪枝什么是剪枝数字王国之军训排队--2942特殊的三角形--3008特殊的多边形--3075DFS基础回溯简介回溯法模版例题N皇后--1508小朋友崇拜圈--182全球变暖--178记忆化搜索简介斐波那契数列混境之地5-3820地宫取宝-216三道例题学会DFS剪枝什......
  • 备战蓝桥杯之填空题技巧(持续更新)
    前言本刷题系列是我为了蓝桥杯前几天可以再系统性思考一下真题所做,所以部分内容会很简洁。如果能够帮助到你,我也会很开心!!!题目110.工作时长-蓝桥云课(lanqiao.cn)截图:excel解题:首先先点击数据排序,排好序后每两行进行计算,用后面的一行减去前面的一行,合并前两个单元格往......
  • 【洛谷 P8695】[蓝桥杯 2019 国 AC] 轨道炮 题解(映射+模拟+暴力枚举+桶排序)
    [蓝桥杯2019国AC]轨道炮题目描述小明在玩一款战争游戏。地图上一共有NNN个敌方单位,可以看作2D平面上的点。其中第i......