广搜解倒水问题 - C++ 代码实现

#include #include #include

using namespace std;

const int N = 110;

struct node{ int x, y; string path; };

int n, m, k; boolean st[N][N]; node q[N * N];

void bfs(){ int hh = 0, tt = 0; q[tt ++] = {0, 0, ""}; st[0][0] = true;

while(hh != tt){
    auto t = q[hh ++];
    if(t.x == k || t.y == k){
        printf("%d\n", t.path.size());
        cout << t.path << endl;
        return;
    }

    if(!st[n][t.y]) st[n][t.y] = true, q[tt ++] = {n, t.y, t.path + "FILL(1)\n"};
    if(!st[t.x][m]) st[t.x][m] = true, q[tt ++] = {t.x, m, t.path + "FILL(2)\n"};
    if(!st[0][t.y]) st[0][t.y] = true, q[tt ++] = {0, t.y, t.path + "DROP(1)\n"};
    if(!st[t.x][0]) st[t.x][0] = true, q[tt ++] = {t.x, 0, t.path + "DROP(2)\n"};

    int a = min(m - t.y, t.x), b = min(n - t.x, t.y);
    if(!st[t.x - a][t.y + a]) st[t.x - a][t.y + a] = true, q[tt ++] = {t.x - a, t.y + a, t.path + "POUR(1,2)\n"};
    if(!st[t.x + b][t.y - b]) st[t.x + b][t.y - b] = true, q[tt ++] = {t.x + b, t.y - b, t.path + "POUR(2,1)\n"};
}

puts("impossible");

}

int main(){ scanf("%d%d%d", &n, &m, &k); bfs(); return 0; }