状态空间搜索的很多问题
需要自己建图,这篇博文是对上一篇的一些内容做了扩展

BFS和DFS在IDA*处理中的异同

ZOJ2669

ZOJ2669-1
ZOJ2669-2

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
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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
//
// main.cpp
// ZOJ2669
//
// Created by zhangmin chen on 2019/7/7.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 10;
const int inf = 0x3f3f3f3f;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)


const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

class Grid {
public:
int x, y;
Grid(int _x = 0, int _y = 0) : x(_x), y(_y) {}

bool operator< (const Grid& rhs) const {
return x < rhs.x || (x == rhs.x && y < rhs.y);
}
};

typedef set<Grid> Post;
set<Post> depth[maxn + 1];
// depth begin from [1, n]
int ans[maxn + 5][maxn + 5][maxn + 5];

int n, w, h;

void init() {
Set(ans, 0);
_for(i, 0, maxn) depth[i].clear();
}

void init2() {
Post beg;
beg.insert(Grid(0, 0));
depth[1].insert(beg);
}

// from depth 1, then expand the solution tree

Post normalize(const Post& p) {
Post p2;
int minX = inf, minY = inf;

for(auto& grid : p) {
minX = min(minX, grid.x);
minY = min(minY, grid.y);
}

for(auto& grid : p) {
p2.insert(Grid(grid.x - minX, grid.y - minY));
}
return p2;
}

Post _rotate(const Post& p) {
Post p2;
for(auto& grid : p) {
p2.insert(Grid(grid.y, -grid.x));
}
return normalize(p2);
}

Post _flip(const Post& p) {
Post p2;
for(auto& grid : p) {
p2.insert(Grid(grid.x, -grid.y));
}
return normalize(p2);
}

// in dfs, if d == maxd, try to insert
// posture to depth[d]
bool tryInsert(Post p, int d) {
_for(i, 0, 4) {
p = _rotate(p);
if(depth[d].count(p)) return false;
}

p = _flip(p);

_for(i, 0, 4) {
p = _rotate(p);
if(depth[d].count(p)) return false;
}

depth[d].insert(p);
return true;
}

//
void dfs(Post p, int d, int maxd) {
if(d == maxd) {
tryInsert(p, d);
return;
}

for(auto grid : p) _for(dir, 0, 4) {
Grid nxtG(grid.x + dx[dir], grid.y + dy[dir]);
if(!p.count(nxtG)) {
Post p2 = p;
p2.insert(nxtG);
dfs(p2, d+1, maxd);
}
}
}

void bfs(int d, int maxd) {
queue<Post> que;
for(auto p : depth[d]) que.push(p);

while (!que.empty()) {
Post f = que.front();
que.pop();

if(f.size() == maxd) {
tryInsert(f, maxd);
continue;
}

for(auto grid : f) _for(dir, 0, 4) {
Grid nxtG(Grid(grid.x + dx[dir], grid.y + dy[dir]));
if(!f.count(nxtG)) {
Post p2 = f;
p2.insert(nxtG);
if(p2.size() <= maxd) que.push(p2);
}
}
}
}


void printTable() {
//
init();
init2();
/*
_rep(maxd, 2, maxn) for(auto p : depth[maxd - 1])
dfs(p, maxd - 1, maxd);
*/
_rep(maxd, 2, maxn) bfs(maxd - 1, maxd);

_rep(n, 2, maxn) _rep(w, 1, maxn) _rep(h, 1, maxn) {
int cnt = 0;

for(auto p : depth[n]) {
int maxX = 0, maxY = 0;
for(auto grid : p) {
maxX = max(maxX, grid.x);
maxY = max(maxY, grid.y);
}
if(min(maxX, maxY) < min(w, h) && max(maxX, maxY) < max(w, h))
cnt++;
}

ans[n][w][h] = cnt;
//debug(ans[n][w][h]);
}
//for(auto g : depth[1]) for(auto p : g) cout << p.x << " " << p.y << endl;
}

