poj3414

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

01 11月 2015

Pots

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed: FILL(i): fill the poti (1 ≤ i ≤ 2) from the tap; DROP(i): empty the poti to the drain; POUR(i,j): pour from poti to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3 5 4

Sample Output

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

Source

Northeastern Europe 2002, Western Subregion

题目类型：BFS+记录路径

算法分析：注意在记录路径的时候要分好类

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int A, B, C, vis[166][166];

struct node
{
    int a, b, cnt;
    node (int aa, int bb, int ccnt) : a (aa), b (bb), cnt (ccnt) {}
    node () {}
};

struct point
{
    int a, b, flag;
};

point par[166][166], out[666];
int pa, pb;

int bfs ()
{
    memset (vis, false, sizeof (vis));
    for (int i = 0; i < 166; i++)
        for (int j = 0; j < 166; j++)
            par[i][j].a = par[i][j].b = par[i][j].flag = -1;

    vis[0][0] = true;
    queue <node> qu;
    qu.push (node (0, 0, 0));
    while (!qu.empty ())
    {
        node tt = qu.front (); qu.pop ();
        if (tt.a == C || tt.b == C)
        {
            pa = tt.a, pb = tt.b;
            return tt.cnt;
        }
        int ta = tt.a, tb = B;
        if (!vis[ta][tb])
        {
            vis[ta][tb] = true;
            qu.push (node (ta, tb, tt.cnt + 1));
            par[ta][tb].a = tt.a;
            par[ta][tb].b = tt.b;
            par[ta][tb].flag = 1;
        }

        ta = A, tb = tt.b;
        if (!vis[ta][tb])
        {
            vis[ta][tb] = true;
            qu.push (node (ta, tb, tt.cnt + 1));
            par[ta][tb].a = tt.a;
            par[ta][tb].b = tt.b;
            par[ta][tb].flag = 2;
        }

        ta = 0, tb = tt.b;
        if (!vis[ta][tb])
        {
            vis[ta][tb] = true;
            qu.push (node (ta, tb, tt.cnt + 1));
            par[ta][tb].a = tt.a;
            par[ta][tb].b = tt.b;
            par[ta][tb].flag = 3;
        }

        ta = tt.a, tb = 0;
        if (!vis[ta][tb])
        {
            vis[ta][tb] = true;
            qu.push (node (ta, tb, tt.cnt + 1));
            par[ta][tb].a = tt.a;
            par[ta][tb].b = tt.b;
            par[ta][tb].flag = 4;
        }

        int tk = min (tt.a, B - tt.b);
        ta = tt.a - tk, tb = tt.b + tk;
        if (!vis[ta][tb])
        {
            vis[ta][tb] = true;
            qu.push (node (ta, tb, tt.cnt + 1));
            par[ta][tb].a = tt.a;
            par[ta][tb].b = tt.b;
            par[ta][tb].flag = 5;
        }

        tk = min (tt.b, A - tt.a);
        ta = tt.a + tk, tb = tt.b - tk;
        if (!vis[ta][tb])
        {
            vis[ta][tb] = true;
            qu.push (node (ta, tb, tt.cnt + 1));
            par[ta][tb].a = tt.a;
            par[ta][tb].b = tt.b;
            par[ta][tb].flag = 6;
        }
    }
    return -1;
}

