[BZOJ2469][中山市选2010]简单数谜

发布于 2018-10-13  88 次阅读


Description

很多人都曾经听说过数独,但你是否听说过数谜(Karuro)呢?实际上,数谜是数独的更大(且更难)的兄弟问题,而且在日本也是非常受欢迎的。
数谜问题和填字游戏类似,不过它要填的不是文字而是数字。数谜游戏的目标是用1-9填满所有空格,且这些数字相加的和满足相应的要求(或者称为“提示”),且在同一栏(“栏”是指一些水平或者竖直的连续的空格,用于提示的格子不算空格)不能填重复的数字。当所有格子按要求被填满后,这个数谜就看作被解决了。图1和图2是一个可能的数谜游戏示例。
当然,直接求解数谜问题的话会比较困难。所以现在我们需要解决的是一个更简单的数谜问题。简单数谜的形状是一个(n+1)行乘(m+1)列的矩形。而简单数谜也只有两种要求,就是行要求和列要求,且分别处于第一行和第一列,其他格子则是空格,而左上角是忽略不计的。coolzzz同学爱好简单数谜,他已经给一些简单数谜填好了其中的一些空格。现在,他想寻求你的帮助,来帮他完成这些简单数谜。如图3所示,2和9是coolzzz同学已经填好的空格,图4则是一个基于图3 的一个可能的解答。

Input

输入包含多组测试数据。第一行包含一个正整数T,表示测试数据数目。每组数据第一行是n(n<10)和m(m<10),表示数谜的形状的大小。接下来一行有n个整数,是相应的行要求;然后一行是m个整数,是相应的列要求。接下来的n行每行有m个小于10的非负整数,0表示该空格还没有被填数字,其他表示coolzzz同学已经填好的数字。输入数据保证未填数字的空格不会超过16个。

Output

对于每组测试数据,输出若干行。如果基于coolzzz已填的结果,该数谜只有一个解,则输出该解;如果不止一个解,则输出一行“Not unique.”;如果没有解,则输出一行“No answer.”。

Sample Input

Sample Output

题解

一道简单的爆搜题,和数独比起来稍微复杂一点(然而代码量更少),比较坑爹的就是如果不加一句话的话全部超时,加上去了就只要32ms
我们每次填只关心当前行满不满足要求,最后结束的时候再来判断是不是合法
具体数组作用可以用一个表格体现

数组(变量)名称 数组(变量)作用
ans 用来存放最终的结果
num 用来统计有多少个答案
kakuro 初始状态以及之后搜索时的状态
x,y 要求的行、列和
X,Y 当前行、列有哪些数是用过的
val_x,val_y 当前状态的行、列和

代码


哇,你居然发现了这里!