搜索小练#8

Posted on Edited on In

题目

这里很容易想到广搜，设初始状态为\((i,j)\)，一共就只有六种变化

A杯倒满，B杯倒满，A杯倒出完，B杯倒出完，A到给B，B到给A

任意一种状态\(i\) 或者 \(j\)达到 \(C\) 就停止，注意要打印路径，我这里用一个string存的操作顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int N = 1e2+100;

int a, b, c;
int v[N][N];
bool flag = false;
string str[10] = {"", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)","POUR(2,1)"};

struct node {
    int x, y, step; string s;
    node (int x, int y, int step, string s):x(x), y(y), step(step),s(s){}
};

inline void bfs () {
    queue<node>q;
    v[0][0] = 1;
    q.push(node(0, 0, 0, "0"));
    while(!q.empty()) {
        /* code */
        node tmp = q.front(); q.pop();
        if (tmp.x == c || tmp.y == c) {
            flag = 1;
            cout << tmp.step << '\n';
            for (int i = 1; i < tmp.s.length(); ++ i)
                cout << str[tmp.s[i]-'0'] << '\n';
            return;
        }
        if (tmp.x < a)
            if (!v[a][tmp.y])
                v[a][tmp.y] = 1, q.push(node(a, tmp.y, tmp.step+1, tmp.s+"1"));
        if (tmp.y < b)
            if (!v[tmp.x][b])
                v[tmp.x][b] = 1, q.push(node(tmp.x, b, tmp.step+1, tmp.s+"2"));
        if (tmp.x != 0)
            if (!v[0][tmp.y])
                v[0][tmp.y] = 1, q.push(node(0, tmp.y, tmp.step+1, tmp.s+"3"));
        if (tmp.y != 0)
            if (!v[tmp.x][0])
                v[tmp.x][0] = 1, q.push(node(tmp.x, 0, tmp.step+1, tmp.s+"4"));
        if (tmp.x != 0 && tmp.y < b) {
            int nx, ny;
            if (tmp.x <= b-tmp.y) nx = 0, ny = tmp.x+tmp.y;
            else nx = tmp.x+tmp.y-b, ny = b;
            if (!v[nx][ny]) 
                v[nx][ny] = 1, q.push(node(nx, ny, tmp.step+1, tmp.s+"5"));
        }
        if (tmp.y != 0 && tmp.x < a) {
            int nx, ny;
            if (tmp.y <= a-tmp.x) nx = tmp.x+tmp.y, ny = 0;
            else nx = a, ny = tmp.x+tmp.y-a;
            if (!v[nx][ny]) 
                v[nx][ny] = 1, q.push(node(nx, ny, tmp.step+1, tmp.s+"6"));
        }
    }
}

int main () {
    cin >> a >> b >> c;
    bfs ();
     if (!flag) puts ("impossible");	
    return 0;
}

分为六种情况讨论

反正现在的我一眼看上去，不知道正解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/*
 * By Youngore
 * Time:20.10.16
 * */
#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
const int N = 110;

int a, b, c, flg;
int v[N][N];
string str[10] = {"", "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
struct yhy
{
	int x, y, stp;
	string s;
	yhy(int x, int y, int stp, string s):x(x), y(y), stp(stp), s(s){}
};

inline void bfs()
{
	queue<yhy>q; v[0][0] = 1;
	q.push(yhy(0, 0, 0, "0"));
	while (! q.empty())
	{
		yhy tmp = q.front(); q.pop();
		if (tmp.x == c || tmp.y == c)
		{
			flg = 1;
			cout << tmp.stp << '\n';
			for (int i = 1; i <= tmp.stp; ++ i) cout << str[tmp.s[i] - '0'] << '\n';
			break;
		}
		if (tmp.x != a && ! v[a][tmp.y])
		{
			v[a][tmp.y] = 1;
			q.push(yhy(a, tmp.y, tmp.stp + 1, tmp.s + "1"));
		}
		if (tmp.y != b && ! v[tmp.x][b])
		{
			v[tmp.x][b] = 1;
			q.push(yhy(tmp.x, b, tmp.stp + 1, tmp.s + "2"));
		}
		if (tmp.x && ! v[0][tmp.y])
		{
			v[0][tmp.y] = 1;
			q.push(yhy(0, tmp.y, tmp.stp + 1, tmp.s + "3"));
		}
		if (tmp.y && !v[tmp.x][0])
		{
			v[tmp.x][0] = 1;
			q.push(yhy(tmp.x, 0, tmp.stp + 1, tmp.s + "4"));
		}
		if (tmp.x && tmp.y != b)
		{
			int nx, ny;
			if (tmp.y + tmp.x <= b) nx = 0, ny = tmp.x + tmp.y;
			else nx = tmp.x + tmp.y - b, ny = b;
			if (! v[nx][ny]) q.push(yhy(nx, ny, tmp.stp + 1, tmp.s + "5"));
		}
		if (tmp.y && tmp.x != a)
		{
			int nx, ny;
			if (tmp.x + tmp.y <= a) nx = tmp.x + tmp.y, ny = 0;
			else nx = a, ny = tmp.x + tmp.y - a;
			if (! v[nx][ny]) q.push(yhy(nx, ny, tmp.stp + 1, tmp.s + "6"));
		}

	}
	if (! flg) puts("impossible");
	return;
}

inline int youngore()
{
	scanf ("%d%d%d", &a, &b, &c);
	bfs();
	return 0;
}

int search_ex = youngore();

signed main() {;};