题意分析

本题给定两个沙漏，需要我们根据两个沙漏的计时时间和对应的四个操作，运用一定的算法判断是否能求出给定的时间以及最短路径。初始时刻（t = 0）时，两个沙漏均已翻转，使得所有沙子都在上层，即两个沙漏剩余时间都满。接下来，沙子将从上层流到下层，当沙子全部流完时（即剩余时间为 0）说明该沙漏计时结束。

我们可以简化思考，沙漏需要操作的“节点”和我们寻找的时间，都必须满足任意沙漏计时结束的时间点，通过在沙漏达到“操作点”（即计时结束）时选择题目给出的操作，使得在某个时刻恰好有沙漏耗尽，而此时经过的总时间正好为目标 T 分钟（要求的时间）。题目允许在每个“操作点”时对沙漏进行以下四种操作中的一种：

1、翻转已耗尽的沙漏

2、翻转未耗尽的沙漏

3、同时翻转两个沙漏

4、不翻转

注意：当两个沙漏同时耗尽，或一个沙漏处于闲置状态（上一操作点选择4不操作）而另一个刚耗尽时（即该操作点），必须至少对其中一个沙漏进行翻转，不能“都不翻转”，否则程序就出不来了。

题解思路

题目本质上是一个状态搜索问题，每个状态由当前时间、两个沙漏剩余流沙时间决定。如果当达到时间 T 且此时至少有一个沙漏正好耗尽（即达到操作点）时，记录当前路径，并求出全部这样的路径给出最短路径。而当当前操作点时间 > T，则表示不存在这样的路径。这里使用深度优先搜索（递归回溯法）来解题（理论上广度优先算法也可解），下面给出详细思路：

1、状态定义

时间t：当前经过的总时间。

沙漏状态 r1 和 r2：分别表示两个沙漏当前剩余的流沙时间。如果 r1 或 r2 为 0，表示该沙漏已耗尽或处于闲置状态，此时需要操作（翻转）。

2、初始状态

时间 t = 0，两个沙漏均被翻转，此时两沙漏均为“满沙”，即 r1 = M，r2 = N。

3、等待过程

等待操作：当两个沙漏都在运行（r1 > 0 且 r2 > 0）时，下一个操作点是等待时间为 min(r1, r2) 的时刻，此时至少有一个沙漏刚耗尽；

当只有一个沙漏在运行（另一沙漏已经为 0）时，则等待该沙漏耗尽的时刻，操作时刻为 t + 运行沙漏剩余时间。

4、操作点的分支选择

在每个操作点（至少一个沙漏的剩余时间为 0）时，允许进行如下操作：

操作 A：翻转已耗尽的沙漏（即只对 r == 0 的沙漏翻转，使其剩余时间恢复为满沙）。

操作 B：翻转未耗尽的沙漏（即只对正在运行的沙漏翻转，翻转后剩余时间变为容量减去当前剩余时间）。

操作 C：同时翻转两个沙漏（无论沙漏是否耗尽，都翻转）。

操作 D（空操作）：当只有一只沙漏耗尽、另一只仍在运行时，可以选择不翻转，直接等待运行中的沙漏耗尽。按照题目输出要求不记录该操作。

5、记录路径

这里可以使用一个容器来保存从初始状态到当前状态的所有翻转操作记录。

递归调用后使用一定要撤销这一步操作，实现回溯。

6、出路

即满足条件结束查找，这里有两个条件，一个是找到了解，即 t = T，另一个是找不到解，即 t > T。

本题代码

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int m, n, T;
vector<string> bestPath;
bool foundSolution = false;

