Wikioi 1174 靶形数独
小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他
们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z 博士请教，
Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。
靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有9 个3 格宽×3 格
高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些
数字，利用逻辑推理，在其他的空格上填入1 到9 的数字。每个数字在每个小九宫格内不能
重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即
每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。
上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红
色区域）每个格子为9 分，再外面一圈（蓝色区域）每个格子为8 分，蓝色区域外面一圈（棕
色区域）每个格子为7 分，最外面一圈（白色区域）每个格子为6 分，如上图所示。比赛的
要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取
更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字
的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为2829。游
戏规定，将以总分数的高低决出胜负。
由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能
够得到的最高分数。
一共 9 行。每行9 个整数（每个数都在0—9 的范围内），表示一个尚未填满的数独方
格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。
输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。
【输入输出样例 1】
7 0 0 9 0 0 0 0 1
1 0 0 0 0 5 9 0 0
0 0 0 2 0 0 0 8 0
0 0 5 0 2 0 0 0 3
0 0 0 0 0 0 6 4 8
4 1 3 0 0 0 0 0 0
0 0 7 0 0 2 0 9 0
2 0 1 0 6 0 8 0 4
0 8 0 5 0 4 0 1 2
【输入输出样例 2】
0 0 0 7 0 2 4 5 3
9 0 0 0 0 8 0 0 0
7 4 0 0 0 5 0 1 0
1 9 5 0 8 0 0 0 0
0 7 0 0 0 0 0 2 5
0 3 0 5 7 9 1 0 8
0 0 0 6 0 1 0 0 0
0 6 0 9 0 0 0 0 1
0 0 0 0 0 0 0 0 6
【输入输出样例 1】
2829
【输入输出样例 1】
2852
【数据范围】
40%的数据，数独中非0 数的个数不少于30。
80%的数据，数独中非0 数的个数不少于26。
100%的数据，数独中非0 数的个数不少于24。
我们看每个空白的格子，看看它还可以填几个数。 如果是我们在做数独的话，我们显然会先从可以填的数少的格子开始试。 所以我们可以找出每个格子可以填几个数，然后排序，先从可以填的数少的格子开始搜。
可行性剪枝：显然，这道题的不合法解就是同一行或同一列或同一个九宫格出现了相同数字，所以我们只需要知道一个格子可以填哪些数，然后只搜索这些可以填的数就可以了
最优性剪枝： 如果当前已有得分+未来可能得到的最大的分<=当前已得到的最大总分（已经找到的合法解中的最优解），则直接退出。显然未来得分不可能超过（没有填的格子数*90）。
我们再想一下，爆搜的大部分时间都浪费在了哪？ 在找这个格子能够填哪些数。 这个问题能够快速解决吗？ 搜索问题中，解决这种问题有一个通用方法，就是：位运算！
既然每行每列每个九宫格一共就9个数，我们就记录一下哪些数没用过。 一共9个数，想到了啥？ 2^9 压位！ 若第i位的二进制为1，则表示第i个数在这一行/这一列/这个九宫格还没有出现过，还可以使用。
那我们怎么找一个格子所在的该行该列该九宫格都还未出现过的数字？ 三个信息and一下就可以了。 假设得到的是x，那么，x的二进制上为1的就是我们可以在这个格子里填的数字。
怎么遍历可以填的所有数字？也就是x的所有二进制位1的位？显然不能一位一位的遍历。。。。那样就成了暴力了。。。。我们希望只遍历二进制是1的位。 For (;x!=0;x-=x&-x) { y=log[x&-x]+1;//+1是因为数字是1~9，不是0~8 ……. ……. }
注意，在给这个格子选择某个数填上，dfs进入下一层之前，我们要先修改该行该列该九宫格还能填的剩余数字。 Dfs回到上一层之后，也记得修改该行该列该九宫格还能填的剩余数字。 For (;x!=0;x-=x&-x) { y=log[x&-x]+1; 记录这个格子填y，将该格子得分加入当前总分，并将该行该列该九宫格记录的还能填的数字信息and (2^10-1-(x&-x)) dfs(………); 将该格子得分从当前总分中减去，并将该行该列该九宫格记录的还能填的数字信息or (x&-x) }
代码：
①自己写的，用了map
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #include<vector> 8 #define mx 111 9 #define maxint 10000 10 using namespace std; 11 struct Node{ 12 int x; 13 int y; 14 int a; 15 }; 16 vector<Node> node; 17 int a[mx][mx],line[mx],col[mx],pal[mx],block[mx][mx],ok[mx][mx],sub[mx],Log[maxint],lft,maxans,ansleft; 18 int s_jud[9][9] = {6,6,6,6,6,6,6,6,6, 19 6,7,7,7,7,7,7,7,6, 20 6,7,8,8,8,8,8,7,6, 21 6,7,8,9,9,9,8,7,6, 22 6,7,8,9,10,9,8,7,6, 23 6,7,8,9,9,9,8,7,6, 24 6,7,8,8,8,8,8,7,6, 25 6,7,7,7,7,7,7,7,6, 26 6,6,6,6,6,6,6,6,6,}; 27 int g_jud[9][9] = {1,1,1,2,2,2,3,3,3, 28 1,1,1,2,2,2,3,3,3, 29 1,1,1,2,2,2,3,3,3, 30 4,4,4,5,5,5,6,6,6, 31 4,4,4,5,5,5,6,6,6, 32 4,4,4,5,5,5,6,6,6, 33 7,7,7,8,8,8,9,9,9, 34 7,7,7,8,8,8,9,9,9, 35 7,7,7,8,8,8,9,9,9,}; 36 bool cmp(Node x,Node y){ 37 return x.a < y.a; 38 } 39 void init(){ 40 lft = maxans = ansleft = 0; 41 int vd = pow(2,9) - 1,acc; 42 memset(line,vd,sizeof(line)); 43 memset(col,vd,sizeof(col)); 44 memset(block,vd,sizeof(block)); 45 memset(pal,vd,sizeof(pal)); 46 memset(ok,0,sizeof(ok)); 47 for(int c = 1,x = 0;c < maxint;c *= 2,x++) Log[c] = x; 48 for(int i = 1;i <= 9;i++) sub[i] = vd - pow(2,i-1); 49 for(int i = 1; i <= 9;i++){ 50 for(int j = 1;j <= 9;j++){ 51 cin>>a[i][j]; 52 if(a[i][j]){ 53 lft++; 54 line[i] = line[i] & sub[a[i][j]]; 55 col[j] = col[j] & sub[a[i][j]]; 56 pal[g_jud[i-1][j-1]] = pal[g_jud[i-1][j-1]] & sub[a[i][j]]; 57 ok[i][j] = 1; 58 ansleft += a[i][j] * s_jud[i-1][j-1]; 59 } 60 } 61 } 62 lft = 81 - lft; 63 Node temp; 64 for(int i = 1;i <= 9;i++){ 65 for(int j = 1;j <= 9;j++){ 66 block[i][j] = line[i] & col[j] & pal[g_jud[i-1][j-1]]; 67 acc = 0; 68 for(int x = block[i][j];x!=0;x-=x&-x) acc++; 69 if(ok[i][j]) continue; 70 temp.y = i; 71 temp.x = j; 72 temp.a = acc; 73 node.push_back(temp); 74 75 } 76 } 77 sort(node.begin(),node.end(),cmp); 78 } 79 void opt_init(){ 80 for(int i = 0;i <lft;i++){ 81 cout<<"No."<<i<<" ("<<node[i].x<<","<<node[i].y<<") "<<node[i].a<<endl; 82 } 83 } 84 int dfs(int deep,int score){ 85 if(deep > lft){ 86 maxans = max(score,maxans); 87 return score; 88 } 89 90 int nowx = node[deep-1].x,nowy = node[deep-1].y,test; 91 int x = line[nowy] & col[nowx] & pal[g_jud[nowy-1][nowx-1]],y; 92 for(;x!=0;x-=x&-x){ 93 y=Log[x&-x]+1; 94 score += y * s_jud[nowy-1][nowx-1]; 95 test = pow(2,10) - 1 - (x&-x); 96 line[nowy] = line[nowy] & test; 97 col[nowx] = col[nowx] & test; 98 pal[g_jud[nowy-1][nowx-1]] = pal[g_jud[nowy-1][nowx-1]] & test; 99 dfs(deep+1,score); 100 score -= y * s_jud[nowy-1][nowx-1]; 101 line[nowy] = line[nowy] | (x&-x); 102 col[nowx] = col[nowx] | (x&-x); 103 pal[g_jud[nowy-1][nowx-1]] = pal[g_jud[nowy-1][nowx-1]] | (x&-x); 104 } 105 } 106 int main(){ 107 init(); 108 dfs(1,0); 109 if(maxans) cout<<maxans + ansleft<<endl; 110 else cout<<-1<<endl; 111 return 0; 112 }
②ida*
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #define MAX(a,b) a>b?a:b 6 using namespace std; 7 8 int Map[10][10] = {0}; //这个就不用解释了吧 9 int Nine[10][10] = {0}; //小九宫格里每个数的使用标记，小九宫格的编号左到右，上到下，1，2,3,4,5,6,7,8,9 10 int Line[10][10] = {0}; //行上每个数的使用标记 11 int Row[10][10] = {0}; //列上每个数的使用标记 12 int FQueL[10] = {0}; //被启发后的行访问顺序 13 int FQueR[10] = {0}; //被启发后的列访问顺序 14 int Value[10][10] = {0}; //地图各点的价值因子 15 int QueL[81] = {0}; // 16 int QueR[81] = {0}; //与上面那个，是根据启发后制定的搜索顺序的行列参数 17 int QLen = 0; //搜索队列的长度 18 int Ans = -1; //最优解 19 int Count = 0; //废物变量，纪念原来我错误的写法，懒得删掉了 20 21 int Swap(int *a,int *b) 22 { 23 int o=*a; 24 *a=*b; 25 *b=o; 26 } 27 28 void Heu() //启发函数 29 { 30 for(int i=1;i<=9;++i){ 31 FQueL[i] = i; 32 FQueR[i] = i; 33 } 34 35 for(int i=1;i<=8;++i) 36 for(int j=9;j>=i+1;--j){ 37 if(Line[FQueL[j]][0] > Line[FQueL[j-1]][0]) 38 Swap(&FQueL[j],&FQueL[j-1]); 39 if(Row[FQueR[j]][0] > Row[FQueR[j-1]][0]) 40 Swap(&FQueR[j],&FQueR[j-1]); 41 } 42 for(int i=1;i<=9;++i) 43 for(int j=1;j<=9;++j) 44 if(Map[FQueL[i]][FQueR[j]] == 0){ 45 QueL[QLen]=FQueL[i]; 46 QueR[QLen]=FQueR[j]; 47 QLen++; 48 } 49 // for(int i=1;i<=9;++i) 50 // cout<<FQueL[i]<<' '<<Line[FQueL[i]][0]<<' '<<FQueR[i]<<' '<<Row[FQueR[i]][0]<<endl; 51 } 52 53 int belong(int i,int j) //判断行列参数为i，j的点属于哪一个九宫格。 54 { 55 int xt = 0,yt = 0; 56 for(int k=6;k>=0;k-=3){ 57 if(i-k>0){xt=(k+3)/3;break;} 58 } 59 for(int k=6;k>=0;k-=3){ 60 if(j-k>0){yt=(k+3)/3;break;} 61 } 62 // cout<<xt<<' '<<yt<<' '<<xt+(yt-1)*3<<endl; 63 // cout<<i<<' '<<j<<' '<< yt+(xt-1)*3 <<endl; 64 return yt+(xt-1)*3; 65 } 66 67 int Score() //成绩计算 68 { 69 int Temp = 0; 70 for(int i=1;i<=9;++i) 71 for(int j=1;j<=9;++j) 72 Temp += Map[i][j]*Value[i][j]; 73 Ans = MAX(Temp,Ans); 74 // cout<<Ans<<endl; 75 } 76 77 int Dfs(int step) //深度优先搜索主体 78 { 79 // cout<<step<<' '<<81-Count<<endl; 80 // for(int i=1;i<=9;++i,cout<<endl) 81 // for(int j=1;j<=9;++j) 82 // cout<<Map[i][j]<<' '; 83 if(step == QLen){Score();return 0;} 84 if(!Map[QueL[step]][QueR[step]]) 85 for(int k=1;k<=9;++k){ 86 if(!Nine[belong(QueL[step],QueR[step])][k]) 87 if(!Line[QueL[step]][k] && !Row[QueR[step]][k]){ 88 //Heu(); 89 // cout<<FQueL[i]<<' '<<FQueR[j]<<' '<<k<<endl; 90 Map[QueL[step]][QueR[step]] = k; 91 Nine[belong(QueL[step],QueR[step])][k] = 1; 92 Line[QueL[step]][k]=Row[QueR[step]][k] = 1; 93 Line[QueL[step]][0]++;Row[QueR[step]][0]++; 94 Dfs(step+1); 95 Map[QueL[step]][QueR[step]] = 0; 96 Nine[belong(QueL[step],QueR[step])][k] = 0; 97 Line[QueL[step]][k]=Row[QueR[step]][k] = 0; 98 Line[QueL[step]][0]--;Row[QueR[step]][0]--; 99 } 100 } 101 return 0; 102 } 103 104 int main() 105 { 106 for(int i=1;i<=5;++i) 107 for(int j=1+(i-1);j<=9-(i-1);++j){ 108 Value[i][j] = 6+(i-1); 109 Value[9-(i-1)][j] = 6+(i-1); 110 Value[j][9-(i-1)] = 6+(i-1); 111 Value[j][i] = 6+(i-1); 112 } //init value 对价值表的初始，好像其他人都是直接用{}初始的....... 113 // for(int i=1;i<=9;++i,cout<<endl) 114 // for(int j=1;j<=9;++j) 115 // cout<<Value[i][j]<<' '; 116 for(int i=1;i<=9;++i) 117 for(int j=1,x,y;j<=9;++j){ 118 scanf("%d",&Map[i][j]); 119 if(Map[i][j] != 0 ){ 120 Line[i][Map[i][j]] = 1; 121 Line[i][0]++; 122 Row[j][Map[i][j]] = 1; 123 Row[j][0]++; 124 Nine[belong(i,j)][Map[i][j]] = 1; 125 Count++; 126 } 127 } 128 129 // for(int i=1;i<=9;++i,cout<<endl) 130 // for(int j=1;j<=9;++j) 131 // cout<<Nine[i][j]; 132 133 Heu(); 134 Dfs(0); 135 136 cout<<Ans; 137 return 0; 138 }
Wikioi 1005 生日礼物
9月12日是小松的朋友小寒的生日。小松知道小寒特别喜欢蝴蝶，所以决定折蝴蝶作为给小寒的生日礼物。他来到了PK大学最大的一家地下超市，在超市里，小松找到了n种可以用来折纸的本子。每种类型的本子里有若干不同颜色的纸若干张，当然同种类型的本子一定是完全一样的，而不同种类型的本子不一定完全不一样。他统计了一下，这里总共有n种不同类型的可以用来折纸的本子，每种本子各有bi本，所有的纸中有m种颜色是小寒所喜欢的颜色。小松希望他折的每种颜色的蝴蝶的数目是一样的。换句话说，小松必须折m*k只蝴蝶，其中k代表每种颜色蝴蝶的数目，这个数由小松自己来决定。但是小松又不能浪费纸，也就是说他买的本子中，只要是小寒喜欢的颜色的纸都要被折成蝴蝶。于是问题来了，每种类型的本子应该各买多少本，才能折出这m*k只蝴蝶呢？当然，由于小松是个很懒的人，他希望折的蝴蝶数目越少越好，只要表达了心意就可以了（也就是不能1只也不折）。而如果小松总共必须折1000只以上的蝴蝶才能满足要求，那么他就宁愿换一种礼物的方案了。
输入的第一行包含2个整数n（1≤n≤8），m（1≤m≤10）。表示有n种不同类型的本子和m种小寒喜欢的颜色。接下来一个n*m的矩阵。第i行第j列的整数aij表示在第i种类型的本子中包含小寒喜欢的颜色j的纸有aij（1≤aij≤100）张。再接下来的一排n个整数b1到bn，表示每种颜色的本子在超市中有多少本（1≤bi≤5）。
输出包含一个整数，表示小松最少需要折的蝴蝶数目，如果该数目超过1000，则输出”alternative!”。（由于可能存在多种买本子的方案，所以这里就不要求输出具体方案了）
2 3
2 1 2
4 8 4
5 5
36
思路：
简单深搜，枚举本子数，达到递归边界判定，如果各种蝴蝶都相等并且每种蝴蝶的数目小于目前的方案，就记录，到最后再输出
代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<string> 6 using namespace std; 7 int n,m,a[20][20],b[20],ans[20],tot,jud[10000]; 8 int dfs(int deep,int add){ 9 if(add >= tot) return false; 10 if(deep == n){ 11 int cmp = 0; 12 if(add == 0) return false; 13 if(jud[add]) return false; 14 for(int i = 2;i <= m;i++){ 15 for(int j = 1;j <= n;j++){ 16 cmp += a[j][i] * ans[j]; 17 } 18 if(cmp!=add) return false; 19 cmp = 0; 20 } 21 tot = min(tot,add); 22 jud[add] = 1; 23 return true; 24 } 25 for(int i = 0;i <= b[deep+1];i++){ 26 ans[deep+1] = i; 27 dfs(deep+1,add + ans[deep+1] * a[deep+1][1]); 28 } 29 return false; 30 } 31 int main(){ 32 tot = 10000000; 33 cin>>n>>m; 34 for(int i = 1;i <= n;i++){ 35 for(int j = 1;j <= m;j++){ 36 cin>>a[i][j]; 37 } 38 } 39 for(int i = 1;i <= n;i++) cin>>b[i]; 40 dfs(0,0); 41 if(tot*m <= 1000) cout<<tot*m; 42 else cout<<"alternative!"; 43 return 0; 44 }
Tyvj 1266 费解的开关
描述
我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式
以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
对于30%的数据，n<=5；
对于100%的数据，n<=500。
输出格式
对于某一个游戏初始状态，若6步以内无法使所有灯变亮，请输出“-1”。
测试样例1
输入
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
输出
3
2
-1
1 #include<cstring> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<iostream> 5 using namespace std; 6 7 typedef int array[6]; 8 array a,b[6],c[6]; 9 int n,ans; 10 void Init() 11 { 12 char str[6]; 13 for (int i=1;i<=5;i++) 14 { 15 scanf("%s",str); 16 for (int j=1;j<=5;j++) 17 b[i][j]=str[j-1]-'0'; 18 } 19 } 20 int work() 21 { 22 int dep=0; 23 for (int i=1;i<=5;i++) 24 if (a[i]==1) 25 { 26 dep++; 27 c[1][i]^=1; c[2][i]^=1; 28 if (i>1) c[1][i-1]^=1; 29 if (i<5) c[1][i+1]^=1; 30 } 31 for (int i=2;i<=5;i++) 32 for (int j=1;j<=5;j++) 33 if (c[i-1][j]==0 && dep<=6) 34 { 35 dep++; 36 c[i][j]^=1; c[i-1][j]^=1; 37 if (j>1) c[i][j-1]^=1; 38 if (j<5) c[i][j+1]^=1; 39 if (i<5) c[i+1][j]^=1; 40 } 41 if (dep>=7) return 7; 42 for (int i=1;i<=5;i++) 43 if (c[5][i]==0) return 7; 44 return dep; 45 } 46 void solve() 47 { 48 Init(); 49 ans=0xFFFFFFF; 50 for (int a1=0;a1<=1;a1++) 51 for (int a2=0;a2<=1;a2++) 52 for (int a3=0;a3<=1;a3++) 53 for (int a4=0;a4<=1;a4++) 54 for (int a5=0;a5<=1;a5++) 55 { 56 memcpy(c,b,sizeof(c)); 57 a[1]=a1; a[2]=a2; a[3]=a3; a[4]=a4; a[5]=a5; 58 int step=work(); 59 if (step<ans) ans=step; 60 if (ans==2) 61 { 62 printf("2 "); 63 return ; 64 } 65 } 66 if (ans<=6) printf("%d ",ans); 67 else printf("-1 "); 68 } 69 int main() 70 { 71 scanf("%d",&n); 72 for (int test=1;test<=n;test++) solve(); 73 return 0; 74 }
水叮当得到了一块五颜六色的格子形地毯作为生日礼物，更加特别的是，地毯上格子的颜色还能随着踩踏而改变。
为了讨好她的偶像虹猫，水叮当决定在地毯上跳一支轻盈的舞来卖萌~~~
地毯上的格子有N行N列，每个格子用一个0~5之间的数字代表它的颜色。
水叮当可以随意选择一个0~5之间的颜色，然后轻轻地跳动一步，左上角的格子所在的联通块里的所有格子就会变成她选择的那种颜色。这里连通定义为：两个格子有公共边，并且颜色相同。
由于水叮当是施展轻功来跳舞的，为了不消耗过多的真气，她想知道最少要多少步才能把所有格子的颜色变成一样的。
每个测试点包含多组数据。
每组数据的第一行是一个整数N，表示地摊上的格子有N行N列。
接下来一个N*N的矩阵，矩阵中的每个数都在0~5之间，描述了每个格子的颜色。
N=0代表输入的结束。
对于每组数据，输出一个整数，表示最少步数。
2
0 0
0 0
3
0 1 2
1 1 2
2 2 1
0
0
3
对于30%的数据，N<=5
对于50%的数据，N<=6
对于70%的数据，N<=7
对于100%的数据，N<=8，每个测试点不多于20组数据。
第二组样例解释：
0 1 2 1 1 2 2 2 2 1 1 1
1 1 2 --> 1 1 2 --> 2 2 2 --> 1 1 1
2 2 1 2 2 1 2 2 1 1 1 1
来源：Nescafe 21
思路：
IDA*
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<iostream> 5 #include<cstdlib> 6 #include<algorithm> 7 using namespace std; 8 const int dx[4]={0,0,1,-1};//扩展联通块时会用上。 9 const int dy[4]={-1,1,0,0};//扩展联通块时会用上。 10 int n,ID;//ID用来标记搜索深度。 11 int map[10][10],cl[10][10];//cl用来存储联通块。 12 bool used[6];//在估价函数中用来判重。 13 14 int get()//获得估价值。 15 { 16 int ret=0; 17 memset(used,false,sizeof(used)); 18 for(int i=1;i<=n;i++) 19 { 20 for(int j=1;j<=n;j++) 21 { 22 if(!used[map[i][j]] && cl[i][j]!=1) 23 { 24 used[map[i][j]]=true; 25 ret++; 26 } 27 } 28 } 29 return ret; 30 } 31 32 void dfs(int x,int y,int color)//对联通块进行扩展，color标记当前染的颜色。 33 { 34 cl[x][y]=1; 35 for(int i=0;i<4;i++) 36 { 37 int nx=x+dx[i],ny=y+dy[i]; 38 if(nx<1 || ny<1 || nx>n || ny>n || cl[nx][ny]==1)continue;//已经在联通块中了。 39 cl[nx][ny]=2; 40 if(map[nx][ny]==color)dfs(nx,ny,color);//如果发现该点颜色与要染的颜色相同，就以它重新扩展边界。 41 } 42 } 43 44 int fill(int color)//该次染色对联通块大小有无影响的判断函数。 45 { 46 int ret=0; 47 for(int i=1;i<=n;i++) 48 { 49 for(int j=1;j<=n;j++) 50 { 51 if(cl[i][j]==2 && map[i][j]==color) 52 { 53 ret++; 54 dfs(i,j,color); 55 } 56 } 57 } 58 return ret; 59 } 60 61 bool IDAstar(int step)//IDAstar的迭代搜索过程。 62 { 63 int g=get();//得到估价值。 64 if(step+g>ID)return false;//超过迭代搜索范围，返回假。 65 if(!g)return true;//如果找到答案，返回真。 66 67 int temp[10][10];//用来暂时保存当前联通块状态。 68 for(int i=0;i<=5;i++) 69 { 70 memcpy(temp,cl,sizeof(map));//用memcpy函数快捷存储。 71 if(fill(i) && IDAstar(step+1))return true;//如果此次染色有利于扩大联通块并且染色后能得到答案，就返回真。 72 memcpy(cl,temp,sizeof(map)); //用memcpy函数快捷存储。 73 } 74 return false;//以上条件都不满足，返回假。 75 } 76 main(){ 77 while(cin>>n && n) 78 { 79 memset(cl,0,sizeof(cl)); 80 for(int i=1;i<=n;i++) 81 { 82 for(int j=1;j<=n;j++) 83 { 84 scanf("%d",&map[i][j]); 85 } 86 } 87 dfs(1,1,map[1][1]); 88 for(ID=0;;ID++)//枚举搜索深度限制。 89 { 90 if(IDAstar(0)) 91 { 92 break;//得到答案后退出循环。 93 } 94 } 95 cout<<ID<<endl;//输出的为退出时的ID值，即为答案。 96 } 97 }