AcWing 4222. 罐子

给你两个罐子，容积分别为 A 升和 B 升。

现在，你可以进行如下三种操作：

1. FILL(i)，将罐子 i（1≤i≤2）灌满水。
2. DROP(i)，将罐子 i（1≤i≤2）清空。
3. POUR(i,j)，将罐子 i 中的水倒向罐子 j，直到罐子 i 空了或罐子 j 满了为止。

请问，至少多少次操作后，可以使得其中一个罐子里恰好有 C 升水。

输入格式

共一行，三个整数 A,B,C。

输出格式

如果无解，则输出一行 impossible 即可。

否则，第一行输出一个整数，表示最少操作次数。

随后按顺序每行输出一个操作指令，格式参考题面。

数据范围

1≤A,B,C≤100,
C≤max(A,B)。

输入样例：

3 5 4

输出样例：

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

本题主要在于两点.

1 如何储存答案;

2 如何模拟这个过程

对于问题1,首先我们把六种情况分别用字符串的1,2,3,4,5,6表示并储存

对于问题2,我们把这个过程模拟成二维数组,就可以解决了 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;
constexpr int N=100+7;
//#define int long long
typedef pair<int,int>PII;
int a,b,c;
string ans[N][N];
string res;
bool st[N][N];
void bfs(){queue<PII>q;q.push({0,0});st[0][0]= true;while(q.size()){auto t=q.front();q.pop();if(t.first == c || t.second == c) {res=ans[t.first][t.second]; break;}string& s=ans[t.first][t.second];if(!st[a][t.second]){st[a][t.second]= true;q.push({a,t.second});ans[a][t.second]=s+'1';}if(!st[t.first][b]){st[t.first][b]= true;q.push({t.first,b});ans[t.first][b]=s+'2';}if(!st[0][t.second]){st[0][t.second]= true;q.push({0,t.second});ans[0][t.second]=s+'3';}if(!st[t.first][0]){st[t.first][0]= true;q.push({t.first,0});ans[t.first][0]= s+'4';}int minn= min(t.first,b-t.second);if(!st[t.first-minn][t.second+minn]){st[t.first-minn][t.second+minn]=true;ans[t.first-minn][t.second+minn]=s+'5';q.push({t.first-minn,t.second+minn});}minn= min(a-t.first,t.second);if(!st[t.first+minn][t.second-minn]){st[t.first+minn][t.second-minn]=true;ans[t.first+minn][t.second-minn]=s+'6';q.push({t.first+minn,t.second-minn});}}
}
signed main() {ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>a>>b>>c;bfs();if(res.size()==0) cout<<"impossible"<<endl;else{cout << res.size() << endl;for(auto k : res){if(k == '1') cout << "FILL(1)\\n";if(k == '2') cout << "FILL(2)\\n";if(k == '3') cout << "DROP(1)\\n";if(k == '4') cout << "DROP(2)\\n";if(k == '5') cout << "POUR(1,2)\\n";if(k == '6') cout << "POUR(2,1)\\n";}}return 0;
}