poj3414Pots(BFS)
22992 ワード
http://poj.org/problem?id=3414
6つの状況を調べてみよう
View Code
6つの状況を調べてみよう
View Code
1 #include <iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 struct node
6 {
7 int ca,cb;
8 int flag,num;
9 int op,ob;
10 }q[1000000];
11 int a,b,c,vis[110][110],num[100000],g;
12 void put(int x,int y)
13 {
14 int yy;
15 if(y==1)
16 yy = 2;
17 else
18 yy = 1;
19 if(x==1)
20 printf("FILL(%d)
",y);
21 else
22 if(x==3)
23 printf("POUR(%d,%d)
",y,yy);
24 else
25 printf("DROP(%d)
",y);
26 }
27 void bfs()
28 {
29 int p = 0,d = 1,na,nb,flag = 0;
30 memset(vis,0,sizeof(vis));
31 q[d].ca = 0;
32 q[d].cb = 0;
33 q[d].num = 0;
34 q[d].flag = -1;
35 g = 0;
36 while(p!=d)
37 {
38 p++;
39 int ta = q[p].ca;
40 int tb = q[p].cb;
41 int tnum = q[p].num;
42 if(ta==c||tb==c)
43 {
44 flag = 1;
45 break;
46 }
47 if(ta!=a)
48 {
49 na = a;
50 nb = tb;
51 if(!vis[na][nb])
52 {
53 d++;
54 q[d].ca = na;
55 q[d].cb = nb;
56 q[d].flag = p;
57 q[d].op = 1;
58 q[d].ob = 1;
59 q[d].num = tnum+1;
60 vis[na][nb] = 1;
61 }
62 }
63 if(tb!=b)
64 {
65 nb = b;
66 na = ta;
67 if(!vis[na][nb])
68 {
69 d++;
70 q[d].ca = na;
71 q[d].cb = nb;
72 q[d].flag = p;
73 q[d].op = 1;
74 q[d].ob = 2;
75 q[d].num = tnum+1;
76 vis[na][nb] = 1;
77 }
78 }
79 if(ta!=0)
80 {
81 nb = tb;
82 na = 0;
83 if(!vis[na][nb])
84 {
85 d++;
86 q[d].ca = na;
87 q[d].cb = nb;
88 q[d].flag = p;
89 q[d].op = 2;
90 q[d].ob = 1;
91 q[d].num = tnum+1;
92 vis[na][nb] = 1;
93 }
94 }
95 if(tb!=0)
96 {
97 nb = 0;
98 na = ta;
99 if(!vis[na][nb])
100 {
101 d++;
102 q[d].ca = na;
103 q[d].cb = nb;
104 q[d].flag = p;
105 q[d].op = 2;
106 q[d].ob = 2;
107 q[d].num = tnum+1;
108 vis[na][nb] = 1;
109 }
110 }
111 if(tb!=b&&ta!=0)
112 {
113 if(ta+tb<=b)
114 {
115 na = 0;
116 nb = ta+tb;
117 }
118 else
119 {
120 nb = b;
121 na = ta-(b-tb);
122 }
123 if(!vis[na][nb])
124 {
125 d++;
126 q[d].ca = na;
127 q[d].cb = nb;
128 q[d].flag = p;
129 q[d].op = 3;
130 q[d].ob = 1;
131 q[d].num = tnum+1;
132 vis[na][nb] = 1;
133 }
134 }
135 if(ta!=a&&tb!=0)
136 {
137 if(tb+ta<=a)
138 {
139 nb = 0;
140 na = tb+ta;
141 }
142 else
143 {
144 na = a;
145 nb = tb-(a-ta);
146 }
147 if(!vis[na][nb])
148 {
149 d++;
150 q[d].ca = na;
151 q[d].cb = nb;
152 q[d].flag = p;
153 q[d].op = 3;
154 q[d].ob = 2;
155 q[d].num = tnum+1;
156 vis[na][nb] = 1;
157 }
158 }
159 }
160 if(flag)
161 {
162 cout<<q[p].num<<endl;
163 int x = p;
164 while(x!=1)
165 {
166 g++;
167 num[g] = x;
168 x = q[x].flag;
169 }
170 }
171 else
172 puts("impossible");
173 }
174 int main()
175 {
176 int i;
177 while(cin>>a>>b>>c)
178 {
179 bfs();
180 for(i = g ; i >= 1; i--)
181 put(q[num[i]].op,q[num[i]].ob);
182 }
183 return 0;
184 }