F. 涂满它！
内存限制：256 MiB时间限制：1000 ms标准输入输出 题目类型：传统评测方式：文本比较题目描述
Flood-it是谷歌+平台上的非常好玩的一款游戏，游戏界面如下所示：
在游戏开始时，系统将随机生成N×N的方形区域，并且区域内的每个网格都被涂成了六种颜色中的一种。
玩家从左上角开始游戏。
在每个步骤中，玩家选择一种颜色并将与左上角连通的所有格子（包括左上角）都变成该种颜色。
这里连通定义为：两个格子有公共边，并且颜色相同。
通过这种方式，玩家可以从左上角开始将所有格子都变为同一种颜色。
下图显示了4×4游戏的最早步骤（颜色标记为0到5）：
请你求出，给定最初区域以后，最少要多少步才能把所有格子的颜色变成一样的。
输入格式
输入包含不超过20个测试用例。
每个测试用例，第一行包含一个整数N，表示方形区域大小。
接下里N行，每行包含N个整数（0-5），第 i 行第 j 个整数表示第 i 行第 j 列的格子的颜色。
当输入样例N=0时，表示输入终止，该用例无需处理。
输出格式
每个测试用例输出一个占据一行的整数，表示所需最少步数。
样例
样例输入
2
0 0
0 0
3
0 1 2
1 1 2
2 2 1
0
样例输出
0
3
数据范围与提示
2≤N≤8
思路分析
事实证明，我现在还并没有写出题目。。。
但是这并不妨碍我理清思路在写题解。。。
首先我们知道这是一道搜索题，然后还是一道A*，我们并不明确最后是以什么颜色结束的，所以一定不是双向搜索
一共有六种颜色，最多有64个格子。
我们知道，最好的情况就是所有对角线上的颜色都是一样的，这样我们就只需要n - 1的次数就能成功。
我首先尝试寻找剩下的没有填的格子中一共有多少种不同的颜色，然后以这一点来指定规则。
我们用iddfs来解决主要问题，dep的最大值肯定不超过n*n，所以无需担心无穷枚举下去，总是会找到答案的。
又仔细思考过后，我们的思路会更加清晰
1.A*
寻找没有走过的格子中有多少个颜色不一样，这就是我们的h
2.Dye染色
我们用Vis数组来标记，0表示这个点没有走到过，1表示这个点已经被同色了，不管后面怎么改动（1，1），它都会被一起更改，2表示我们在某个是1的点可以走到2，这样我们下次染色时，这个点是2且与更换的颜色相同，就可以直接更改了。
3.A_iddfs
常规操作：先预判，如果不满足条件的话就直接return，再写出口。分别枚举5个颜色，对地图进行染色。（我们大多数人可能都懂，但是代码要怎么具体实现呢？）
代码部分
#include <bits/stdc++.h>
using namespace std ;
int a[10][10], n, dep = 0, s ;
int Vis[10][10] ;
int rx[5] = {-1, 1, 0, 0} ;
int ry[5] = {0, 0, -1, 1} ;
bool flag = 0 ;
int h()
{
int sum = 0, cl[7] ;
memset(cl, 0, sizeof(cl)) ;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
if(Vis[i][j] != 1 && !cl[a[i][j]]){//!这里的Vis[i][j]可以等于2，所以不能只判零
sum ++ ;
cl[a[i][j]] = 1 ;
}
}
}
return sum ;
}
bool out(int x, int y){
if(x <= 0 || x > n || y <= 0 || y > n) return false ;
return true ;
}
void Dye(int c, int x, int y){
Vis[x][y] = 1 ;
for(int i = 0; i < 4; i ++)
{
int nx = x + rx[i], ny = y + ry[i] ;
if(out(nx, ny) == false || Vis[nx][ny]) continue ;
Vis[nx][ny] = 2 ;
if(a[nx][ny] == c){
Dye(c, nx, ny) ;
}
}
return ;
}
void A_iddfs(int tot)
{
int num = h() ;
if(tot + num > dep) return ;
if(num == 0){
flag = 1 ;
return ;
}
int ori[10][10] ;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
ori[i][j] = Vis[i][j] ;
}
}
for(int c = 0; c <= 5; c ++){
bool f = 0 ;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
if(Vis[i][j] == 2 && a[i][j] == c){
Dye(c, i, j) ;
f = 1 ;//更改了颜色
}
}
}
if(f == 1) A_iddfs(tot + 1) ;
if(flag == 1) return ;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
Vis[i][j] = ori[i][j] ;//相当于回溯，如果不填充这个颜色就还原。
}
}
}
}
int main()
{
while(scanf("%d", &n) != EOF && n != 0)
{
flag = 0 ;
dep = 0 ;
memset(Vis, 0, sizeof(Vis)) ;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
scanf("%d", &a[i][j]) ;
}
}
Dye(a[1][1], 1, 1) ;
while(!flag){
A_iddfs(0) ;
dep ++ ;
}
printf("%d\n", dep - 1) ;
}
return 0 ;
}
————————Hellioca 2023-01-1719:52:48 归零——一切过往，皆为序章。所有未来，皆是可期。
标签：10,颜色,格子,水叮当,int,题解,nx,涂色,return From： https://www.cnblogs.com/ybC202444/p/17058615.html