---

title: "bfs+模拟"
author: Sun-Wind
date: February 2,2022

水一道绿题，整体思路和八数码很像，哈希表存解，然后常规模拟即可

#include<iostream>
#include<utility>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
#define fi(i,a,b) for(int i = a; i <= b; ++i)
#define fr(i,a,b) for(int i = a; i >= b; --i)
#define x first
#define y second
#define sz(x) ((int)(x).size())
#define pb push_back
using pii = pair<int,int>;
//#define DEBUG
int T,ca,cb,n,a,b;
bool vis[1005][1005];
struct water{
    int a,b,step;
    string res;
};
void bfs(){
    queue<water> que;
    que.push({0,0,0});
    while(!que.empty()){
        water temp = que.front();
        que.pop();
        if(temp.b == n){
            cout << temp.step << " ";
            cout << temp.res[0];
            fi(i,1,sz(temp.res)-1) cout << " " << temp.res[i];
            cout << endl;
            return;
        }
        fi(i,1,6){
            if(i == 1){
                if(temp.a < ca) 
                    {
                        if(!vis[ca][temp.b])
                            que.push({ca,temp.b,temp.step+1,temp.res + '1'}),vis[ca][temp.b] = true;
                    }
            }
            if(i == 2){
                if(temp.b < cb) 
                    {
                        if(!vis[temp.a][cb])
                            que.push({temp.a,cb,temp.step+1,temp.res + '2'}),vis[temp.a][cb] = true;
                    }
            }
            if(i == 3){
                if(temp.a != 0)
                    {
                        if(!vis[0][temp.b])
                            que.push({0,temp.b,temp.step+1,temp.res + '3'}),vis[0][temp.b] = true;
                    }
            }
            if(i == 4){
                if(temp.b != 0)
                    {
                        if(!vis[temp.a][0])
                            que.push({temp.a,0,temp.step+1,temp.res + '4'}),vis[temp.a][0];
                    }
            }
            if(i == 5){
                if(temp.b != 0 && temp.a != ca){
                    int v = min(temp.a+temp.b,ca);
                    int a = temp.b - (v - temp.a);
                    if(!vis[v][a])
                        que.push({v,a,temp.step+1,temp.res+'5'}),vis[v][a] = true;
                }
            }
            if(i == 6){
               if(temp.a != 0 && temp.b != cb){
                    int v = min(temp.b+temp.a,cb);
                    int a = temp.a - (v - temp.b);
                    if(!vis[a][v])
                        que.push({a,v,temp.step+1,temp.res+'6'}),vis[v][a] = true;
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while(T--){
        fi(i,0,1000) fi(j,0,1000) vis[i][j] = false;
        cin >> ca >> cb >> n;
        vis[0][0] = true;
        bfs();
    }
#ifdef DEBUG
    //freopen(D:\in.txt,r,stdin);
#endif
    return 0;
}