C++(g++ 7.5.0) 解法, 执行用时: 152ms, 内存消耗: 472K, 提交时间: 2022-08-03 12:59:11

#include<bits/stdc++.h>
#define N 8
#define M 6
#define met(x) memset(x,0,sizeof(x))
using namespace std;
int mp[N][N],n;
int state[N][N];
bool mark[M];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void dfs(int px,int py,int color){
    state[px][py]=1;
    for(int i=0;i<4;++i){
        int x=px+dx[i];
        int y=py+dy[i];
        if(0<=x&&x<n&&0<=y&&y<n)
        if(state[x][y]!=1){
            if(mp[x][y]==color)dfs(x,y,color);
            else state[x][y]=2;
        }
    }
}
void init(){
    met(state);
    dfs(0,0,mp[0][0]);
}
int Astar(int color){
    int sum=0;
    met(mark);
    for(int i=0;i<n;++i)
    for(int j=0;j<n;++j)
        if(state[i][j]!=1&&!mark[mp[i][j]]){
            mark[mp[i][j]]=1;
            sum++;
        }
    return sum;
}
int cnt(int color){
    int sum=0;
    for(int i=0;i<n;++i)
    for(int j=0;j<n;++j)
    if(state[i][j]==2&&mp[i][j]==color){
        sum++;
        dfs(i,j,color);
    }
    return sum;
}
bool IDAstar(int deep,int color){
    if(deep<Astar(color))return 0;
    if(deep==0)return 1;
    for(int i=0;i<M;++i){
        int memery[N][N];
        memcpy(memery,state,sizeof(state));
        if(cnt(i)==0)continue;
        if(IDAstar(deep-1,i))return 1;
        memcpy(state,memery,sizeof(memery));
    }
    return 0;
}
int main(void){
    while(scanf("%d",&n)){
        if(n==0)break;
        for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            scanf("%d",&mp[i][j]);
        init();
        int deep=Astar(mp[0][0]);
        if(deep==0){
            printf("0\n");
        }else{
            while(!IDAstar(deep,mp[0][0]))deep++;
            printf("%d\n",deep);
        }
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 96ms, 内存消耗: 388K, 提交时间: 2020-09-29 16:12:00

#include <cstring>
#include <iostream>
using namespace std;
const int N = 10;
int n, a[N][N], dep, v[N][N];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

bool pd(int x, int y) {
	return x > 0 && x <= n && y > 0 && y <= n;
}

void dfs(int x, int y, int z) {
	v[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (!pd(nx, ny)) continue;
		if (v[nx][ny] == 1) continue;
		v[nx][ny] = 2;
		if (a[nx][ny] == z) dfs(nx, ny, z);
	}
}

int gj() {
	int ans = 0;
	bool w[6];
	memset(w, 0, sizeof(w));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (!w[a[i][j]] && v[i][j] != 1) {
				w[a[i][j]] = 1;
				++ans;
			}
	return ans;
}

bool dfs0(int now) {
	int cnt = gj();
	if (now + cnt > dep) return 0;
	if (!cnt) return 1;
	int w[N][N];
	memcpy(w, v, sizeof(w));
	for (int i = 0; i < 6; i++) {
		bool flag = 0;
		for (int x = 1; x <= n; x++)
			for (int y = 1; y <= n; y++)
				if (a[x][y] == i && v[x][y] == 2) {
					flag = 1;
					dfs(x, y, i);
				}
		if (flag && dfs0(now + 1)) return 1;
		memcpy(v, w, sizeof(v));
	}
	return 0;
}

int main() {
	while (cin >> n && n) {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				cin >> a[i][j];
		memset(v, 0, sizeof(v));
		dfs(1, 1, a[1][1]);
		dep = 0;
		while (!dfs0(0)) ++dep;
		cout << dep << endl;
	}
	return 0;
}