Submission #136497

#	Time	Username	Problem	Language	Result	Execution time	Memory
136497		sebinkim	Connect (CEOI06_connect)	C++14	100 / 100	31 ms	17020 KiB

connect

#include <bits/stdc++.h>

using namespace std;

int D[1010][9090];
char S[33][99];
int n, m;

int main()
{
	int i, j, x, y, t, k, v;
	
	scanf("%d%d\n", &n, &m);
	
	for(i=0; i<n; i++){
		fgets(S[i], 88, stdin);
	}
	
	n /= 2; m /= 2;
	
	for(i=0; i<=n*m; i++){
		for(j=0; j<(1<<n+1); j++){
			D[i][j] = 1e9;
		}
	}
	
	D[0][0] = 0;
	
	for(i=0; i<n*m; i++){
		x = i % n << 1 | 1; y = i / n << 1 | 1;
		for(j=0; j<(1<<n+1); j++){
			if(S[x][y] == 'X'){
				v = 1;
				if((j & 3) == 3) k = 0;
				else if(j & 3) k = 1;
				else k = 2;
			}
			else{
				v = 2;
				if((j & 3) == 3) k = 1;
				else if(j & 3) k = 2;
				else k = 5;
			}
			
			if(k & 1){
				t = j >> 1 & ~1;
				D[i + 1][t] = min(D[i + 1][t], D[i][j] + (k > 1? 0 : v));
			}
			if(k & 2){
				if(S[x + 1][y] != '-'){
					t = j >> 1 | 1;
					D[i + 1][t] = min(D[i + 1][t], D[i][j] + v);
				}
				if(S[x][y + 1] != '|'){
					t = j >> 1 & ~1 | 1 << n;
					D[i + 1][t] = min(D[i + 1][t], D[i][j] + v);
				}
			}
			if(k & 4){
				if(S[x + 1][y] != '-' && S[x][y + 1] != '|'){
					t = j >> 1 | 1 | 1 << n;
					D[i + 1][t] = min(D[i + 1][t], D[i][j] + v);
				}
			}
		}
	}
	
	for(i=n*m, j=0; i; i--){
		x = (i - 1) % n << 1 | 1; y = (i - 1) / n << 1 | 1;
		t = j & ~1 & ~(1 << n);
		
		if(S[x][y] == 'X'){
			v = 1;
			if((j & 1) || (j & 1 << n)) k = 1;
			else k = 2;
		}
		else{
			v = 2;
			if((j & 1) && (j & 1 << n)) k = 1;
			else if((j & 1) || (j & 1 << n)) k = 2;
			else k = 4;
		}
		
		if(k & 1){
			if(S[x][y] == ' ') S[x][y] = '.';
			j = t << 1;
		}
		if(k & 2){
			if(S[x][y] == ' ') S[x][y] = '.';
			if(D[i - 1][t << 1 | 2] + v == D[i][j]){
				S[x][y - 1] = '.'; j = t << 1 | 2;
			}
			else if(D[i - 1][t << 1 | 1] + v == D[i][j]){
				S[x - 1][y] = '.'; j = t << 1 | 1;
			}
		}
		if(k & 4){
			if(D[i - 1][t << 1] == D[i][j]) j = t << 1;
			else if(D[i - 1][t << 1 | 3] + v == D[i][j]){
				S[x][y] = S[x - 1][y] = S[x][y - 1] = '.';
				j = t << 1 | 3;
			}
		}
	}
	
	printf("%d\n", D[n * m][0]);
	
	for(i=0; i<=n+n; i++){
		printf("%s", S[i]);
	}
	
	return 0;
}

Compilation message (stderr)

connect.cpp: In function 'int main()':
connect.cpp:22:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   for(j=0; j<(1<<n+1); j++){
                  ~^~
connect.cpp:31:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   for(j=0; j<(1<<n+1); j++){
                  ~^~
connect.cpp:55:17: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
      t = j >> 1 & ~1 | 1 << n;
          ~~~~~~~^~~~
connect.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d\n", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~
connect.cpp:16:8: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fgets(S[i], 88, stdin);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100