#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(State *_prv1, int _type1, State *_prv2, int _type2) {
if (_prv1->cost < _prv2->cost) prv = _prv1, type = _type1;
else prv = _prv2, type = _type2;
cost = prv->cost;
if (type < 4) cost++;
else if (type < 10) cost += 2;
}
};
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;
for (int i = 0; i < n; i++)
for (int j = 0; j <= m; j++)
for (int mask = 0; mask < (1 << n + 1); mask++)
dp[i][j][mask] = new State();
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] = new State(dp[n - 1][j - 1][prv_base], 1);
if (d) dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base], 2);
} else dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base + 1], 3);
} else {
if (r && d) dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base], 7);
else if (r || d) {
if (r) dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base + 1], 8);
if (d) dp[i][j][mask] = new State(dp[n - 1][j - 1][prv_base + 1], 9);
} else dp[i][j][mask] = new State(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] = new State(dp[i - 1][j][prv_base], 1);
if (d) dp[i][j][mask] = new State(dp[i - 1][j][prv_base], 2);
} else dp[i][j][mask] = new State(
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] = new State(dp[i - 1][j][prv_base], 7);
else if (r || d) {
if (r) dp[i][j][mask] = new State(
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] = new State(
dp[i - 1][j][prv_base + (1 << i)], 5,
dp[i - 1][j][prv_base + (1 << i + 1)], 9);
} else dp[i][j][mask] = new State(
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:15: warning: 'State::type' will be initialized after [-Wreorder]
6 | int cost, type;
| ^~~~
connect.cpp:6:9: warning: 'int State::cost' [-Wreorder]
6 | int cost, type;
| ^~~~
connect.cpp:9:5: 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:35:47: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
35 | for (int mask = 0; mask < (1 << n + 1); mask++)
| ~~^~~
connect.cpp:40:47: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
40 | for (int mask = 0; mask < (1 << n + 1); mask++) {
| ~~^~~
connect.cpp:41:61: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
41 | int r = mask & (1 << i), d = mask & (1 << i + 1);
| ~~^~~
connect.cpp:63:53: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
63 | int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
| ~~^~~
connect.cpp:63:84: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
63 | int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
| ~~^~~
connect.cpp:63:74: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
63 | int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
| ~~~~~~~~~^~~~~~~~~~~~~~
connect.cpp:70:65: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
70 | dp[i - 1][j][prv_base + (1 << i + 1)], 3);
| ~~^~~
connect.cpp:76:69: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
76 | dp[i - 1][j][prv_base + (1 << i + 1)], 8);
| ~~^~~
connect.cpp:79:69: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
79 | dp[i - 1][j][prv_base + (1 << i + 1)], 9);
| ~~^~~
connect.cpp:81:76: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
81 | dp[i - 1][j][prv_base + (1 << i) + (1 << i + 1)], 6,
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1644 KB |
Output is correct |
| 4 |
Correct |
21 ms |
15468 KB |
Output is correct |
| 5 |
Runtime error |
92 ms |
65540 KB |
Execution killed with signal 9 |
| 6 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2412 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3692 KB |
Output is correct |
| 9 |
Correct |
10 ms |
8044 KB |
Output is correct |
| 10 |
Correct |
14 ms |
11372 KB |
Output is correct |
| 11 |
Correct |
17 ms |
13676 KB |
Output is correct |
| 12 |
Correct |
29 ms |
23276 KB |
Output is correct |
| 13 |
Correct |
41 ms |
32876 KB |
Output is correct |
| 14 |
Correct |
62 ms |
47852 KB |
Output is correct |
| 15 |
Runtime error |
83 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
77 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
80 ms |
65540 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
79 ms |
65540 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
80 ms |
65540 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
78 ms |
65540 KB |
Execution killed with signal 9 |
