题解
搜索是个好东西，不是人人都会搜
迭代加深，然后用一个函数估值，值是除了和左上连通的部分还有几个颜色不同的块，如果走的步数加上估值大于当前枚举的深度就跳出
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <ctime>
#define MAXN 200005
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
int N,a[10][10],D,vis[10][10],_vis[10][10];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
void pre(int x,int y) {
vis[x][y] = 1;
for(int i = 0 ; i <= 3 ; ++i) {
if(vis[x + dx[i]][y + dy[i]]) continue;
if(a[x + dx[i]][y + dy[i]] == a[x][y]) {
pre(x + dx[i],y + dy[i]);
}
}
}
bool expend(int x,int y,int c) {
_vis[x][y] = 1;
bool flag = 0;
if(!vis[x][y]) flag = 1;
for(int i = 0 ; i <= 3 ; ++i) {
if(_vis[x + dx[i]][y + dy[i]]) continue;
if(vis[x + dx[i]][y + dy[i]] || a[x + dx[i]][y + dy[i]] == c)
flag = expend(x + dx[i],y + dy[i],c) || flag;
}
return flag;
}
int calc() {
bool used[6];memset(used,0,sizeof(used));
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
if(!vis[i][j]) {
used[a[i][j]] = 1;
}
}
}
int res = 0;
for(int i = 0 ; i <= 5 ; ++i) res += used[i];
return res;
}
bool dfs(int dep) {
if(dep > D) {
if(calc() == 0) return 1;
else return 0;
}
if(dep + calc() - 1 > D) return false;
for(int i = 0 ; i <= 5 ; ++i) {
memset(_vis,0,sizeof(_vis));
if(!expend(1,1,i)) continue;
int cpy[10][10];
memcpy(cpy,vis,sizeof(vis));
memcpy(vis,_vis,sizeof(vis));
if(dfs(dep + 1)) return 1;
memcpy(vis,cpy,sizeof(cpy));
}
return false;
}
void Solve() {
bool used[6];
memset(used,0,sizeof(used));
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
scanf("%d",&a[i][j]);
used[a[i][j]] = 1;
}
}
for(int i = 0 ; i <= N + 1; ++i) {
a[0][i] = a[N + 1][i] = 6;
a[i][0] = a[i][N + 1] = 6;
}
memset(vis,0,sizeof(vis));
pre(1,1);
if(calc() == 0) {puts("0");return;}
for(int dep = calc(); ; ++dep) {
D = dep;
if(dfs(1)) {
printf("%d\n",dep);
return;
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
while(scanf("%d",&N)!=EOF && N) {
if(N == 0) break;
Solve();
}
return 0;
}