int main() {
freopen("input.txt", "r", stdin);
printTable();

while (scanf("%d%d%d", &n, &w, &h) == 3) {
// solve()
if(n == 1) {
printf("1\n");
continue;
}

printf("%d\n", ans[n][w][h]);
}

}

dfs处理方法
IDA*外层循环for(auto p : depth[maxd - 1])
遍历深度为maxd - 1的解答树,并且获取状态p
dfs时候只针对p这单一状态,往下扩张

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dfs(Post p, int d, int maxd) {
if(d == maxd) {
tryInsert(p, d);
return;
}

for(auto grid : p) _for(dir, 0, 4) {
Grid nxtG(grid.x + dx[dir], grid.y + dy[dir]);
if(!p.count(nxtG)) {
Post p2 = p;
p2.insert(nxtG);
dfs(p2, d+1, maxd);
}
}
}

int solve() {
_rep(maxd, 2, maxn) for(auto p : depth[maxd - 1])
dfs(p, maxd - 1, maxd);
}

bfs处理方法
bfs逐层扩展解答树
解答树从d->maxd expand
当前在解答树的d层,获取d层的状态进队列

值得注意的是,需要有一个flag标志或者是dist标志,来退出解答树的扩张

1
2
3
4
5
6
while(!que.empty()) {
int x = que.front(); que.pop();
if(x is the exist point)
not expand x
continue;
}
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
void bfs(int d, int maxd) {
queue<Post> que;
for(auto p : depth[d]) que.push(p);

while (!que.empty()) {
Post f = que.front();
que.pop();

if(f.size() == maxd) {
tryInsert(f, maxd);
continue;
}

for(auto grid : f) _for(dir, 0, 4) {
Grid nxtG(Grid(grid.x + dx[dir], grid.y + dy[dir]));
if(!f.count(nxtG)) {
Post p2 = f;
p2.insert(nxtG);
if(p2.size() <= maxd) que.push(p2);
}
}
}
}

int solve() {
_rep(maxd, 2, maxn) bfs(maxd - 1, maxd);
}

IDA与图遍历的路径输出(sstream), 把路径看成IDA的状态

LA5147

1/ 并查集的处理

1
2
3
4
5
6
int findset(int x) {
return pa[x] == x ? x : pa[x] = findset(pa[x]);
}

常见错误直接return findset(pa[x])
正确的写法是pa[x] = findset(pa[x])

pa[x] = findset(pa[x])完成递归而不是findset(pa[x])

2/ 图的路径打印,转成字符串输出
stringstream的用法

1
2
3
4
5
6
7
8
9
10
11
ostream& operator<< (ostream& os, const vector<int>& path) {
_for(i, 0, path.size()) {
os << ' ';
os << path[i];
}
return os;
}

stringstream ss;
ss << path;
pathstr.push_back(ss.str());

stringstream还有一种用法比较常见
获取字符串流,字符串流中有空格,我们需要用空格分隔字串,然后依次读入字串

1
2
3
4
5
vector<string> words;
stringstream ss(str);
string tmp;

while(ss >> tmp) words.push_back(tmp);

3/ dfs执行图的路径输出
如果要输出所有路径,if(u == dest)时候不需要return
这时候需要有穷遍历vectorG[maxn]
其中u->dest的连通性,保证了_for(i, 0, G[u].size()) v = G[u][i]是有穷的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int u, int dest, vector<int>& path) {
path.push_back(u)

if(u == dest) {
...
}

_for(i, 0, G[u].size()) {
int v = G[u][i];
...
dfs(v, dest, path);
}

path.pop_back();
}

path.push_back(u), path.pop_back()完成回溯

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
112
113
114
115
116
117
118
119
120
121
122
123
124
//
// main.cpp
// LA5147
//
// Created by zhangmin chen on 2019/7/7.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int maxn = 20 + 5;


#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

int pa[maxn];
set<int> G[maxn];
int n, k;

// Graph start from 1

void init() {
//
Set(pa, 0);
_for(i, 0, maxn) G[i].clear();
}

