HDU 4490 – Mad Veterinarian [无脑BFS]

Link

传送门

Problem

Mad Veterinarian puzzles have a mad veterinarian, who has developed several machines that can transform an animal into one or more animals and back again. The puzzle is then to determine if it is possible to change one collection of animals into another by applying the machines in some order (forward or reverse). For example:

Machine A turns one ant into one beaver.
Machine B turns one beaver into one ant, one beaver and one cougar.
Machine C turns one cougar into one ant and one beaver.

Can we convert a beaver and a cougar into 3 ants?

Can we convert one ant into 2 ants? NO

These puzzles have the properties that:

1. In forward mode, each machine converts one animal of a given species into a finite, non-empty collection of animals from the species in the puzzle.
2. Each machine can operate in reverse.
3. There is one machine for each species in the puzzle and that machine (in forward mode) takes as input one animal of that species.

Write a program to find the shortest solution (if any) to Mad Veterinarian puzzles. For this problem we will restrict to Mad Veterinarian puzzles with exactly three machines, A, B, C.

Mean

三个起始数字A1 B1C1,和终止数字A2 B2 C2,给你三种变幻和逆变幻,问最短要变幻几次才能完成,同时输出具体变化路径。

Analysis

题目比较坑,没有数据范围,据说最少搜索到8以内能AC。题目输出比较麻烦,细节也比较多,但基本都是无脑简单BFS。具体看代码吧

Code

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int x, y, z;
    Node(int x = 0, int y = 0, int z = 0):
        x(x), y(y), z(z) {}
};

int chg[5][5];
int st[5], ed[5];
bool vis[12][12][12];
char pre[12][12][12];
Node preno[12][12][12];

void output() {
    Node cur(ed[0], ed[1], ed[2]);
    string ans;
    while(cur.x != st[0] || cur.y != st[1] || cur.z != st[2]) {
        ans.push_back(pre[cur.x][cur.y][cur.z]);
        cur = preno[cur.x][cur.y][cur.z];
    }
    printf("%d ", ans.size());
    for(int i = ans.size()-1; i >= 0; --i)
        putchar(ans[i]);
    puts("");
}

bool isVis(Node &n, char p, Node &u) {
    // printf("!!! %d %d %d %c\n", n.x, n.y, n.z, p);
    if(n.x >= 12 || n.y >= 12 || n.z >= 12)
        return true;
    bool fuck = vis[n.x][n.y][n.z];
    if(!fuck) {
        vis[n.x][n.y][n.z] = true;
        pre[n.x][n.y][n.z] = p;
        preno[n.x][n.y][n.z] = u;
    }
    return fuck;
}

void solve() {
    queue<Node> qu;
    qu.push(Node(st[0], st[1], st[2]));
    while(!qu.empty()) {
        Node u = qu.front(); qu.pop();
        // printf("%d %d %d\n", u.x, u.y, u.z);
        if(u.x == ed[0] && u.y == ed[1] && u.z == ed[2]) {
            output();
            return;
        }
        if(u.x > 0) {
            Node v(u.x-1+chg[0][0], u.y+chg[0][1], u.z+chg[0][2]);
            if(!isVis(v, 'A', u)) qu.push(v);
        }
        if(u.y > 0) {
            Node v(u.x+chg[1][0], u.y-1+chg[1][1], u.z+chg[1][2]);
            if(!isVis(v, 'B', u)) qu.push(v);
        }
        if(u.z > 0) {
            Node v(u.x+chg[2][0], u.y+chg[2][1], u.z-1+chg[2][2]);
            if(!isVis(v, 'C', u)) qu.push(v);
        }
        if(u.x >= chg[0][0] && u.y >= chg[0][1] && u.z >= chg[0][2]) {
            Node v(u.x-chg[0][0]+1, u.y-chg[0][1], u.z-chg[0][2]);
            if(!isVis(v, 'a', u)) qu.push(v);
        }
        if(u.x >= chg[1][0] && u.y >= chg[1][1] && u.z >= chg[1][2]) {
            Node v(u.x-chg[1][0], u.y-chg[1][1]+1, u.z-chg[1][2]);
            if(!isVis(v, 'b', u)) qu.push(v);
        }
        if(u.x >= chg[2][0] && u.y >= chg[2][1] && u.z >= chg[2][2]) {
            Node v(u.x-chg[2][0], u.y-chg[2][1], u.z-chg[2][2]+1);
            if(!isVis(v, 'c', u)) qu.push(v);
        }
        
    }
    printf("NO SOLUTION\n");
}

int main()
{
    //freopen("out111.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--) {
        int ID, N; scanf("%d%d", &ID, &N);
        for(int i = 0; i < 3; ++i)
            for(int j = 0; j < 3; ++j)
                scanf("%d", &chg[i][j]);
        printf("%d %d\n", ID, N);
        for(int i = 0; i < N; ++i) {
            int id; scanf("%d", &id);
            memset(vis, false, sizeof(vis));
            for(int j = 0; j < 3; ++j)
                scanf("%d", st + j);
            for(int j = 0; j < 3; ++j)
                scanf("%d", ed + j);
            printf("%d ", id);
            solve();
        }
    }
    return 0;
}

欢迎留言