test03

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

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

using namespace std;

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

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

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

bool init()
{
    scanf("%d%d%d", &w, &h, &ghost_num); ghost_num = 0; 
    root.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(dict, 0, sizeof(dict));
    memset(save, 0, sizeof(save));
    memset(vis, 0, sizeof(vis));
    return (w && h);
}
void input();
int bfs();

int main(void)
{
//  clock_t startTime,endTime; startTime = clock();

//     freopen("in.txt", "r", stdin);
    while(true)
    {
        if(!init()) break;
        input();
        int ans = bfs();
        printf("%d\n", ans);
    }
//  endTime = clock();
//     printf("Totle time : %lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC);

    return 0;
}

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');
                root.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 a, int b, int c, int index)
{
    if(vis[a][b][c]) return false;
    vis[a][b][c] = index; return true;
}

int bfs()
{
    int depth = 1, index = 1;
    queue<State> Q1; Q1.push(root);
    queue<State> Q2; Q2.push(goal);

    while(!Q1.empty()) {
        queue<State> Q1_child;
        while(!Q1.empty())
        {
            State s = Q1.front(); Q1.pop();
            int g1 = s.p[0]; int g2 = s.p[1]; int g3 = s.p[2];

            for(int x = 0; x < G[g1].size(); ++x) {
                for(int y = 0; y < G[g2].size(); ++y) {
                    for(int z = 0; z < G[g3].size(); ++z) {
                        int newg1 = G[g1][x], newg2 = G[g2][y], 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;

                        if(vis[newg1][newg2][newg3] + index == 0) return depth;
                        if(try_to_insert(newg1, newg2, newg3, index))
                            Q1_child.push(State{newg1, newg2, newg3, s.dis+1});
                    }
                }
            }
        }

        Q1 = Q2; Q2 = Q1_child;
        index = -index; ++depth;
    }

    return 0;
}