void initSet() {
_for(i, 0, maxn) pa[i] = i;
}

int findSet(int x) {
return pa[x] == x ? x : (pa[x] = findSet(pa[x]));
}

// regard path as status in IDA*
// expand path

ostream& operator<< (ostream& os, const vector<int>& path) {
bool first = true;
_for(i, 0, path.size()) {
if(first) first = false;
else os << ' ';
os << path[i];
}
return os;
}

void dfs(int u, int dest, vector<int>& path, vector<string>& paths) {
path.push_back(u);

if(u == dest) {
stringstream ss;
ss << path;
paths.push_back(ss.str());
}

_forS(i, G[u].begin(), G[u].end()) {
int v = *i;
if(find(path.begin(), path.end(), v) != path.end()) continue;
dfs(v, dest, path, paths);
}

path.pop_back();
}

int main() {
//
freopen("input.txt", "r", stdin);
for(int kase = 1, from, to; scanf("%d", &k) == 1 && k; kase++) {
init();
initSet();
while(true) {
scanf("%d%d", &from, &to);
if(from == 0 || to == 0) break;
G[from].insert(to);
G[to].insert(from);

int p1 = findSet(from);
int p2 = findSet(to);
if(p1 != p2) pa[p1] = p2;
}

// finish build graph
// then solve()

vector<int> path;
vector<string> paths;
if(findSet(pa[1]) == findSet(pa[k])) dfs(1, k, path, paths);

printf("CASE %d:\n", kase);
_for(i, 0, paths.size()) cout << paths[i] << endl;
printf("There are %lu routes from the firestation to streetcorner %d.\n", paths.size(), k);
}
}

图形路径输出(LA5164)

LA5164
LA5164

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
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
//
// main.cpp
// LA5164
//
// Created by zhangmin chen on 2019/7/9.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int maxn = 20 + 5;
const int maxk = 50 + 5;
const int MAX = 256;
int N, K;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _forV(i, l, r) for(vector<Pos>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)


class Pos {
public:
int x, y;
Pos(int _x = 0, int _y = 0) : x(_x), y(_y) {}
};

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const char DIR[] = {'w', 's', 'e', 'n'};
// (dx[dir], dy[dir]) => DIR[dir]

vector<Pos> blocks;
int vis[MAX * 2][MAX * 2];

bool inRange(int x, int left, int right) {
if(left > right) return inRange(x, right, left);
return left <= x && x <= right;
}

bool isBlock(const Pos& src, const Pos& dest) {
if(src.x == dest.x) {
for(auto b : blocks) {
if(src.x == b.x && inRange(b.y, src.y, dest.y)) return true;
}
}
else if(src.y == dest.y) {
for(auto b : blocks) {
if(src.y == b.y && inRange(b.x, src.x, dest.x)) return true;
}
}
return false;
}


void init() {
blocks.clear();
Set(vis, 0);
}

ostream& operator<< (ostream& os, const vector<char>& path) {
for(const auto p : path) os << p;
return os;
}

bool h(const Pos& pos, const vector<char>& path) {
int dist = abs(pos.x) + abs(pos.y);
int d = (int)path.size();
int walk = (N + d + 1) * (N - d) / 2;

return walk < dist;
}
// usage: if(h(pos, path)) dfs return

void dfs(const Pos& pos, vector<char>& path, vector<string>& paths) {
if(path.size() == N) {
if(pos.x == 0 && pos.y == 0) {
stringstream ss;
ss << path;
paths.push_back(ss.str());
}
return;
}

if(h(pos, path)) return;

_for(dir, 0, 4) {
// find invalid move
const char D = DIR[dir];
int len = (int)path.size() + 1;
if(path.size()) {
const char last = path.back();

if(last == D) continue;
if(last == 'w' && D == 'e') continue;
if(last == 'n' && D == 's') continue;
if(last == 'e' && D == 'w') continue;
if(last == 's' && D == 'n') continue;
}

Pos nxt(pos.x + dx[dir] * len, pos.y + dy[dir] * len);
if(isBlock(pos, nxt)) continue;

if(vis[nxt.x + MAX][nxt.y + MAX]) continue;

vis[nxt.x + MAX][nxt.y + MAX] = 1;
path.push_back(D);
dfs(nxt, path, paths);
path.pop_back();
vis[nxt.x + MAX][nxt.y + MAX] = 0;
}
}


