涂满它!,骑士精神--最后两个搜索.搜索拜拜

第一个代码:

#include <bits/stdc++.h>
using namespace std;
const int N=10;
int n;
int vis[N][N];
int a[N][N];
int color[N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int f()
{
    int cnt=0;
    memset(color,0,sizeof color);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!color[a[i][j]]&&vis[i][j]!=1)
            {
                color[a[i][j]]=1;
                cnt++;  
            }
        }
    }
    return cnt;
}

void paint(int x,int y,int c)
{
    vis[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(vis[tx][ty]==1||tx<1||tx>n||ty<1||ty>n) continue;
        vis[tx][ty]=2;
        if(a[tx][ty]==c) paint(tx,ty,c);
    }
}

int fill(int c)
{
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vis[i][j]==2&&a[i][j]==c)
            {
                paint(i,j,c);
                cnt++;
            }
        }
    }
    return cnt;
}

bool dfs(int u,int dep)
{
    int x=f();
   // cout<<x<<endl;
    //减枝
    if(x+u>dep) return false;
    //递归出口
    if(!x)      return true;
    int res[N][N];
    for(int i=0;i<6;i++)
    {
        memcpy(res,vis,sizeof res);
        if(fill(i)&&dfs(u+1,dep)) return true;   
        memcpy(vis,res,sizeof res);
    }
    return false;
}

int main()
{
    while(cin>>n,n)
    {
        memset(vis,0,sizeof vis);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>a[i][j];
            }
        }
        paint(1,1,a[1][1]);
        int depth=0;
        while(!dfs(0,depth)) depth++;
        cout<<depth<<endl;
    }
    return 0;
}
/*
3
0 1 2
1 1 2
2 2 1
*/

第二个代码:

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
#define f first
#define s second
const int N=5;
int dx[8]={-1,-2,-2,-1,2,1,2,1};
int dy[8]={-2,-1,1,2,1,2,-1,-2};
int ans[N][N]={
    {1,1,1,1,1},
    {-1,1,1,1,1},
    {-1,-1,0,1,1},
    {-1,-1,-1,-1,1},
    {-1,-1,-1,-1,-1}
};
int a[N][N];

int f()
{
    int cnt=0;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(a[i][j]!=ans[i][j]&&a[i][j]) cnt++;
        }
    }
    return cnt;
}

bool dfs(int u,int dep,pi start)
{
    int eva=f();
    if(!eva) return true;
    if(eva+u>dep) return false;
    int x=start.f;
    int y=start.s;
    for(int i=0;i<8;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<0||tx>4||ty<0||ty>4) continue;
        swap(a[x][y],a[tx][ty]);
        pi end={tx,ty};
        if(dfs(u+1,dep,end)) return true;
        swap(a[x][y],a[tx][ty]);
    }
    return false;
}

int main()
{
    int T;
    char c;
    pi start;
    cin>>T;
    while(T--)
    {
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                cin>>c;
                if(c=='1')      a[i][j]=1;
                else if(c=='0') a[i][j]=-1;
                else
                {
                    a[i][j]=0;
                    start={i,j};    
                }
            }
        }
        int depth=0;
        while(!dfs(0,depth,start)&&depth<=15) depth++;
        if(depth>15) puts("-1"); 
        else         cout<<depth<<endl;
    }
    return 0;
}