void dfs(int t, int r1, int r2, vector<string>& path) {
    if(t > T) return;
    
    if(t == T && (r1 == 0 || r2 == 0)) {
        if(!foundSolution || path.size() < bestPath.size()){
            bestPath = path;
            foundSolution = true;
        }
        return;
    }
    
    if(r1 > 0 && r2 > 0) {
        int dt = min(r1, r2);
        dfs(t + dt, r1 - dt, r2 - dt, path);
        return;
    }
    
    if(r1 == 0 && r2 == 0) {
        
        {
            int new_r1 = m, new_r2 = 0;
            ostringstream oss;
            oss << t << ": " << m;
            path.push_back(oss.str());
        
            dfs(t + new_r1, 0, 0, path);
            path.pop_back();
        }
		
        {
            int new_r1 = 0, new_r2 = n;
            ostringstream oss;
            oss << t << ": " << n;
            path.push_back(oss.str());
            dfs(t + new_r2, 0, 0, path);
            path.pop_back();
        }
        
        {
            int new_r1 = m, new_r2 = n;
            ostringstream oss;
            oss << t << ": " << m << "," << n;
            path.push_back(oss.str());
            int dt = min(new_r1, new_r2);
            dfs(t + dt, new_r1 - dt, new_r2 - dt, path);
            path.pop_back();
        }
        return;
    }
    
    if((r1 == 0 && r2 > 0) || (r2 == 0 && r1 > 0)) {
        int running = (r1 > 0 ? r1 : r2);
        dfs(t + running, 0, 0, path);
    }
    
    {
        int new_r1 = r1, new_r2 = r2;
        ostringstream oss;
        oss << t << ": ";
        bool flip = false;
        if(r1 == 0) { new_r1 = m; oss << m; flip = true; }
        if(r2 == 0) { 
            if(flip) oss << ",";
            new_r2 = n; 
            oss << n; flip = true;
        }
        if(flip) {
            string opStr = oss.str();
            path.push_back(opStr);
            if(new_r1 > 0 && new_r2 > 0) {
                int dt = min(new_r1, new_r2);
                dfs(t + dt, new_r1 - dt, new_r2 - dt, path);
            } else {
                int running = (new_r1 > 0 ? new_r1 : new_r2);
                dfs(t + running, 0, 0, path);
            }
            path.pop_back();
        }
    }
    
    {
        int new_r1 = r1, new_r2 = r2;
        ostringstream oss;
        oss << t << ": ";
        bool flip = false;
        if(r1 > 0) { new_r1 = m - r1; oss << m; flip = true; }
        if(r2 > 0) { 
            if(flip) oss << ",";
            new_r2 = n - r2; oss << n; flip = true;
        }
        if(flip) {
            string opStr = oss.str();
            path.push_back(opStr);
            if(new_r1 > 0 && new_r2 > 0) {
                int dt = min(new_r1, new_r2);
                dfs(t + dt, new_r1 - dt, new_r2 - dt, path);
            } else {
                int running = (new_r1 > 0 ? new_r1 : new_r2);
                dfs(t + running, 0, 0, path);
            }
            path.pop_back();
        }
    }
    
    {
        int new_r1 = (r1 == 0 ? m : m - r1);
        int new_r2 = (r2 == 0 ? n : n - r2);
        ostringstream oss;
        oss << t << ": " << m << "," << n;
        path.push_back(oss.str());
        if(new_r1 > 0 && new_r2 > 0) {
            int dt = min(new_r1, new_r2);
            dfs(t + dt, new_r1 - dt, new_r2 - dt, path);
        } else {
            int running = (new_r1 > 0 ? new_r1 : new_r2);
            dfs(t + running, 0, 0, path);
        }
        path.pop_back();
    }
}

int main(){
    while(cin >> m >> n >> T) {
        if(m == 0 && n == 0 && T == 0) break;
        bestPath.clear();
        foundSolution = false;
        vector<string> path;
        {
            ostringstream oss;
            oss << "0: " << m << "," << n;
            path.push_back(oss.str());
        }
        int dt = min(m, n);
        dfs(dt, m - dt, n - dt, path);
        if(foundSolution) {
            for(size_t i = 0; i < bestPath.size(); i++){
                cout << bestPath[i] << endl;
            }
        } else {
            cout << "Impossible" << endl;
        }
        cout << "----------" << endl;
    }
    return 0;
}