int main() {
freopen("input.txt", "r", stdin);
int kase;
scanf("%d", &kase);

while (kase--) {
init();
scanf("%d%d", &N, &K);
Pos b;
_for(i, 0, K) {
scanf("%d%d", &b.x, &b.y);
blocks.push_back(b);
}

// finish input
// solve the problem
Pos src(0, 0);
vector<char> path;
vector<string> paths;

dfs(src, path, paths);

sort(paths.begin(), paths.end());
_for(i, 0, paths.size()) cout << paths[i] << endl;
printf("Found %lu golygon(s).\n\n", paths.size());
}
}

网格问题: 一个状态占用多个格子(LA5150)

数据处理: 行单向扩展

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
void init() {
int cnt = 0;
_for(i, 0, ROW) _for(j, i, COL) {
Pos& cur = cards[cnt];
cur.x = i; cur.y = j;
getCard[i][j] = cnt++;
}
}

bool nxt(Pos& pos) {
int r = pos.x, c = pos.y;
c++;
r += c / COL; c %= COL;
if(r >= ROW) return false
pos.x = r, pos.y = c;
return true;
}

usage: in grid
_for(i, 0, R) _for(j, 0, C)
const Card& cur = cards[getCard[i][j]];


int main() {
Pos st(0, 0);
while(true) {
if(scanf("%d", &grid[st.x][st.y]) != 1) break;
while(nxt(st)) cin >> grid[st.x][st.y];
}
}

状态dfs求解的时候,对每一个节点,要给出预留的扩展空间

LA5150
LA5150

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
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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
//
// main.cpp
// LA5150
//
// Created by zhangmin chen on 2019/7/11.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int COL = 8;
const int ROW = 7;
const int dx[] = {0, 1};
const int dy[] = {1, 0};
const int maxn = 28;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

class Pips {
public:
int x, y;
Pips(int _x = 0, int _y = 0) : x(_x), y(_y) {}
};

int grid[ROW][COL], ans[ROW][COL];

int getCard[ROW][ROW];
Pips cards[maxn];

// cards <-> getCard[][]
// usage: cards[getCard[i][j]]
// ID = getCard[i][j]


void init() {
Set(grid, 0);
Set(ans, -1);
Set(cards, 0);
Set(getCard, -1);
}

int read() {
int x;
scanf("%d", &x);
return x;
}

void initCards() {
int cnt = 0;

_for(i, 0, ROW) _for(j, i, ROW) {
Pips& cur = cards[cnt];

cur.x = i; cur.y = j;
getCard[i][j] = cnt;

cnt++;
}
}

int getBone(int x, int y) {
if(x > y) return getBone(y, x);
return getCard[x][y];
}

bool nxt(Pips& pos) {
int pr = pos.x, pc = pos.y;
pc++;

pr += pc / COL;
pc %= COL;

if(pr >= ROW) return false;
pos.x = pr; pos.y = pc;

return true;
}

bool inRange(int x, int left, int right) {
if(left >= right) return inRange(x, right, left);
return left <= x && x <= right;
}

bool valid(int r, int c) {
return inRange(r, 0, ROW - 1) && inRange(c, 0, COL - 1);
}

