#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
const bool debug = 0;
int dp[40][12][1<<13];
int sex[40][12][1<<13];
bool B[12][39][4], isX[12][39];
char A[25][80];
int H, W, Ans;
void upd(int x, int y, int key, int t, int pkey, int dr) {
if(dp[x][y][key] <= t) return;
dp[x][y][key] = t;
sex[x][y][key] = pkey<<4 | dr;
}
int main() {
scanf("%d%d ", &H, &W);
for(int i = 0; i < H; i++) fgets(A[i], INF, stdin);
H >>= 1; W >>= 1;
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
int y = i<<1|1, x = j<<1|1;
if(' ' == A[y-1][x]) B[i][j][0] = true;
if(' ' == A[y][x+1]) B[i][j][1] = true;
if(' ' == A[y+1][x]) B[i][j][2] = true;
if(' ' == A[y][x-1]) B[i][j][3] = true;
isX[i][j] = 'X' == A[y][x];
}
fill(dp[0][0], dp[39][11]+(1<<13), INF);
dp[0][0][0] = 0;
for(int x = 0; x < W; x++) {
for(int key = 1<<H; key--;) {
int t = dp[x][0][key];
if(INF <= t) continue;
if(isX[0][x]) {
if(key & 1) upd(x, 1, key>>1, t+1, key, 1);
else {
if(B[0][x][1]) upd(x, 1, key>>1 | 1<<(H-1), t+2, key, 1<<1);
if(B[0][x][2]) upd(x, 1, key>>1 | 1<<H, t+2, key, 1<<2);
}
} else {
if(key & 1) {
if(B[0][x][1]) upd(x, 1, key>>1 | 1<<(H-1), t+2, key, 1<<1);
if(B[0][x][2]) upd(x, 1, key>>1 | 1<<H, t+2, key, 1<<2);
} else {
if(B[0][x][1] && B[0][x][2])
upd(x, 1, key>>1 | 1<<(H-1) | 1<<H, t+3, key, 1<<1|1<<2);
upd(x, 1, key>>1, t, key, 0);
}
}
}
for(int y = 1; y < H-1; y++) {
if(isX[y][x]) {
for(int key = 1<<(H+1); key--;) {
if((key & 1) && (key & (1<<H))) continue;
int t = dp[x][y][key];
if(INF <= t) continue;
if(key & 1) upd(x, y+1, key>>1, t+1, key, 0);
else if(key & (1<<H)) upd(x, y+1, (key^(1<<H))>>1, t+1, key, 1);
else {
if(B[y][x][1]) upd(x, y+1, key>>1 | 1<<(H-1), t+2, key, 1<<1);
if(B[y][x][2]) upd(x, y+1, key>>1 | 1<<H, t+2, key, 1<<2);
}
}
} else {
for(int key = 1<<(H+1); key--;) {
int t = dp[x][y][key];
if(INF <= t) continue;
if((key & 1) && (key & (1<<H))) upd(x, y+1, (key^(1<<H))>>1, t+1, key, 1);
else if(key & 1) {
if(B[y][x][1]) upd(x, y+1, key>>1 | 1<<(H-1), t+2, key, 1<<1);
if(B[y][x][2]) upd(x, y+1, key>>1 | 1<<H, t+2, key, 1<<2);
} else if(key & (1<<H)) {
if(B[y][x][1]) upd(x, y+1, (key^(1<<H))>>1 | 1<<(H-1), t+2, key, 1<<1);
if(B[y][x][2]) upd(x, y+1, (key^(1<<H))>>1 | 1<<H, t+2, key, 1<<2);
} else {
if(B[y][x][1] && B[y][x][2])
upd(x, y+1, key>>1 | 1<<(H-1) | 1<<H, t+3, key, 1<<1|1<<2);
upd(x, y+1, key>>1, t, key, 0);
}
}
}
}
if(isX[H-1][x]) {
for(int key = 1<<(H+1); key--;) {
if((key & 1) && (key & (1<<H))) continue;
int t = dp[x][H-1][key];
if(INF <= t) continue;
if(key & 1) upd(x+1, 0, key>>1, t+1, key, 1);
else if(key & (1<<H)) upd(x+1, 0, (key^(1<<H))>>1, t+1, key, 1);
else if(B[H-1][x][1]) upd(x+1, 0, key>>1 | 1<<(H-1), t+2, key, 1<<1);
}
} else {
for(int key = 1<<(H+1); key--;) {
int t = dp[x][H-1][key];
if(INF <= t) continue;
if((key & 1) && (key & (1<<H))) upd(x+1, 0, (key^(1<<H))>>1, t+1, key, 1);
else if(key & 1) {
if(B[H-1][x][1]) upd(x+1, 0, key>>1 | 1<<(H-1), t+2, key, 1<<1);
} else if(key & (1<<H)) {
if(B[H-1][x][1]) upd(x+1, 0, (key^(1<<H))>>1 | 1<<(H-1), t+2, key, 1<<1);
} else upd(x+1, 0, key>>1, t, key, 0);
}
}
}
Ans = dp[W][0][0];
int xcnt = 0;
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++)
if(isX[i][j]) xcnt++;
Ans -= xcnt >> 1;
printf("%d\n", Ans);
for(int y = 0, x = W, key = 0, fuck, dr, py, px;;) {
if(!y && !x) break;
fuck = sex[x][y][key];
dr = fuck & 15;
if(!y) {
y = H-1;
x--;
} else y--;
py = y<<1|1; px = x<<1|1;
if(dr & 1) A[py][px] = '.';
if(dr & 2) A[py][px] = A[py][px+1] = '.';
if(dr & 4) A[py][px] = A[py+1][px] = '.';
key = fuck >> 4;
}
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++)
if(isX[i][j]) A[i<<1|1][j<<1|1] = 'X';
for(int i = 0; i < (H<<1|1); i++) {
for(int j = 0; j < (W<<1|1); j++)
putchar(A[i][j]);
puts("");
}
return 0;
}
Compilation message
connect.cpp: In function 'int main()':
connect.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d ", &H, &W);
~~~~~^~~~~~~~~~~~~~~~~
connect.cpp:31:34: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < H; i++) fgets(A[i], INF, stdin);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
15836 KB |
Output is correct |
| 2 |
Correct |
15 ms |
15864 KB |
Output is correct |
| 3 |
Correct |
16 ms |
16120 KB |
Output is correct |
| 4 |
Correct |
16 ms |
15864 KB |
Output is correct |
| 5 |
Correct |
20 ms |
19192 KB |
Output is correct |
| 6 |
Correct |
16 ms |
16504 KB |
Output is correct |
| 7 |
Correct |
16 ms |
16604 KB |
Output is correct |
| 8 |
Correct |
16 ms |
17016 KB |
Output is correct |
| 9 |
Correct |
17 ms |
17400 KB |
Output is correct |
| 10 |
Correct |
18 ms |
18168 KB |
Output is correct |
| 11 |
Correct |
17 ms |
17144 KB |
Output is correct |
| 12 |
Correct |
18 ms |
18424 KB |
Output is correct |
| 13 |
Correct |
18 ms |
18168 KB |
Output is correct |
| 14 |
Correct |
18 ms |
18168 KB |
Output is correct |
| 15 |
Correct |
18 ms |
17784 KB |
Output is correct |
| 16 |
Correct |
19 ms |
18808 KB |
Output is correct |
| 17 |
Correct |
20 ms |
19192 KB |
Output is correct |
| 18 |
Correct |
25 ms |
23288 KB |
Output is correct |
| 19 |
Correct |
32 ms |
26872 KB |
Output is correct |
| 20 |
Correct |
29 ms |
25720 KB |
Output is correct |
