test

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

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

using namespace std;

struct Point
{
    int x, y;
    void setv(int a, int b) { x = a; y = b; }
};
struct State
{
    Point p[3];
    void init() { p[1].setv(1,0); p[2].setv(0,1); }
    void init(Point a, Point b, Point c) {p[0]=a; p[1]=b; p[2]=c;}
    void setv(int idx, int a, int b) { p[idx].setv(a,b); }
};

const int maxstate = 8000000;
State st[maxstate], goal;
char save[17][17];
set<int> vis;

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();
    memset(dis, 0, sizeof(dis));
    memset(dict, 0, sizeof(dict));
    memset(save, 0, sizeof(save));

    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]);
    }
}

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 = 1; i <= h; ++i) 
    {
        scanf("%c", &line);
        for(int j = 1; j <= w; ++j) 
        {
            scanf("%c", &save[i][j]);
            char ch = save[i][j];

            if(ch >= 'a' && ch <= 'z') 
            {
                int now_idx = query(ch - 'a');
                st[1].setv(now_idx, i, j);
            }else if(ch >= 'A' && ch <= 'Z') 
            {
                int now_idx = query(ch - 'A');
                goal.setv(now_idx, i, j);
            }
        }
    }
}

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

bool islegal(Point p, int index)
{
    if(save[p.x][p.y] == '#') return false;
    if(ghost_num < index)
    {
        int x = p.x; int y = p.y;
        return (x > 0 && y > 0 && x <= h && y <= w);
    }
    return true;
}

bool isequal(Point a, Point b)
{
    return (a.x == b.x) && (a.y == b.y);
}

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

bool try_to_insert(int rear)
{
    int v = 0;
    for(int i = 0; i < 3; ++i)
    {
        Point now = st[rear].p[i];
        v = (v << 5) + now.x;
        v = (v << 5) + now.y;
    }
    if(vis.count(v)) return false;

    vis.insert(v); return true;
}

int bfs()
{
    int front = 1, rear = 2; 

    int y_size = (ghost_num == 1) ? 1 : 5;
    int z_size = (ghost_num < 3) ? 1 : 5;

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

        for(int x = 0; x < 5; ++x) 
        {
            Point newa{s.p[0].x+dx[x], s.p[0].y+dy[x]};
            if(!islegal(newa, 0)) continue;
            for(int y = 0; y < y_size; ++y) 
            {
                Point newb{s.p[1].x+dx[y], s.p[1].y+dy[y]};
                if(!islegal(newb, 1)) continue;
                for(int z = 0; z < z_size; ++z) 
                {
                    Point newc{s.p[2].x+dx[z], s.p[2].y+dy[z]};
                    if(!islegal(newc, 2)) continue;

                    if(!x && !y && !z) continue;
                    if(isequal(newa, newb)) continue;
                    if(isequal(newc, newb)) continue;
                    if(isequal(newc, newa)) continue;

                    if(isequal(newa, s.p[1]) && isequal(newb, s.p[0])) continue;
                    if(isequal(newa, s.p[2]) && isequal(newc, s.p[0])) continue;
                    if(isequal(newb, s.p[2]) && isequal(newc, s.p[1])) continue;

                    State& r = st[rear];
                    r.init(newa, newb, newc);

                    dis[rear] = dis[front] + 1;
                    if(try_to_insert(rear)) 
                    {
                        ++rear;
//                         printf("-------\n");
//                         printf("x = %d, y = %d, z = %d\n", x, y, z);
//                         printf("newa = (%d, %d)\n", newa.x, newa.y);
//                         printf("newb = (%d, %d)\n", newb.x, newb.y);
//                         printf("newc = (%d, %d)\n", newc.x, newc.y);
//                         printf("rear = %d\n", rear);
//                         printf("-------\n");
                    }
                }
            }
        }
        ++front;
    }

    return 0;
}