void dfs(const Pips& pos, set<int> cardID, int& cnt) {
if(cardID.size() == maxn) {
cnt++;
_for(i, 0, ROW) {
printf(" ");
_for(j, 0, COL) printf("%4d", ans[i][j] + 1);
printf("\n");
}
printf("\n");
return;
}

// then cut stretch
// if cur position is been assigned
// dfs from _nxt
Pips _nxt = pos;
if(ans[_nxt.x][_nxt.y] != -1) {
if(nxt(_nxt)) dfs(_nxt, cardID, cnt);
return;
}

// then assign the card
_nxt = pos;
if(!nxt(_nxt)) return;

_for(dir, 0, 2) {
int px = pos.x, py = pos.y;
int nx = px + dx[dir], ny = py + dy[dir];

if(!valid(nx, ny)) continue;
if(ans[nx][ny] != -1) continue;

int _bone = getBone(grid[px][py], grid[nx][ny]);
if(_bone != -1 && !cardID.count(_bone)) {
Pips _nxt = pos; nxt(_nxt);

ans[px][py] = ans[nx][ny] = _bone;
cardID.insert(_bone);
dfs(_nxt, cardID, cnt);
cardID.erase(_bone);
ans[px][py] = ans[nx][ny] = -1;
}
}
}



int main() {
freopen("input.txt", "r", stdin);
init();
initCards();

int kase = 1;
while (true) {
Pips st(0, 0);
if(scanf("%d", &grid[st.x][st.y]) != 1) break;
while(nxt(st)) grid[st.x][st.y] = read();

// finish input
// then solve()

if(kase > 1) printf("\n\n\n");
printf("Layout #%d:\n\n", kase);
_for(i, 0, ROW) {
_for(j, 0, COL) printf("%4d", grid[i][j]);
printf("\n");
}
printf("\nMaps resulting from layout #%d are:\n\n", kase);


int cnt = 0;
set<int> cardID;
dfs(Pips(), cardID, cnt);

printf("There are %d solution(s) for layout #%d.\n", cnt, kase);

kase++;
init();
initCards();
}

}

求解策略

递推

URAL1309
URAL1309

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
112
113
114
115
//
// main.cpp
// URAL1309
//
// Created by zhangmin chen on 2019/7/11.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>


using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int M = 9973;
const int maxn = 50000;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)


int _pow(int x, int k) {
int ans = 1;
_for(i, 0, k) ans = (ans * x) % M;
return ans;
}

void _mod(int& x) {
x %= M;
if(x < 0) x += M;
}

int _A(int x) {
int ans = 0;
ans = (_pow(x, 5) - x + 7);
_mod(ans);
return ans;
}

int _B(int x) {
int ans = 0;
ans = -1 * _pow(x, 5) + _pow(x, 3) + 3 * x;
_mod(ans);
return ans;
}

int f[maxn];
void init() {
Set(f, 0);
}

int main() {
freopen("input.txt", "r", stdin);
int n;
scanf("%d", &n);
init();

int b = n % M;

// recursive: [1, b]
_rep(i, 1, b) {
int A0 = _A(i);
int B0 = _B(i);
f[i] = A0 * f[i - 1] + B0;
_mod(f[i]);
}

// coefficent: [b+1, b+M], get A(b+M)f(x) + B(b+M)
int A = 1, B = 0;
_rep(i, b+1, b+M) {
//
int Ai = _A(i);
int Bi = _B(i);
f[i] = Ai * f[i - 1] + Bi;

A *= Ai;
B = B * Ai + Bi;
_mod(A);
_mod(B);
_mod(f[i]);
}

int ans = f[b];
while (b < n) {
ans = ans * A + B;
_mod(ans);
b += M;
}
printf("%d\n", ans);

}

搜索:位模拟,连通分量,开点

C++ STL中的bitset头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
构造方法:
string s = "100101";
bitset<MAXN> bits(s)
MAXN位,最低位是s,高位不足用0补齐

bits.count()返回1的位数
bits.set(3, 0) => bits[3] = 0

bits.set(3) => bits[3] = 1
bits.reset(3) => bits[3] = 0

bits.test(2)
bits[2] == 1, return true
bits[2] == 0, return false

LA5218
LA5218

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
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
//
// main.cpp
// LA5218
//
// Created by zhangmin chen on 2019/7/11.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int maxn = 15;


#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

int n;
int G[maxn][maxn];
int vis[maxn];

void init() {
Set(G, 0);
Set(vis, 0);
}

