oj.uz

Submission #136351

# Submission time Handle Problem Language Result Execution time Memory
136351 2019-07-25T07:33:14 Z 조승현(#3264) Connect (CEOI06_connect) C++14
100 / 100
 46 ms 43132 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

connect.cpp: In function 'int main()':
connect.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);
  ~~~~~^~~~~~~~~~~~~~~~
connect.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);
  ~~~~~^~~~~~~~~~~~~~~~~
connect.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);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 1144 KB Output is correct
4 Correct 3 ms 2040 KB Output is correct
5 Correct 14 ms 12536 KB Output is correct
6 Correct 3 ms 2168 KB Output is correct
7 Correct 3 ms 1656 KB Output is correct
8 Correct 4 ms 2552 KB Output is correct
9 Correct 5 ms 3960 KB Output is correct
10 Correct 6 ms 5496 KB Output is correct
11 Correct 5 ms 4088 KB Output is correct
12 Correct 9 ms 7544 KB Output is correct
13 Correct 9 ms 8184 KB Output is correct
14 Correct 10 ms 8696 KB Output is correct
15 Correct 11 ms 9464 KB Output is correct
16 Correct 14 ms 11384 KB Output is correct
17 Correct 17 ms 14588 KB Output is correct
18 Correct 30 ms 25052 KB Output is correct
19 Correct 46 ms 43132 KB Output is correct
20 Correct 38 ms 35704 KB Output is correct