1 | 11月 | 2015 | 超客的水墨烟雨

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

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

01 11月 2015

Shuffle'm Up

The actual shuffle operation is performed by interleaving a chip from S₁ with a chip from S₂ as shown below for C = 5:A common pastime for poker players at a poker table is to shuffle stacks of chips. Shuffling chips is performed by starting with two stacks of poker chips, S₁ and S₂, each stack containingC chips. Each stack may contain chips of several different colors.

The single resultant stack, S₁₂, contains 2 * C chips. The bottommost chip of S₁₂ is the bottommost chip from S₂. On top of that chip, is the bottommost chip from S₁. The interleaving process continues taking the 2^nd chip from the bottom of S₂ and placing that on S₁₂, followed by the 2^nd chip from the bottom of S₁ and so on until the topmost chip from S₁ is placed on top of S₁₂.

After the shuffle operation, S₁₂ is split into 2 new stacks by taking the bottommost C chips from S₁₂ to form a new S₁ and the topmost C chips from S₁₂ to form a new S₂. The shuffle operation may then be repeated to form a new S₁₂.

For this problem, you will write a program to determine if a particular resultant stack S₁₂ can be formed by shuffling two stacks some number of times.

Input

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.

Each dataset consists of four lines of input. The first line of a dataset specifies an integer C, (1 ≤ C ≤ 100) which is the number of chips in each initial stack (S₁ and S₂). The second line of each dataset specifies the colors of each of the C chips in stack S₁, starting with the bottommost chip. The third line of each dataset specifies the colors of each of the C chips in stack S₂starting with the bottommost chip. Colors are expressed as a single uppercase letter (A through H). There are no blanks or separators between the chip colors. The fourth line of each dataset contains 2 * C uppercase letters (A through H), representing the colors of the desired result of the shuffling of S₁ and S₂ zero or more times. The bottommost chip’s color is specified first.

Output

Output for each dataset consists of a single line that displays the dataset number (1 though N), a space, and an integer value which is the minimum number of shuffle operations required to get the desired resultant stack. If the desired result can not be reached using the input for the dataset, display the value negative 1 (−1) for the number of shuffle operations.

Sample Input

2
4
AHAH
HAHA
HHAAAAHH
3
CDE
CDE
EEDDCC

Sample Output

1 2

2 -1

Source

Greater New York 2006

题目类型：BFS

算法分析：直接按照题目的规则进行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;

string sa, sb, ss;
int n;

string TT (string &vala, string &valb)
{
    string res;
    for (int i = 0; i < n; i++)
    {
        res += vala[i];
        res += valb[i];
    }
    return res;
}

struct node
{
    string cur;
    int cnt;
    node (string ccur, int ccnt) : cur (ccur), cnt (ccnt) {}
    node () {}
};

int bfs ()
{
    map<string, bool> vis;
    queue <node> qu;
    qu.push (node (TT(sb,sa), 1));
    while (!qu.empty ())
    {
        node tt = qu.front (); qu.pop ();
        if (tt.cur == ss)
            return tt.cnt;

        string ta, tb;
        for (int i = 0; i < n; i++) ta += tt.cur[i];
        for (int i = n; i < 2 * n; i++) tb += tt.cur[i];
        tt.cur = TT (tb, ta);
        if (!vis[tt.cur])
        {
            vis[tt.cur] = true;
            qu.push (node (tt.cur, tt.cnt + 1));
        }
    }
    return -1;
}


int main()
{
//    CPPFF;
    int t, flag = 1;
    cin >> t;
    while(t--)
    {
        cin >> n;
        cin >> sa >> sb >> ss;
        cout << flag++ << " " << bfs () << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

#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;

string sa, sb, ss;

int n;

string TT (string &vala, string &valb)

{

string res;

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

{

res += vala[i];

res += valb[i];

}

return res;

}

struct node

{

string cur;

int cnt;

node (string ccur, int ccnt) : cur (ccur), cnt (ccnt) {}

node () {}

};

int bfs ()

{

map<string, bool> vis;

queue <node> qu;

qu.push (node (TT(sb,sa), 1));

while (!qu.empty ())

{

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

if (tt.cur == ss)

return tt.cnt;

string ta, tb;

for (int i = 0; i < n; i++) ta += tt.cur[i];

for (int i = n; i < 2 * n; i++) tb += tt.cur[i];

tt.cur = TT (tb, ta);

if (!vis[tt.cur])

{

vis[tt.cur] = true;

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

}

return -1;

}

int main()

{

// CPPFF;

int t, flag = 1;

cin >> t;

while(t--)

{

cin >> n;

cin >> sa >> sb >> ss;

cout << flag++ << " " << bfs () << endl;

}

return 0;

}

超客的水墨烟雨

poj3414

poj3087

分类目录

标签云

书签

近期评论

2015年11月
一	二	三	四	五	六	日
« 10月				12月 »
						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