#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for (auto i = (l) - ((l) > (r)); i != (r) - ((l) > (r)); i += 1 - 2 * ((l) > (r)))
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define pb push_back
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ld = long double;
using lli = long long;
using ii = pair<int, int>;
const int N = 12, M = 40;
int dp[M][N][1 << N];
const int N_BITSET = 2;
template <class T>
bool umin(T& a, T b) {
return (a = min(a, b)) == b;
}
int main() {
cin.tie(0)->sync_with_stdio(0), cout.tie(0);
int n, m;
cin >> n >> m;
cin.ignore();
cin.ignore();
vector<string> board(n);
debug(n, m);
fore (i, 0, n) {
getline(cin, board[i]);
assert(sz(board[i]) == m);
debug(board[i]);
}
#define coord(x) (x * 2 + 1)
auto isAFigure = [&] (int r, int c) -> bool {
if (r < 0 || c < 0) {
debug("isAFigure: Coordinates out of range");
return false;
}
debug(r, c);
r = coord(r), c = coord(c);
debug(r, c, board[r][c]);
return board[r][c] == 'X';
};
auto blocked = [&] (int r1, int c1, int r2, int c2) -> bool {
debug(r1, c1, r2, c2);
if (r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0) {
debug("blocked: Coordinates out of range");
return false;
}
r1 = coord(r1), c1 = coord(c1);
r2 = coord(r2), c2 = coord(c2);
bool thereIsAWall = false;
if (r1 == r2) { // hor
debug("horizontal");
if (c1 > c2) {
swap(c1, c2);
}
assert(c1 + 2 == c2);
thereIsAWall = board[r1][c1 + 1] == '|';
} else { // ver
debug("vertical");
assert(c1 == c2);
if (r1 > r2) {
swap(r1, r2);
}
assert(r1 + 2 == r2);
thereIsAWall = board[r1 + 1][c1] == '-';
}
debug(r1, c1, r2, c2, thereIsAWall);
return thereIsAWall;
};
memset(dp, 63, sizeof(dp));
dp[0][0][0] = 0;
n /= 2, m /= 2;
debug(n, m);
fore (r, 0, n) {
fore (c, 0, m + 1) {
// curr = r;
fore (mask, 0, 1 << m) {
// verity
debug("verify");
bool canContinue = true;
int updatedMask = 0;
if (r > 0) {
fore (ith, 0, m) {
bool bit = updatedMask & (1 << ith);
if (bit) { // bit is set
if (isAFigure(r - 1, ith)) {
// do nothing
} else {
updatedMask |= 1 << ith;
if (blocked(r - 1, c, r, c)) {
canContinue = false;
break;
}
}
} else { // bit isn't set
if (isAFigure(r - 1, ith)) {
if (isAFigure(r, ith)) { // two consecutive X's
if (blocked(ith, r - 1, ith, r)) {
canContinue = false;
break;
} else { // connect them
updatedMask |= (1 << ith);
}
}
updatedMask |= 1 << ith;
} else {
// do nothing
}
}
}
}
debug("");
bitset<N_BITSET> updatedMaskBitset(updatedMask);
bitset<N_BITSET> maskBitset(mask);
auto& me = dp[r][c][mask];
debug(r, c, maskBitset, me);
debug(updatedMaskBitset, canContinue);
if (!canContinue) {
continue;
}
if (c == m) {
debug("next row", r + 1, 0, mask, me);
umin(dp[r + 1][0][mask], me);
debug(dp[r + 1][0][mask]);
debug("");
continue;
}
if (~updatedMask & (1 << c)) { // do nothing
debug("// do nothing");
umin(dp[r][c + 1][updatedMask], me);
}
debug("");
debug("start");
debug("create a new pair (a, b)");
if (~updatedMask & (1 << c)) { // create a new pair (a, b)
// place a in c
// try to place b after c
int a = c;
for (int b = c + 1; b < m; b++) {
if (updatedMask & (1 << b) || blocked(r, b - 1, r, b)) { // there is an end here or is blocked
break;
}
int newMask = updatedMask | (1 << a) | (1 << b);
int newC = b + 1;
int len = abs(a - b) + 1; // +1 ??
umin(dp[r][newC][newMask], me + len);
if (isAFigure(r, b)) {
break;
}
}
}
debug("");
{ // continue an end
debug("continue an end");
int indexNextEnd = -1;
fore (ith, c, m) {
if (updatedMask & (1 << ith)) {
indexNextEnd = ith;
break;
}
}
debug(indexNextEnd);
if (indexNextEnd != -1) {
// left
debug("left");
for (int ith = indexNextEnd; ith >= c; ith--) {
if (ith != indexNextEnd && blocked(r, ith, r, ith + 1)) {
break;
}
// move end from indexNextEnd to ith if possible
int newMask = updatedMask;
assert(updatedMask & (1 << indexNextEnd));
newMask ^= 1 << indexNextEnd; // off
newMask |= 1 << ith; // on
int newC = max(ith, indexNextEnd) + 1;
int len = abs(indexNextEnd - ith) + 1;
umin(dp[r][newC][newMask], me + len);
if (isAFigure(r, ith)) {
break;
}
}
// right
debug("right");
for (int ith = indexNextEnd + 1; ith < m; ith++) {
if (blocked(r, ith - 1, r, ith)) { // is blocked
break;
}
if (updatedMask & (1 << ith)) {
break;
}
// move end from indexNextEnd to ith if possible
int newMask = updatedMask;
assert(updatedMask & (1 << indexNextEnd));
newMask ^= 1 << indexNextEnd; // off
newMask |= 1 << ith; // on
int newC = max(ith, indexNextEnd) + 1;
int len = abs(indexNextEnd - ith) + 1;
umin(dp[r][newC][newMask], me + len);
if (isAFigure(r, ith)) {
break;
}
}
}
}
debug("");
{ // connect two next ends if possible
debug(" connect two next ends if possible");
int a = -1, b = -1;
fore (ith, c, m) {
if (a != -1) {
if (isAFigure(r, ith)) {
break;
}
if (blocked(r, ith - 1, r, ith)) {
break;
}
if (updatedMask & (1 << ith)) { // second end
b = ith;
int newC = ith + 1;
int newUpdatedMask = updatedMask ^ (1 << a) ^ (1 << b);
bitset<N_BITSET> newUpdatedMaskBitset(newUpdatedMask);
int len = abs(a - b) + 1;
debug(a, b, newC, newUpdatedMaskBitset, me, len);
umin(dp[r][newC][newUpdatedMask], me + len);
break;
}
} else { // looking for first
if (updatedMask & (1 << ith)) {
a = ith;
if (isAFigure(r, ith)) {
break;
}
}
}
}
}
// anything else?
debug("---------------------------------------------");
}
debug("");
}
debug("");
}
debug("");
cout << dp[n][0][0] << '\n';
return 0;
}
/* Please, check the following:
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* write down your ideas
* DON'T get stuck on ONE APPROACH!
* ASK for HELP from your TEAMMATES
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 8 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 9 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 13 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 14 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 15 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 16 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 17 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 18 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 19 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 20 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
