一号热搜榜,为您提供最新的热搜资讯,热搜榜信息!

AHCPC2021省赛本科组题目-H数字迷盘_speciaIweak的博客-CSDN博客

娱乐热搜 作者:互联网收集 热度:400

AHCPC2021省赛本科组题目-H数字迷盘_speciaIweak的博客-CSDN博客

H. 数字谜盘

描述

有一个方盘,被分割成了 4 行 4 列共 16 个方格。方盘的主人 Jasonare 最近突然

萌生了一个问题,但是任他怎么冥思苦想都得不到答案,他非常沮丧,以至于最

近这段时间茶饭不思,他的好朋友 May 看到他这样非常担心,打算把这个问题晒

AHCPC2021省赛本科组题目-H数字迷盘_speciaIweak的博客-CSDN博客

出来,并承诺若有人能将此问题解决,便可以将他珍藏多年的钢铁侠手办限量版

赠与对方。

可以看到问题是这样的——你需要在方盘中 4*4 的方格中填数,且填入的数字必

须为正整数,Jasonare 事先规定了每一行数字的总和、每一列数字的总和以及

两条对角线数字的总和。另外在你开始填数前,他在方盘的任意四个格子事先填

好了数字。请问你能否将这个方盘中的方格填满数字,并且满足每一行数字的总

和、每一列数字的总和以及两条对角线的总和都与 Jasonare 规定的相同。

输入

首先在第一行输入 10 个数字分别表示每一行数字的总和、每一列数字的总和以

及两条对角线数字的总和。然后再输入 12 个数字,分 4 行,每一行输入 3 个数

字(i,j,k),表示 Jasonare 事先在(i,j)这个位置填入数字 k,即 M(i,j) = k。

注意:

1、 行与列的下标均从 0 开始;

2、 对于 100%的数据,任何行,列或对角线之和不会超过 200;

3、 你可以假设输入总是存在解决方案,即不存在无解的情况。

输出

输出应该包括一个 4*4 的数字矩阵,表示在 4*4 的方格中填入的数字。

dfs暴力搜索, 回溯 + 丑陋代码,题能做,只能做一点点

大家看个乐呵,不要抄我的代码啦

硬着头皮写的回溯

sum 0 -3 表示还未处理的4行的和

sum 4 - 7 表示还未处理的4列的和

sum 8 正对角

sun 9 反对角

cnt 下标含义和sum一致 表示还未为处理的个数

自己可以列几个测试案例自己看看

calcu函数的参数val = 1表示回溯 -1表示搜索

这是以前的代码哦

标签: 博客     AHCPC2021     省赛