test02

原始文件为 cpp 代码，本文是转换后的 Markdown 文件。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <set>

using namespace std;

struct State
{
    int p[3];
    void init() { p[1] = 257; p[2] = 258; }
    void init(int a, int b, int c) {p[0]=a; p[1]=b; p[2]=c;}
    void setv(int idx, int value) { p[idx]=value; }
};

const int maxstate = 8000000;
State st[maxstate], goal;
char save[17][17];
// set<int> vis;
bool vis[260][260][260];
vector<int> G[260];

int w, h, ghost_num;
char dict[26];
int dis[maxstate];

bool init()
{
    scanf("%d%d%d", &w, &h, &ghost_num); ghost_num = 0; 
    st[1].init(); goal.init();
    for(int i = 0; i < 260; ++i) G[i].clear();
    for(int i = 0; i < 260; ++i) G[i].push_back(i);
    memset(dis, 0, sizeof(dis));
    memset(dict, 0, sizeof(dict));
    memset(save, 0, sizeof(save));

    memset(vis, false, sizeof(vis));
//     vis.clear();
    return (w && h);
}
void input();
int bfs();

int main()
{
//     freopen("in.txt", "r", stdin);
    while(true)
    {
        if(!init()) break;
        input();
        int ans = bfs();
        printf("%d\n", dis[ans]);
    }
}

void link(int a, int b)
{
    G[b].push_back(a);
    G[a].push_back(b);
}

int query(int ch_int)
{
    if(!dict[ch_int])
    {
        ++ghost_num;
        dict[ch_int] = ghost_num;
        return (ghost_num - 1);
    }
    return dict[ch_int] - 1;
}

void input()
{
    char line;
    for(int i = 0; i < h; ++i) 
    {
        scanf("%c", &line);
        for(int j = 0; j < w; ++j) 
        {
            scanf("%c", &save[i][j]);
        }
    }

    for(int j = 1; j < w; ++j)
    {
        if(save[0][j] == '#') continue;
        if(save[0][j-1] != '#') link(j, j-1); 
    }
    for(int i = 1; i < h; ++i)
    {
        if(save[i][0] == '#') continue;
        if(save[i-1][0] != '#') link((i << 4), (i - 1) << 4);
    }
    for(int i = 1; i < h; ++ i)
    {
        for(int j = 1; j < w; ++j)
        {
            if(save[i][j] == '#') continue;
            int now_idx = (i << 4) + j;
            if(save[i-1][j] != '#') link(now_idx, now_idx - 16);
            if(save[i][j-1] != '#') link(now_idx, now_idx - 1);
        }
    }

    for(int i = 0; i < h; ++i) 
    {
        for(int j = 0; j < w; ++j)
        {
            char ch = save[i][j];
            if(ch >= 'a' && ch <= 'z') 
            {
                int now_idx = query(ch - 'a');
                st[1].setv(now_idx, (i << 4) + j);
            }else if(ch >= 'A' && ch <= 'Z') 
            {
                int now_idx = query(ch - 'A');
                goal.setv(now_idx, (i << 4) + j);
            }
        }
    }
}

bool isequal(State a, State b)
{
    for(int i = 0; i < 3; ++i)
    {
        if(a.p[i] != b.p[i]) return false;
    }
    return true;
}

bool try_to_insert(int rear)
{
    if(vis[st[rear].p[0]][st[rear].p[1]][st[rear].p[2]]) return false;
    vis[st[rear].p[0]][st[rear].p[1]][st[rear].p[2]] = true;
    return true;

//     int v = 0;
//     for(int i = 0; i < 3; ++i)
//         v = (v << 10) + st[rear].p[i];

//     if(vis.count(v)) return false;

//     vis.insert(v); return true;
}

const int dx[] = {0, -16, 1, 16, -1};
int bfs()
{
    int front = 1, rear = 2; 

    while(front < rear) {
        State& s = st[front];
        if(isequal(s, goal)) return front;

        int g1 = s.p[0]; int g2 = s.p[1]; int g3 = s.p[2];

        for(int x = 0; x < G[g1].size(); ++x) 
        {
            int newg1 = G[g1][x];
            for(int y = 0; y < G[g2].size(); ++y) 
            {
                int newg2 = G[g2][y];
                for(int z = 0; z < G[g3].size(); ++z) 
                {
                    int newg3 = G[g3][z];
                    if(!x && !y && !z) continue;

                    if(newg1 == newg2 || newg2 == newg3 || newg1 == newg3 ) continue;

                    if(newg1 == g2 && newg2 == g1) continue;
                    if(newg1 == g3 && newg3 == g1) continue;
                    if(newg2 == g3 && newg3 == g2) continue;

                    State& r = st[rear];
                    r.init(newg1, newg2, newg3);

                    dis[rear] = dis[front] + 1;
                    if(try_to_insert(rear)) ++rear;
                }
            }
        }
        ++front;
    }

    return 0;
}