感觉这两份代码的差别不大，该剪的枝都剪了，可是实际测出来效率差别还是挺大的，一份140ms，一份80ms，其中140ms的那份代码在AcWing上测还TLE了

我甚至感觉140ms的那份代码每个搜索到的每个状态下遍历整个地图的次数更少，所以常数因子应该更小才对，但是不知道为啥实际跑出来效率差这么大

求dalao解答，感谢！

140ms:评测记录

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int n;
int g[10][10];
bool st[10][10];
int now[6];

void draw(int c)
{
    #define x first
    #define y second
    
    bool v[10][10];
    memset(v, false, sizeof v);
    memset(now, 0, sizeof now);
    
    queue<PII> q;
    q.push({1, 1});
    st[1][1] = true;
    v[1][1] = true;
    
    while (q.size())
    {
        PII t = q.front(); q.pop();
        
        for (int i = 0; i < 4; ++i)
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (v[x][y]) continue;
            if (g[x][y] == c || st[x][y]) st[x][y] = true, v[x][y] = true, q.push({x, y});
            else if (x >= 1 && x <= n && y >= 1 && y <= n) ++ now[g[x][y]];
        }
    }
}

inline int h()
{
    int cnt[6];
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (!st[i][j])
                ++ cnt[g[i][j]];
    int tot = 0;
    for (int i = 0; i < 6; ++i)
        if (cnt[i]) ++ tot;
    return tot;
}

bool IDA_star(int step, int depth)
{
    /*cout << step << ' ' << depth << endl;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j)
            cout << g[i][j] << ' '; cout << endl;}
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j)
            cout << st[i][j] << ' '; cout << endl;}
    cout << endl;*/
    if (step + h() > depth) return false;
    if (step == depth) return true;
    
    //int b[10][10];
    bool b1[10][10];
    int b2[6];
    //memcpy(b, g, sizeof b);
    memcpy(b1, st, sizeof b1);
    memcpy(b2, now, sizeof b2);
    for (int i = 0; i < 6; ++i)
    {
        if (!now[i]) continue;
        draw(i);
        if (IDA_star(step + 1, depth)) return true;
        //memcpy(g, b, sizeof g);
        memcpy(st, b1, sizeof st);
        memcpy(now, b2, sizeof now);
    }
    
    return false;
}

int main()
{
    while (scanf("%d", &n), n)
    {
        memset(g, 0x3f, sizeof g);
        memset(st, false, sizeof st);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d", &g[i][j]);
        
        draw(g[1][1]);
        
        int depth = 0;
        while (!IDA_star(0, depth)) ++ depth;
        printf("%d\n", depth);
    }
    return 0;
}

80ms:评测记录

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int n;
int g[10][10];
int st[10][10];

inline void draw(int x, int y, int c)
{
    st[x][y] = 1;
    for (int i = 0; i < 4; ++i)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= n)
        {
            if (st[a][b]) continue;
            if (g[a][b] == c) draw(a, b, c);
            else st[a][b] = 2;
        }
    }
}

inline int h()
{
    int cnt[6];
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (st[i][j] != 1)
                ++ cnt[g[i][j]];
    int tot = 0;
    for (int i = 0; i < 6; ++i)
        if (cnt[i]) ++ tot;
    return tot;
}

bool IDA_star(int step, int depth)
{
    /*cout << step << ' ' << depth << endl;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j)
            cout << g[i][j] << ' '; cout << endl;}
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j)
            cout << st[i][j] << ' '; cout << endl;}
    cout << endl;*/
    if (step + h() > depth) return false;
    if (step == depth) return true;
    
    int b[10][10];
    memcpy(b, st, sizeof b);
    for (int c = 0; c < 6; ++c)
    {
        bool success = false;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (g[i][j] == c && st[i][j] == 2)
                     success = true, draw(i, j, c);
        if (!success) continue;
        if (IDA_star(step + 1, depth)) return true;
        memcpy(st, b, sizeof st);
    }
    
    return false;
}

int main()
{
    while (scanf("%d", &n), n)
    {
        memset(g, 0x3f, sizeof g);
        memset(st, 0, sizeof st);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d", &g[i][j]);
        
        draw(1, 1, g[1][1]);
        
        int depth = 0;
        while (!IDA_star(0, depth)) ++ depth;
        printf("%d\n", depth);
    }
    return 0;
}