Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 3041: 水叮当的舞步

题目链接

传送门

Description

水叮当得到了一块五颜六色的格子形地毯作为生日礼物,更加特别的是,地毯上格子的颜色还能随着踩踏而改变。
为了讨好她的偶像虹猫,水叮当决定在地毯上跳一支轻盈的舞来卖萌~~~
地毯上的格子有N行N列,每个格子用一个0~5之间的数字代表它的颜色。
水叮当可以随意选择一个0~5之间的颜色,然后轻轻地跳动一步,左上角的格子所在的联通块里的所有格子就会变成她选择的那种颜色。这里连通定义为:两个格子有公共边,并且颜色相同。
由于水叮当是施展轻功来跳舞的,为了不消耗过多的真气,她想知道最少要多少步才能把所有格子的颜色变成一样的。

Input

每个测试点包含多组数据。
每组数据的第一行是一个整数N,表示地摊上的格子有N行N列。
接下来一个N*N的矩阵,矩阵中的每个数都在0~5之间,描述了每个格子的颜色。
N=0代表输入的结束。

Output

对于每组数据,输出一个整数,表示最少步数。

Sample Input

2

0 0

0 0

3

0 1 2

1 1 2

2 2 1

0

Sample Output

0

3

HINT

对于100%的数据,N<=8,每个测试点不多于20组数据。

第二组样例解释

0 1 2
1 1 2
2 2 1


1 1 2
1 1 2
2 2 1


2 2 2
2 2 2
2 2 1


1 1 1
1 1 1
1 1 1

想说的话

实在不明白讨好偶像跟这题有什么关系
卖萌就算了呗 干嘛把我们这些无辜的人扯上
水叮当那么可爱这题我还是好好做做吧
水叮当偶像是虹猫不是我不开心
水叮当是谁我不认识

题解

看到这题其实N<=8的时候我第一个考虑的是状压
然而这题是作为搜索的例题出现的
所以状压做法我就没考虑
解法I:直接迭代搜索
期望得分:20分
不给代码了
解法II:考虑ID Astar
这个Astar加在哪里是一个问题
在迭代搜索中
最浪费时间的无非就是找所谓的联通块的时间
所以这个Astar就在这里做文章
我们引入一个N*N的mark数组。左上角的格子所在的联通块里的格子标记为1。左上角联通块周围一圈格子标记为2,其它格子标记为0。如果某次选择了颜色c,我们只需要找出标记为2并且颜色为c的格子,向四周扩展,并相应地修改mark标记,就可以不断扩大标记为1的区域,最终如果所有格子标记都是1,那么显然找到了答案。
期望得分:90-100分(最好还是有点卡常
bzoj当然是没有问题了
但是codevs上面就不好说了

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