2015
07-17

# HDU 4490-Mad Veterinarian-BFS-[解题报告]HOJ

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.

The first line of input contains a single integer P, (1<= P <= 1000 ), which is the number of data sets that follow. Each data set consists of several lines of input. Each data set should be processed identically and independently.

The first line of each data set consists of two decimal integers separated by a single space. The first integer is the data set number. The second integer is the number, N, of puzzle questions. The next three input lines contain the descriptions of machines A, B and C in that order. Each machine description line consists of three decimal integers separated by spaces giving the number of animals of type a, b and c output for one input animal. The following N lines give the puzzle questions for the Mad Veterinarian puzzle. Each contains seven decimal digits separated by single spaces: the puzzle number, the three starting animal counts for animals a, b and c followed by the three desired ending animal counts for animals a, b and c.

The first line of input contains a single integer P, (1<= P <= 1000 ), which is the number of data sets that follow. Each data set consists of several lines of input. Each data set should be processed identically and independently.

The first line of each data set consists of two decimal integers separated by a single space. The first integer is the data set number. The second integer is the number, N, of puzzle questions. The next three input lines contain the descriptions of machines A, B and C in that order. Each machine description line consists of three decimal integers separated by spaces giving the number of animals of type a, b and c output for one input animal. The following N lines give the puzzle questions for the Mad Veterinarian puzzle. Each contains seven decimal digits separated by single spaces: the puzzle number, the three starting animal counts for animals a, b and c followed by the three desired ending animal counts for animals a, b and c.

2
1 2
0 1 0
1 1 1
1 1 0
1 0 1 1 3 0 0
2 1 0 0 2 0 0
2 2
0 3 4
0 0 5
0 0 3
1 2 0 0 0 0 5
2 2 0 0 0 0 4

1 2
1 3 Caa
2 NO SOLUTION
2 2
1 NO SOLUTION
2 25 AcBcccBccBcccAccBccBcccBc

10以上就不要了我会乱说?队列只要开1000我会乱说?

→_→

#include<cstdio>
#include<cstring>
using namespace std;
bool vis[12][12][12];
int tras[4][4];
struct node
{
int a[4];
int dis;
}st,end,q[1000];
char path[1000];
int fa[1000];
char h[]="ZABCabc";
int num;
void print(int k)
{
if(!k) return;
print(fa[k]);
putchar(path[k]);
}
void bfs()
{
node f,r;
int rear=0,front=0;
st.dis=0;
q[rear++]=st;
vis[st.a[1]][st.a[2]][st.a[3]]=1;
while(front<rear)
{
f=q[front];
f.dis++;
for(int i=1;i<=3;i++)
{
r=f;
if(r.a[i])
{
r.a[i]--;
for(int j=1;j<=3;j++)
{
r.a[j]+=tras[i][j];
}
if(r.a[1]>10||r.a[2]>10||r.a[3]>10) continue;
if(!vis[r.a[1]][r.a[2]][r.a[3]])
{
fa[rear]=front;
path[rear]=h[i];
if(r.a[1]==end.a[1]&&r.a[2]==end.a[2]&&r.a[3]==end.a[3]) {printf("%d %d ",num,r.dis);print(rear);return;}
vis[r.a[1]][r.a[2]][r.a[3]]=1;
q[rear++]=r;
}
}
}
for(int i=4;i<=6;i++)
{
r=f;
int ok=1;
for(int j=1;j<=3;j++)
{
if(r.a[j]<tras[i-3][j]) ok=0;
}
if(ok)
{
for(int j=1;j<=3;j++)
{
r.a[j]-=tras[i-3][j];
}
r.a[i-3]++;
if(r.a[1]>10||r.a[2]>10||r.a[3]>10) continue;
if(!vis[r.a[1]][r.a[2]][r.a[3]])
{
path[rear]=h[i];
fa[rear]=front;
if(r.a[1]==end.a[1]&&r.a[2]==end.a[2]&&r.a[3]==end.a[3]) {printf("%d %d ",num,r.dis);print(rear);return;}
vis[r.a[1]][r.a[2]][r.a[3]]=1;
q[rear++]=r;
}
}
}
front++;
}
printf("%d NO SOLUTION",num);
}
int main()
{
int p,casq,n;
scanf("%d",&p);
while(p--)
{
scanf("%d %d",&casq,&n);
printf("%d %d\n",casq,n);
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
scanf("%d",&tras[i][j]);
}
for(int i=1;i<=n;i++)
{
scanf("%d %d %d %d %d %d %d",&num,&st.a[1],&st.a[2],&st.a[3],&end.a[1],&end.a[2],&end.a[3]);
if(st.a[1]==end.a[1]&&st.a[2]==end.a[2]&&st.a[3]==end.a[3])
{
printf("%d 0\n",num);
continue;
}
memset(vis,0,sizeof(vis));
bfs();
puts("");
}
}
return 0;
}