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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<P, P> PP;
int memo[105][105][2];
struct State {
int a, b, c, d, cost;
bool flag;
State(int a, int b, int c, int d, int cost, bool flag) : a(a), b(b), c(c), d(d), cost(cost), flag(flag) {}
bool operator<(const State& s) const {
return cost < s.cost;
}
bool operator>(const State& s) const {
return cost > s.cost;
}
};
ostream& operator << (ostream& os, const State& s) {
os << "(" << s.a << ", " << s.b << " | " << s.c << ", " << s.d << ") : " << s.cost << " flag:" << s.flag;
return os;
}
bool ok(State s) {
int a = s.a, b = s.b, c = s.c, d = s.d;
bool f1 = false;
if(a == 0 || b == 0) f1 = true;
if(a >= b) f1 = true;
bool f2 = false;
if(c == 0 || d == 0) f2 = true;
if(c >= d) f2 = true;
return (f1 && f2);
}
class Cannibals {
public:
int minCrossings(int M, int C, int R) {
memset(memo, -1, sizeof(memo));
priority_queue<State, vector<State>, greater<State> > que;
que.push(State(M, C, 0, 0, 0, 0));
memo[M][C][0] = 0;
while(que.size()) {
State s = que.top(); que.pop();
if(s.flag == 0) {
rep(i, s.a + 1) {
rep(j, s.b + 1) {
if(i == 0 && j == 0) continue;
if(i + j > R) continue;
if(i != 0 && j != 0 && i < j) continue;
int a = s.a - i;
int b = s.b - j;
State nc(a, b, s.c + i, s.d + j, s.cost + 1, 1);
if(ok(nc) && memo[nc.a][nc.b][nc.flag] == -1) {
memo[nc.a][nc.b][nc.flag] = nc.cost;
que.push(nc);
}
}
}
} else {
rep(i, s.c + 1) {
rep(j, s.d + 1) {
if(i == 0 && j == 0) continue;
if(i + j > R) continue;
if(i != 0 && j != 0 && i < j) continue;
int c = s.c - i;
int d = s.d - j;
State nc(s.a + i, s.b + j, c, d, s.cost + 1, 0);
if(ok(nc) && memo[nc.a][nc.b][nc.flag] == -1) {
memo[nc.a][nc.b][nc.flag] = nc.cost;
que.push(nc);
}
}
}
}
}
return memo[0][0][1];
}
};
|