int deg(const int u, const bitset<maxn>& opened) {
if(opened.test(u)) return 0;
int ans = 0;
_for(v, 0, n) if(G[u][v] && !opened.test(v)) ans++;
return ans;
}

bool canDfs(const int u, const int pa, const bitset<maxn>& opened) {
if(vis[u] == 1) return true;
if(vis[u] == -1) return false;

if(opened.test(u)) {
vis[u] = 1;
return true;
}

vis[u] = -1;
// dfs v

_for(v, 0, n) if(v != pa && G[u][v]) if(!canDfs(v, u, opened)) return false;

vis[u] = 1;
return true;
}

void initVis() {
Set(vis, 0);
}

int solve() {
int ans = n;
bitset<maxn> opened;

_for(x, 0, 1 << n) {
opened.reset();
bool ok = true;

// check line
_for(i, 0, n) if((1 << i) & x) opened.set(i);
_for(i, 0, n) if(deg(i, opened) > 2 && !opened.test(i)) {
ok = false;
break;
}

if(!ok) continue;

// check circle and component
initVis();
int ti = 0;
_for(u, 0, n) {
if(opened.test(u)) continue;
if(!vis[u]) ti++;
if(!canDfs(u, -1, opened)) {
ok = false;
break;
}
}

if(!ok) continue;

int kc = (int)opened.count();
//debug(ti);
if(ti <= kc + 1) ans = min(ans, kc);
}
return ans;

}

int main() {
freopen("input.txt", "r", stdin);
for(int kase = 1; scanf("%d", &n) == 1 && n; kase++) {
init();
int from, to;
while (true) {
scanf("%d%d", &from, &to);
if(from == -1 || to == -1) break;
from--; to--;
G[from][to] = G[to][from] = 1;
}
// input finished
// then solve

int ans = solve();
// cout << ans << endl;
printf("Set %d: Minimum links to open is %d\n", kase, ans);
}
}

Pipeline Scheduling

LA5678
LA5678

位模拟:右移动

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
//
// main.cpp
// LA5678
//
// Created by zhangmin chen on 2019/7/12.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int UNIT = 5;
const int MAXN = 20 + 5;
const int MAXTASK = 10;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

int units[UNIT];
vector<int> skip;
int N;

void init() {
Set(units, 0);
skip.clear();
}

bool overlap(const int* tb, int dt) {
_for(i, 0, UNIT) if(units[i] & (tb[i] >> dt)) return true;
return false;
}

void read() {
char line[MAXN];
_for(i, 0, UNIT) {
scanf("%s", line);
_for(j, 0, N) if(line[j] == 'X') units[i] |= (1 << j);
}
_rep(dt, 1, N) if(!overlap(units, dt)) skip.push_back(dt);
}

void dfs(int* tb, int clock, int d, int& ans) {
if(d == MAXTASK) {
ans = min(ans, clock);
return;
}

if( (clock + (MAXTASK - d) * skip[0]) > ans) return;

_for(i, 0, skip.size()) {
int dt = skip[i];
if(!overlap(tb, dt)) {
int nxt[UNIT];
Cpy(nxt, tb);
_for(j, 0, UNIT) nxt[j] = ((nxt[j] >> dt) | units[j]);

dfs(nxt, clock + dt, d + 1, ans);
}
}
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d", &N) && N) {
//
init();
read();
int ans = N * MAXTASK;
dfs(units, N, 1, ans);
printf("%d\n", ans);
}
}

位模拟:左移动

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
bitset<MAXN> units[UNIT], MASK;
vector<int> skip;
int N;

// units in overall scope means incoming task
// parameter *tb is old task

void init() {
_for(i, 0, UNIT) units[i].reset();
// MASK.reset();
skip.clear();
}

bool overlap(bitset<MAXN>* tb, int dt) {
_for(i, 0, UNIT) if( ((tb[i] << dt) & units[i]).any() ) return true;
return false;
}

