Mad Veterinarian
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 249 Accepted Submission(s): 104
Special Judge
Problem Description
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.
Input
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.
Output
For each input data set there are multiple lines of output. The first line of output for each data set contains the data set number, a space and the number of puzzle questions (N). For each puzzle question, there is one line of output which consists of the puzzle question number followed by a space, followed by “NO SOLUTION”, (without the quotes) if there is no solution OR the puzzle question number followed by the shortest number of machine steps used, a space and a sequence of letters [A B C a b c] with capital letters indicating applying the machine in the forward direction and lower case letters indicating applying the machine in the reverse direction.
Sample Input
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
Sample Output
1 2
1 3 Caa
2 NO SOLUTION
2 2
1 NO SOLUTION
2 25 AcBcccBccBcccAccBccBcccBc
Source
Greater New York 2012
題意：有三個機器ABC,可以分別把a,b,c變成對應的某幾個東西，也可以逆著變，求變到目標狀態的最少步數
很水的題，不過我寫了好長好長，太不符合我的風格了，剛開始調試的時候無解的情況表示不出來，因為它的數據可以一直往上漲，最後限制了一下，看學長的博客說的最多8個，加這個限制就可以了，好不容易調試出來了，結果跟示例對不上，過了好久才想到方法可能不止一種，於是提交了，結果就AC了。。。0ms
寫的有點長，不過很多就是差不多的，看起來應該不費力吧，這題的輸入數據很蛋疼要小心
#include<stdio.h>
#include<string.h>
#define M 8
struct node
{
int a,b,c,f;
char o;
}f[4],s[1000],start,end;
int visit[10][10][10];
int bfs()
{
int t=0,w=1;
memset(visit,0,sizeof(visit));
visit[s[t].a][s[t].b][s[t].c]=1;
s[0].f=-1;
while(t<w)
{
if(s[t].a>0)
{
s[w].a=s[t].a+f[0].a-1;
s[w].b=s[t].b+f[0].b;
s[w].c=s[t].c+f[0].c;
s[w].f=t;
s[w].o='A';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
if(s[t].b>0)
{
s[w].b=s[t].b+f[1].b-1;
s[w].a=s[t].a+f[1].a;
s[w].c=s[t].c+f[1].c;
s[w].f=t;
s[w].o='B';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
if(s[t].c>0)
{
s[w].c=s[t].c+f[2].c-1;
s[w].b=s[t].b+f[2].b;
s[w].a=s[t].a+f[2].a;
s[w].f=t;
s[w].o='C';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
if(s[t].a>=f[0].a&&s[t].b>=f[0].b&&s[t].c>=f[0].c)
{
s[w].a=s[t].a-f[0].a+1;
s[w].b=s[t].b-f[0].b;
s[w].c=s[t].c-f[0].c;
s[w].f=t;
s[w].o='a';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
if(s[t].a>=f[1].a&&s[t].b>=f[1].b&&s[t].c>=f[1].c)
{
s[w].b=s[t].b-f[1].b+1;
s[w].a=s[t].a-f[1].a;
s[w].c=s[t].c-f[1].c;
s[w].f=t;
s[w].o='b';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
if(s[t].a>=f[2].a&&s[t].b>=f[2].b&&s[t].c>=f[2].c)
{
s[w].c=s[t].c-f[2].c+1;
s[w].b=s[t].b-f[2].b;
s[w].a=s[t].a-f[2].a;
s[w].f=t;
s[w].o='c';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
t++;
}
return 0;
}
int main()
{
int t,i,j,n,num,tt;
char cou[100];
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&num,&n);
printf("%d %d\n",num,n);
for(i=0;i<3;i++)
scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c);
while(n--)
{
scanf("%d%d%d%d%d%d%d",&tt,&s[0].a,&s[0].b,&s[0].c,&end.a,&end.b,&end.c);
printf("%d ",tt);
if(i=bfs())
{
for(j=98;i>0;j--)
{
cou[j]=s[i].o;
i=s[i].f;
}
cou[99]='\0';
printf("%d ",98-j);
puts(cou+j+1);
}
else puts("NO SOLUTION");
}
}
return 0;
}
#include<stdio.h>
#include<string.h>
#define M 8
struct node
{
int a,b,c,f;
char o;
}f[4],s[1000],start,end;
int visit[10][10][10];
int bfs()
{
int t=0,w=1;
memset(visit,0,sizeof(visit));
visit[s[t].a][s[t].b][s[t].c]=1;
s[0].f=-1;
while(t<w)
{
if(s[t].a>0)
{
s[w].a=s[t].a+f[0].a-1;
s[w].b=s[t].b+f[0].b;
s[w].c=s[t].c+f[0].c;
s[w].f=t;
s[w].o='A';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
if(s[t].b>0)
{
s[w].b=s[t].b+f[1].b-1;
s[w].a=s[t].a+f[1].a;
s[w].c=s[t].c+f[1].c;
s[w].f=t;
s[w].o='B';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
if(s[t].c>0)
{
s[w].c=s[t].c+f[2].c-1;
s[w].b=s[t].b+f[2].b;
s[w].a=s[t].a+f[2].a;
s[w].f=t;
s[w].o='C';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
if(s[t].a>=f[0].a&&s[t].b>=f[0].b&&s[t].c>=f[0].c)
{
s[w].a=s[t].a-f[0].a+1;
s[w].b=s[t].b-f[0].b;
s[w].c=s[t].c-f[0].c;
s[w].f=t;
s[w].o='a';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
if(s[t].a>=f[1].a&&s[t].b>=f[1].b&&s[t].c>=f[1].c)
{
s[w].b=s[t].b-f[1].b+1;
s[w].a=s[t].a-f[1].a;
s[w].c=s[t].c-f[1].c;
s[w].f=t;
s[w].o='b';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
if(s[t].a>=f[2].a&&s[t].b>=f[2].b&&s[t].c>=f[2].c)
{
s[w].c=s[t].c-f[2].c+1;
s[w].b=s[t].b-f[2].b;
s[w].a=s[t].a-f[2].a;
s[w].f=t;
s[w].o='c';
if(s[w].a<M&&s[w].b<M&&s[w].c<M&&!visit[s[w].a][s[w].b][s[w].c])
{
if(s[w].a==end.a&&s[w].b==end.b&&s[w].c==end.c)
{
end.f=w;
return w;
}
visit[s[w].a][s[w].b][s[w].c]=1;
w++;
}
}
t++;
}
return 0;
}
int main()
{
int t,i,j,n,num,tt;
char cou[100];
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&num,&n);
printf("%d %d\n",num,n);
for(i=0;i<3;i++)
scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c);
while(n--)
{
scanf("%d%d%d%d%d%d%d",&tt,&s[0].a,&s[0].b,&s[0].c,&end.a,&end.b,&end.c);
printf("%d ",tt);
if(i=bfs())
{
for(j=98;i>0;j--)
{
cou[j]=s[i].o;
i=s[i].f;
}
cou[99]='\0';
printf("%d ",98-j);
puts(cou+j+1);
}
else puts("NO SOLUTION");
}
}
return 0;
}
