AcWing 194. 涂满它！    原题链接    中等

作者： 作者的头像   xjc ,  2019-08-21 20:51:41 ,  所有人可见 ,  阅读 1572

2


1

IDA*不解释

#include <cstdio>
#include <cstring>
int a[10][10], n, l[] = {-1, 1, 0, 0}, r[] = {0, 0, -1, 1}, v[10], vis[10][10], limit;
void dfs(int now, int x, int y){
    //printf("%d %d %d\n", now, x, y);
    vis[x][y] = 1;
    for(int i = 0; i < 4; ++i){
        int X = x + l[i], Y = y + r[i];
        if(X < 0 || Y < 0 || X >= n || Y >= n || vis[X][Y] == 1) continue;
        vis[X][Y] = 2;
        if(a[X][Y] == now) dfs(now, X, Y);
    }
} 
int fill(int now){
    int p = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            if(a[i][j] == now && vis[i][j] == 2)
                dfs(now, i, j), ++p;
    return p;
}
int IDA(int now, int dep){
    v[0] = v[1] = v[2] = v[3] = v[4] = v[5] = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            if(vis[i][j] != 1)
                v[a[i][j]] = 1;
    int f = v[0] + v[1] + v[2] + v[3] + v[4] + v[5];
    if(!f) return 1;
    if(dep + f > limit) return 0;
    int tmp[10][10];
    memcpy(tmp, vis, sizeof vis);
    for(int k = 0; k < 6; ++k){
        if(k == now) continue;
        if(fill(k) && IDA(k, dep + 1)) return 1;
        memcpy(vis, tmp, sizeof vis);
    }
    return 0;
}
int main(){
    while(scanf("%d", &n) && n){
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                scanf("%d", &a[i][j]);
        memset(vis, 0, sizeof vis);
        dfs(a[0][0], 0, 0);
        for(limit = 0; ; ++limit){
            if(IDA(a[0][0], 0)){
                printf("%d\n", limit);
                break;
            }
        }
    }
}

10 评论

用户头像
大魔王_0   2023-11-02 19:01         踩      回复

听君一席话，如没有听话

用户头像
dugouxukaixinjiukanrp   2023-02-02 14:56         踩      回复

听君一席话，胜听半席话

用户头像
Cyprus   2023-02-02 09:48         踩      回复

听君一席话，白读十年书

用户头像
小蒟蒻-   2023-02-02 09:36         踩      回复

听君一席话，如听一席话

用户头像
Deep_Dark_Fantasy   2021-02-06 19:24         踩      回复

%%%

用户头像
zach   2020-04-20 22:44         踩      回复

不知道为啥，谢谢您！

用户头像
zach   2020-04-20 22:44         踩      回复 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define y second
#define x first
#define pii pair <int, int>
using namespace std;

const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

bool vis[8][8];
int n, map[8][8];
pii Q[120];
void flip(int type, int (*mat)[8])
{
    memset(vis, 0, sizeof(vis));
    int head = 0, tail = 1, i;
    Q[tail] = make_pair(0, 0);
    vis[0][0] = true;

    while(head != tail)
    {
        pii next, now = Q[head ++];

        for(i = 0; i < 4; ++ i)
        {
            next = make_pair(now.x + dx[i], now.y + dy[i]);
            if(next.x >= 0 && next.x < n && next.y >= 0 && next.y < n && vis[next.x][next.y] == false)
            {
                if(mat[next.x][next.y] == 0 && map[next.x][next.y] == type)
                {
                    vis[next.x][next.y] = true;
                    mat[next.x][next.y] = 1;
                    Q[tail ++] = next;
                }else if(mat[next.x][next.y] == 1)
                {
                    vis[next.x][next.y] = true;
                    Q[tail ++] = next;
                }
            }
        }
    }
    return;
}
int calc(int (*mat)[8], int *color)
{
    int i, j, t = 0;
    bool b[6] = {};
    for(i = 0; i < n; ++ i)
    {
        for(j = 0; j < n; ++ j)
        {
            if(!mat[i][j] && !b[map[i][j]])
            {
                color[t ++] = map[i][j];
                b[map[i][j]] = true;
            }
        }
    }
    return t;
}
bool dfs(int (*mat)[8], int cur, int dep)
{
    int color[6], cnt = calc(mat, color);
    if(cnt > dep) return false;
    if(!dep)
    {
        if(!cnt) return true;
        return false;
    }
    int copy[8][8], i;

    for(i = 0; i < cnt; ++ i)
    {
        memcpy(copy, mat, sizeof(copy));
        if(cur == color[i]) continue;
        flip(color[i], copy);
        if(dfs(copy, color[i], dep - 1)) return true;
    }
    return false;
}
int main()
{
    freopen("data.in", "r", stdin);
    while(scanf("%d", &n) == 1)
    {
        if(!n) 
        {
            return 0;
        }
        int i, j, copy[8][8] = {1};
        for(i = 0; i < n; ++ i)
            for(j = 0; j < n; ++ j) scanf("%d", &map[i][j]);

        flip(map[0][0], copy);
        for(i = 0; i < 25; ++ i)
        {
            if(dfs(copy, map[0][0], i))
            {
                printf("%d\n", i);
                break;
            }
        }   
    }   
    return 0;
}
用户头像
zach   2020-04-20 22:43         踩      回复

请问大佬，为什么paint函数使用广搜和深搜运行时间会有那么大的差别？？？

用户头像
扶摇直上九万里   2020-01-13 11:56         踩      回复

我自己做半个小时硬是没有做出来

用户头像
扶摇直上九万里   2020-01-13 11:56         踩      回复

%%% 巨佬