#include <bits/stdc++.h>
using namespace std;
struct State {
State *prv;
int cost, type;
State(int _cost = 10000) : prv(nullptr), cost(_cost), type(-1) {}
State(State *_prv, int _type) : prv(_prv), type(_type), cost(_prv->cost) {
if (type < 4) cost++;
else if (type < 10) cost += 2;
}
};
State *construct(State *A, int typeA, State *B = nullptr, int typeB = -1) {
if (!A && !B) return nullptr;
if (!A) return new State(B, typeB);
if (!B) return new State(A, typeA);
if (A->cost < B->cost) return new State(A, typeA);
return new State(B, typeB);
}
string grid[25];
State *dp[12][40][1 << 13];
int main() {
cin.tie(0)->sync_with_stdio(0);
int r, c;
cin >> r >> c;
getline(cin, grid[0]); // Buffer stuff >:(
for (int i = 0; i < r; i++) getline(cin, grid[i]);
int n = r >> 1, m = c >> 1;
dp[n - 1][0][0] = new State(0);
for (int j = 1; j <= m; j++) {
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < (1 << n + 1); mask++) {
int r = mask & (1 << i), d = mask & (1 << i + 1);
// You can't connect over a blocked corridor
if (r && grid[2 * i + 1][2 * j] == '|') continue;
if (d && grid[2 * i + 2][2 * j - 1] == '-') continue;
// An 'X' can't have more than 1 paths going out from it
if (r && d && grid[2 * i + 1][2 * j - 1] == 'X') continue;
// Casework for the DP
if (!i) {
int prv_base = (mask >> 2) << 1;
if (grid[2 * i + 1][2 * j - 1] == 'X') {
if (r || d) {
if (r) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 1);
if (d) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 2);
} else dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base + 1], 3);
} else {
if (r && d) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 7);
else if (r || d) {
if (r) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base + 1], 8);
if (d) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base + 1], 9);
} else dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 10);
}
} else {
int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
if (grid[2 * i + 1][2 * j - 1] == 'X') {
if (r || d) {
if (r) dp[i][j][mask] = construct(dp[i - 1][j][prv_base], 1);
if (d) dp[i][j][mask] = construct(dp[i - 1][j][prv_base], 2);
} else dp[i][j][mask] = construct(
dp[i - 1][j][prv_base + (1 << i)], 0,
dp[i - 1][j][prv_base + (1 << i + 1)], 3);
} else {
if (r && d) dp[i][j][mask] = construct(dp[i - 1][j][prv_base], 7);
else if (r || d) {
if (r) dp[i][j][mask] = construct(
dp[i - 1][j][prv_base + (1 << i)], 4,
dp[i - 1][j][prv_base + (1 << i + 1)], 8);
if (d) dp[i][j][mask] = construct(
dp[i - 1][j][prv_base + (1 << i)], 5,
dp[i - 1][j][prv_base + (1 << i + 1)], 9);
} else dp[i][j][mask] = construct(
dp[i - 1][j][prv_base + (1 << i) + (1 << i + 1)], 6,
dp[i - 1][j][prv_base], 10);
}
}
}
}
}
cout << dp[n - 1][m][0]->cost << '\n';
State *curr = dp[n - 1][m][0];
for (int j = m - 1; ~j; j--) for (int i = n - 1; ~i; i--) {
if (curr->type == 0) grid[2 * i][2 * j + 1] = '.';
else if (curr->type == 1) grid[2 * i + 1][2 * j + 2] = '.';
else if (curr->type == 2) grid[2 * i + 2][2 * j + 1] = '.';
else if (curr->type == 3) grid[2 * i + 1][2 * j] = '.';
else if (curr->type == 4) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j + 2] = '.';
else if (curr->type == 5) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 2][2 * j + 1] = '.';
else if (curr->type == 6) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.';
else if (curr->type == 7) grid[2 * i + 1][2 * j + 2] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 2][2 * j + 1] = '.';
else if (curr->type == 8) grid[2 * i + 1][2 * j + 2] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.';
else if (curr->type == 9) grid[2 * i + 2][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.';
curr = curr->prv;
}
for (int i = 0; i < r; i++) cout << grid[i] << '\n';
return 0;
}
Compilation message
connect.cpp: In constructor 'State::State(State*, int)':
connect.cpp:6:12: warning: 'State::type' will be initialized after [-Wreorder]
6 | int cost, type;
| ^~~~
connect.cpp:6:6: warning: 'int State::cost' [-Wreorder]
6 | int cost, type;
| ^~~~
connect.cpp:9:2: warning: when initialized here [-Wreorder]
9 | State(State *_prv, int _type) : prv(_prv), type(_type), cost(_prv->cost) {
| ^~~~~
connect.cpp: In function 'int main()':
connect.cpp:37:38: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
37 | for (int mask = 0; mask < (1 << n + 1); mask++) {
| ~~^~~
connect.cpp:38:49: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
38 | int r = mask & (1 << i), d = mask & (1 << i + 1);
| ~~^~~
connect.cpp:60:38: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
60 | int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
| ~~^~~
connect.cpp:60:69: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
60 | int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
| ~~^~~
connect.cpp:60:59: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
60 | int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
| ~~~~~~~~~^~~~~~~~~~~~~~
connect.cpp:67:41: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
67 | dp[i - 1][j][prv_base + (1 << i + 1)], 3);
| ~~^~~
connect.cpp:73:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
73 | dp[i - 1][j][prv_base + (1 << i + 1)], 8);
| ~~^~~
connect.cpp:76:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
76 | dp[i - 1][j][prv_base + (1 << i + 1)], 9);
| ~~^~~
connect.cpp:78:52: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
78 | dp[i - 1][j][prv_base + (1 << i) + (1 << i + 1)], 6,
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
16 ms |
12140 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2284 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3564 KB |
Output is correct |
| 11 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5868 KB |
Output is correct |
| 13 |
Correct |
8 ms |
6636 KB |
Output is correct |
| 14 |
Correct |
8 ms |
7788 KB |
Output is correct |
| 15 |
Correct |
10 ms |
9964 KB |
Output is correct |
| 16 |
Correct |
14 ms |
13164 KB |
Output is correct |
| 17 |
Correct |
20 ms |
15212 KB |
Output is correct |
| 18 |
Correct |
31 ms |
28396 KB |
Output is correct |
| 19 |
Correct |
70 ms |
51044 KB |
Output is correct |
| 20 |
Correct |
41 ms |
33192 KB |
Output is correct |
