Submission #136479

#	Time	Username	Problem	Language	Result	Execution time	Memory
136479		youngyojun	Connect (CEOI06_connect)	C++11	100 / 100	32 ms	26872 KiB

connect

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

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);
                             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100