Submission #136353

#	Time	Username	Problem	Language	Result	Execution time	Memory
136353		ainta	Connect (CEOI06_connect)	C++17	100 / 100	48 ms	43128 KiB

connect

#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 (stderr)

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 / 100