void read() {
char line[MAXN];
_for(i, 0, UNIT) {
scanf("%s", line);
_for(j, 0, N) if(line[j] == 'X') units[i].set(j);
}
_rep(dt, 1, N) if(!overlap(units, dt)) skip.push_back(dt);
// MASK = (1 << N) - 1;
}

void dfs(bitset<MAXN>* tb, int clock, int d, int& ans) {
if(d == MAXTASK) {
ans = min(ans, clock);
return;
}

if( (clock + (MAXTASK - d) * skip[0]) > ans) return;

_for(i, 0, skip.size()) {
int dt = skip[i];
if(!overlap(tb, dt)) {
bitset<MAXN> nxt[UNIT];
_for(j, 0, UNIT) nxt[j] = tb[j];

_for(j, 0, UNIT) nxt[j] = ((nxt[j] << dt) | units[j]);

dfs(nxt, clock + dt, d + 1, ans);
}
}
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d", &N) && N) {
//
init();
read();
int ans = N * MAXTASK;
dfs(units, N, 1, ans);
printf("%d\n", ans);
}
}

Overlapping Squares

LA3790
LA3790

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
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
//
// main.cpp
// LA3790
//
// Created by zhangmin chen on 2019/7/12.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int R = 5;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

int _hash(int r, int c) {
return r * R + c;
}

void decode(const int x, int& r, int& c) {
c = x % R;
r = x / R;
}


class Grid {
public:
int bitX, bitY;
Grid(int _x = 0, int _y = 0) : bitX(_x), bitY(_y) {}

inline void clear() {
bitX = bitY = 0;
}

int getX(int r, int c) {
return bitX & (1 << _hash(r, c));
}
int getY(int r, int c) {
return bitY & (1 << _hash(r, c));
}

void setX(int r, int c) {
bitX |= (1 << _hash(r, c));
}
void resetX(int r, int c) {
bitX &= ~(1 << _hash(r, c));
}
void setY(int r, int c) {
bitY |= (1 << _hash(r, c));
}
void resetY(int r, int c) {
bitY &= ~(1 << _hash(r, c));
}

// usage: "_" setX(r, c) OR "|" setY(r, c)

void fillGrid(int r, int c) {
assert(0 <= r && r <= 2);
// assert("green");

setX(r, c); setY(r, c);

setX(r, c+1); setX(r+2, c); setX(r+2, c+1);
setY(r+1, c); setY(r, c+2); setY(r+1, c+2);

resetX(r+1, c); resetX(r+1, c+1);
resetY(r, c+1); resetY(r+1, c+1);
}

bool operator== (const Grid& rhs) const {
return bitX == rhs.bitX && bitY == rhs.bitY;
}
};

Grid target;

bool dfs(const Grid& grid, int d) {
if(grid == target) return true;
if(d >= 6) return false;

_rep(r, 0, 2) _rep(c, 0, 2) {
Grid nxt = grid;
nxt.fillGrid(r, c);
if(dfs(nxt, d+1)) return true;
}
return false;
}

void init() {
//
target.clear();
}

int main() {
freopen("input.txt", "r", stdin);

string line;
for(int kase = 1; ; kase++) {
init();
_for(i, 0, R) {
getline(cin, line);
if(line == "0") return 0;

_for(j, 0, 9) {
if(line[j] == ' ') continue;
if(line[j] == '_') {
// (i, j/2) => bitX
target.setX(i, j/2);
}
if(line[j] == '|') {
// (i-1, j/2) => bitY
target.setY(i-1, j/2);
}
}
}

// finish input
// then solve
Grid st;
bool ans = dfs(st, 0);

printf("Case %d: ", kase);
if(ans) printf("Yes\n");
else printf("No\n");

}
}

debug的技巧,assert的使用
1/ 在预计程序不会到达的地方设置一个assert(false)
2/ assert用于检查传递给私有方法的参数

1
2
3
4
void fillGrid(int r, int c) {
assert(0 <= r && r <= 2)
assert(0 <= c && c <= 2)
}

3/ 检查变量的属性,比如在dfs中给节点染色