int main()
{
//    CFF;
    while (scanf ("%d %d %d", &A, &B, &C) != EOF)
    {
        int tt = bfs ();
        if (tt == -1)
            puts ("impossible");

        else
        {
            printf ("%d\n", tt);
            int len = 0;
            do
            {
                out[len].a = par[pa][pb].a;
                out[len].b = par[pa][pb].b;
                out[len++].flag = par[pa][pb].flag;
                int tta = par[pa][pb].a, ttb = par[pa][pb].b;
                pa = tta, pb = ttb;
            } while (pa != -1 && pb != -1);
            for (int i = len - 1; i >= 0; i--)
            {
                if (out[i].flag == 1) puts ("FILL(2)");
                if (out[i].flag == 2) puts ("FILL(1)");
                if (out[i].flag == 3) puts ("DROP(1)");
                if (out[i].flag == 4) puts ("DROP(2)");
                if (out[i].flag == 5) puts ("POUR(1,2)");
                if (out[i].flag == 6) puts ("POUR(2,1)");
            }
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int A, B, C, vis[166][166];

struct node

{

int a, b, cnt;

node (int aa, int bb, int ccnt) : a (aa), b (bb), cnt (ccnt) {}

node () {}

};

struct point

{

int a, b, flag;

};

point par[166][166], out[666];

int pa, pb;

int bfs ()

{

memset (vis, false, sizeof (vis));

for (int i = 0; i < 166; i++)

for (int j = 0; j < 166; j++)

par[i][j].a = par[i][j].b = par[i][j].flag = -1;

vis[0][0] = true;

queue <node> qu;

qu.push (node (0, 0, 0));

while (!qu.empty ())

{

node tt = qu.front (); qu.pop ();

if (tt.a == C || tt.b == C)

{

pa = tt.a, pb = tt.b;

return tt.cnt;

}

int ta = tt.a, tb = B;

if (!vis[ta][tb])

{

vis[ta][tb] = true;

qu.push (node (ta, tb, tt.cnt + 1));

par[ta][tb].a = tt.a;

par[ta][tb].b = tt.b;

par[ta][tb].flag = 1;

}

ta = A, tb = tt.b;

if (!vis[ta][tb])

{

vis[ta][tb] = true;

qu.push (node (ta, tb, tt.cnt + 1));

par[ta][tb].a = tt.a;

par[ta][tb].b = tt.b;

par[ta][tb].flag = 2;

}

ta = 0, tb = tt.b;

if (!vis[ta][tb])

{

vis[ta][tb] = true;

qu.push (node (ta, tb, tt.cnt + 1));

par[ta][tb].a = tt.a;

par[ta][tb].b = tt.b;

par[ta][tb].flag = 3;

}

ta = tt.a, tb = 0;

if (!vis[ta][tb])

{

vis[ta][tb] = true;

qu.push (node (ta, tb, tt.cnt + 1));

par[ta][tb].a = tt.a;

par[ta][tb].b = tt.b;

par[ta][tb].flag = 4;

}

int tk = min (tt.a, B - tt.b);

ta = tt.a - tk, tb = tt.b + tk;

if (!vis[ta][tb])

{

vis[ta][tb] = true;

qu.push (node (ta, tb, tt.cnt + 1));

par[ta][tb].a = tt.a;

par[ta][tb].b = tt.b;

par[ta][tb].flag = 5;

}

tk = min (tt.b, A - tt.a);

ta = tt.a + tk, tb = tt.b - tk;

if (!vis[ta][tb])

{

vis[ta][tb] = true;

qu.push (node (ta, tb, tt.cnt + 1));

par[ta][tb].a = tt.a;

par[ta][tb].b = tt.b;

par[ta][tb].flag = 6;

}

return -1;

}

int main()

{

// CFF;

while (scanf ("%d %d %d", &A, &B, &C) != EOF)

{

int tt = bfs ();

if (tt == -1)

puts ("impossible");

else

{

printf ("%d\n", tt);

int len = 0;

{

out[len].a = par[pa][pb].a;

out[len].b = par[pa][pb].b;

out[len++].flag = par[pa][pb].flag;

int tta = par[pa][pb].a, ttb = par[pa][pb].b;

pa = tta, pb = ttb;

} while (pa != -1 && pb != -1);

for (int i = len - 1; i >= 0; i--)

{

if (out[i].flag == 1) puts ("FILL(2)");

if (out[i].flag == 2) puts ("FILL(1)");

if (out[i].flag == 3) puts ("DROP(1)");

if (out[i].flag == 4) puts ("DROP(2)");

if (out[i].flag == 5) puts ("POUR(1,2)");

if (out[i].flag == 6) puts ("POUR(2,1)");

}

return 0;

}

poj3087

fzu2150

超客的水墨烟雨

poj3414

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	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