Submission #136468

#	Time	Username	Problem	Language	Result	Execution time	Memory
136468		youngyojun	Connect (CEOI06_connect)	C++11	16 / 100	22 ms	15864 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];

bool B[12][39][4], isX[12][39];
char A[25][80];

int H, W, Ans;

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) {
					upmin(dp[x][1][key>>1], t+1);
				} else {
					if(B[0][x][1]) upmin(dp[x][1][key>>1 | 1<<(H-1)], t+2);
					if(B[0][x][2]) upmin(dp[x][1][key>>1 | 1<<H], t+2);
				}
			} else {
				if(key & 1) {
					if(B[0][x][1]) upmin(dp[x][1][key>>1 | 1<<(H-1)], t+2);
					if(B[0][x][2]) upmin(dp[x][1][key>>1 | 1<<H], t+2);
				} else {
					if(B[0][x][1] && B[0][x][2])
						upmin(dp[x][1][key>>1 | 1<<(H-1) | 1<<H], t+3);
					upmin(dp[x][1][key>>1], t);
				}
			}
		}
		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) {
						upmin(dp[x][y+1][key>>1], t+1);
					} else if(key & (1<<H)) {
						upmin(dp[x][y+1][(key^(1<<H))>>1], t+1);
					} else {
						if(B[y][x][1]) upmin(dp[x][y+1][key>>1 | 1<<(H-1)], t+2);
						if(B[y][x][2]) upmin(dp[x][y+1][key>>1 | 1<<H], t+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))) {
						upmin(dp[x][y+1][(key^(1<<H))>>1], t+1);
					} else if(key & 1) {
						if(B[y][x][1]) upmin(dp[x][y+1][key>>1 | 1<<(H-1)], t+2);
						if(B[y][x][2]) upmin(dp[x][y+1][key>>1 | 1<<H], t+2);
					} else if(key & (1<<H)) {
						if(B[y][x][1]) upmin(dp[x][y+1][(key^(1<<H))>>1 | 1<<(H-1)], t+2);
						if(B[y][x][2]) upmin(dp[x][y+1][(key^(1<<H))>>1 | 1<<H], t+2);
					} else {
						if(B[y][x][1] && B[y][x][2])
							upmin(dp[x][y+1][key>>1 | 1<<(H-1) | 1<<H], t+3);
						upmin(dp[x][y+1][key>>1], t);
					}
				}
			}
		}
		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) {
					upmin(dp[x+1][0][key>>1], t+1);
				} else if(key & (1<<H)) {
					upmin(dp[x+1][0][(key^(1<<H))>>1], t+1);
				} else {
					if(B[H-1][x][1]) upmin(dp[x+1][0][key>>1 | 1<<(H-1)], t+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))) {
					upmin(dp[x+1][0][(key^(1<<H))>>1], t+1);
				} else if(key & 1) {
					if(B[H-1][x][1]) upmin(dp[x+1][0][key>>1 | 1<<(H-1)], t+2);
				} else if(key & (1<<H)) { 
					if(B[H-1][x][1]) upmin(dp[x+1][0][(key^(1<<H))>>1 | 1<<(H-1)], t+2);
				} else {
					upmin(dp[x+1][0][key>>1], t);
				}
			}
		}
	}

	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;
	cout << Ans << endl;
	return 0;
}

Compilation message (stderr)

connect.cpp: In function 'int main()':
connect.cpp:23: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:24: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: 16 / 100