1
2
3
4
5
6
void dfs(int u) {
if(color[u] == GREEN) return
assert(color[u] == GRAY);

then visit node u
}

用一个断言来确定节点的执行

复杂搜索

解答树填空法的综合应用

LA3784
LA3784

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
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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
//
// main.cpp
// LA3784
//
// Created by zhangmin chen on 2019/7/13.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;
//const int maxn = 10 + 5;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)


const string buf = "*0123456789";
const int BUFLEN = 11;
int len[3];
string data;

void init() {
//
data.clear();
Set(len, 0);
}

/*
void clearVis() {
Set(vis, 0);
}
*/

// only one solution
// check exp 0;

// st3[i] == bit + '0' || str3[i] == '*'
// ans is correct

int cal(const string& str, int from, int to) {
// [from, to]
int ans = 0, base = 1;

_rep(i, from, to) {
ans *= base;
ans += str[i] - '0';
base *= 10;
}

return ans;
}

// find one and only one solution
// return true

bool _equal(const string& str) {
// string lhs1 = lhs.substr(0, len1), lhs2 = lhs.substr(len1, len2);
// assert(lhs1.length() == len1);
// assert(lhs2.length() == len2);

//if(lhs1[0] == '0' || lhs2[0] == '0' || rhs[0] == '0') return false;

int a = cal(str, 0, len[0] - 1), b = cal(str, len[0], len[0] + len[1] - 1);
int c = a * b;

char ans[5];
/*
stringstream ss;
ss << c;
*/
sprintf(ans, "%d", c);
int ansL = (int)strlen(ans);

assert(ansL > 0);
//debug(ans);


if(ansL != len[2]) return false;
else {
// bool ok = 1;
_for(i, len[0] + len[1], str.length()) {
if(str[i] == '*') continue;
// debug(ans[i]);
if(ans[i - (len[0] + len[1])] != str[i]) return false;
}
return true;
}
}

void check(string& str, int i, int& cnt) {
if(cnt > 1) return;

if(i == len[0] + len[1]) {
if(_equal(str)) cnt++;

return;
}


if(str[i] != '*') check(str, i + 1, cnt);
else {
_for(k, 1, BUFLEN) {
if(k == 1 && (i == 0 || i == len[0])) continue;
str[i] = buf[k];
check(str, i + 1, cnt);
str[i] = '*';
}
}
}

// ans O(8100)


bool dfs(string& str, int i, int d, int maxd) {
if(d == maxd) {
int cnt = 0;
check(str, 0, cnt);
// debug(cnt);


if(cnt == 1) return true;
else return false;
}

if(i == str.length()) return false;
if(str.length() - i < maxd - d) return false;

// debug(len1);

char old = str[i];
_for(k, 0, BUFLEN) {
if(k == 1 && (i == 0 || i == len[0] || i == len[0] + len[1])) continue;
if(old == buf[k]) {
// debug(old);
if(dfs(str, i + 1, d, maxd)) return true;
}
else {
str[i] = buf[k];
if(dfs(str, i + 1, d + 1, maxd)) return true;
str[i] = old;
}
}

// if(dfs(nxt)) return true
return false;
}


string solve() {
int maxd = 0;
string clone = data;
for(maxd = 0; ; maxd++) {
if(dfs(clone, 0, 0, maxd)) break;
}
//debug(maxd);
return clone;
}



int main() {
freopen("input.txt", "r", stdin);
string line;
int kase = 1;
while(getline(cin, line)) {
init();

if(line[0] == '0') return 0;

// then line is the input data
// line -> Exp
stringstream ss(line);
string tmp;

int k = 0;
while (ss >> tmp) {
len[k++] = (int)tmp.length();
data += tmp;
}

// cout << data << endl;
string ans = solve();
// cout << ans << endl;

printf("Case %d: ", kase++);
cout << ans.substr(0, len[0]) << " " << ans.substr(len[0], len[1])
<< " " << ans.substr(len[0] + len[1]) << endl;

}
}