| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 136370 |
2019-07-25T07:55:52 Z |
조승현(#3264) |
Meandian (CEOI06_meandian) |
C++14 |
|
2 ms |
256 KB |
#include<cstdio>
#include<algorithm>
#include<vector>
char p[30][100];
int W, H, n, m, chk[15][50];
int D[15][50][1 << 13], w[15][50][4], Path[15][50][1 << 13][2];
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
void UDT(int *T, int *D, int x, int y, int mask, int pv, int i) {
if (D[mask | pv] > T[i] + (pv & 1) + !!(pv & 2)){
D[mask | pv] = T[i] + (pv & 1) + !!(pv & 2);
Path[x][y][mask | pv][0] = i;
Path[x][y][mask | pv][1] = pv;
}
}
void Do(int *T, int *D, int x, int y) {
int i, Full = (1 << (n + 1)) - 1;
for (i = 0; i < (1 << (n + 1)); i++) {
if (T[i] > 8e8)continue;
int c = 0;
if ((i & 1))c++;
if ((i >> n) & 1)c++;
int mask = ((i&(~1)) << 1)&Full;
if (chk[x][y]) {
if (c == 2)continue;
if (c == 1) {
UDT(T, D, x, y, mask, 0, i);
}
else {
if (w[x][y][0]) {
UDT(T, D, x, y, mask, 2, i);
}
if (w[x][y][1]) {
UDT(T, D, x, y, mask, 1, i);
}
}
continue;
}
if (c == 1) {
if (w[x][y][0]) {
UDT(T, D, x, y, mask, 2, i);
}
if (w[x][y][1]) {
UDT(T, D, x, y, mask, 1, i);
}
}
if (c == 2) {
UDT(T, D, x, y, mask, 0, i);
}
if (c == 0) {
if (D[mask] > T[i]) {
UDT(T, D, x, y, mask, 0, i);
}
if (w[x][y][0] && w[x][y][1]) {
UDT(T, D, x, y, mask, 3, i);
}
}
}
}
void Go(int x, int y, int pv) {
if (!y)return;
int nxt = Path[x][y][pv][0];
int t = Path[x][y][pv][1];
if (t & 1)p[x * 2 + 1][y * 2] = '.';
if (t & 2)p[x * 2][y * 2 + 1] = '.';
x--;
if (x == 0) {
x = n, y--;
}
Go(x, y, nxt);
}
int main() {
//freopen("input.txt", "r", stdin);
int i, j, k;
scanf("%d%d", &W, &H);
fgets(p[0], 90, stdin);
for (i = 1; i <= W; i++) {
fgets(p[i]+1, 90, stdin);
}
n = W / 2, m = H / 2;
int c = 0;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
if (i != n && p[i * 2 + 1][j * 2] != '-') {
w[i][j][1] = w[i + 1][j][3] = 1;
}
if (j != m && p[i * 2][j * 2 + 1] != '|') {
w[i][j][0] = w[i][j + 1][2] = 1;
}
if (p[i * 2][j * 2] == 'X')chk[i][j] = 1, c++;
}
}
for (i = 0; i <= n; i++)for (j = 0; j <= m; j++)for (k = 0; k < (1 << (n + 1)); k++)D[i][j][k] = 1e9;
D[n][0][0] = 0;
int pj = n, pi = 0;
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
Do(D[pj][pi], D[j][i], j, i);
pi = i;
pj = j;
}
}
printf("%d\n", D[n][m][0]*2);
Go(n, m, 0);
for (i = 1; i <= W; i++) {
for (j = 1; j <= H; j++) {
if (i%2==0&&j%2==0&&p[i][j] == ' ') {
for (k = 0; k < 4; k++) {
if (p[i + dx[k]][j + dy[k]] == '.')p[i][j] = '.';
}
}
printf("%c", p[i][j]);
}
puts("");
}
}
Compilation message
meandian.cpp: In function 'int main()':
meandian.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &W, &H);
~~~~~^~~~~~~~~~~~~~~~
meandian.cpp:75:7: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fgets(p[0], 90, stdin);
~~~~~^~~~~~~~~~~~~~~~~
meandian.cpp:77:8: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fgets(p[i]+1, 90, stdin);
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2 ms |
248 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
2 ms |
256 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
2 ms |
256 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
2 ms |
248 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
2 ms |
248 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
2 ms |
252 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
2 ms |
256 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
2 ms |
256 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
2 ms |
248 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
2 ms |
248 KB |
Time limit exceeded (wall clock) |
