Submission #384914

#	Time	Username	Problem	Language	Result	Execution time	Memory
384914		pure_mem	Connect (CEOI06_connect)	C++14	64 / 100	39 ms	28652 KiB

connect

#include <bits/stdc++.h> 
 
#define X first
#define Y second
#define MP make_pair
#define ll long long
 
using namespace std;
 
const int N = 80, INF = 1e9;
const ll mod = 1e9 + 7;
 
int r, c, n, m, dp[12][40][(1 << 12)][2], pr[12][40][(1 << 12)][2], cntX;
string s[N];

void inputs(){
	scanf("%d %d\n", &r, &c);
	for(int i = 0;i < r;i++)
		getline(cin, s[i]), scanf("\n");
	for(int i = 0;i < r;i++)
		for(int j = 0;j < c;j++)
			cntX += (s[i][j] == 'X');
	n = r / 2, m = c / 2;
}

bool good(int x, int y, int tp){
	bool res = 1;
	if(tp <= 4 && s[x][y] != 'X')
		res = 0;
	if(tp == 1 || tp == 9 || tp == 10 || tp == 11){
		if(s[x][y - 1] == '|')
			res = 0;
	}
	if(tp == 2 || tp == 7 || tp == 8 || tp == 11){
		if(s[x - 1][y] == '-')
			res = 0;	
	}
	if(tp == 3 || tp == 6 || tp == 7 || tp == 10){
		if(s[x + 1][y] == '-')
			res = 0;	
	}
	if(tp == 4 || tp == 6 || tp == 8 || tp == 9){
		if(s[x][y + 1] == '|')
			res = 0;
	}
	return res;
}

int main () {
	inputs();
	for(int j = 0;j < m;j++)
		for(int i = 0;i < n;i++)
			for(int mask = 0;mask < (1 << n);mask++)
				dp[i][j][mask][0] = dp[i][j][mask][1] = INF;
	for(int i = 0, j = 0;i < n;i++){
		for(int mask = 0;mask < (1 << n);mask++){
			if(s[i * 2 + 1][j * 2 + 1] == 'X'){
				if(!((mask >> i) & 1)){
					int newmask = mask ^ (1 << i), val = (i ? dp[i - 1][j][mask][1]: INF);
					if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 2)){
						dp[i][j][mask][0] = val;
						pr[i][j][mask][0] = 2;
					}
					val = (i ? dp[i - 1][j][mask][0]: INF) + 1;
					if(val > INF && mask == 0)
						val = 1;	
					if(dp[i][j][mask][1] > val && good(i * 2 + 1, j * 2 + 1, 3)){
						dp[i][j][mask][1] = val;
						pr[i][j][mask][1] = 3;
					}
					if(dp[i][j][newmask][0] > val && good(i * 2 + 1, j * 2 + 1, 4)){
						dp[i][j][newmask][0] = val;
						pr[i][j][newmask][0] = 4;
					}	
				}
			}
			else{
				if((mask >> i) & 1)
					continue;
				int val = (i ? dp[i - 1][j][mask][0]: INF);
				if(mask == 0 && i == 0)
					val = 0;
				if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 5)){
					dp[i][j][mask][0] = val;
					pr[i][j][mask][0] = 5;
				}
				int newmask = mask ^ (1 << i);
				if(dp[i][j][newmask][1] > val + 3 && good(i * 2 + 1, j * 2 + 1, 6)){
					dp[i][j][newmask][1] = val + 3;
					pr[i][j][newmask][1] = 6;
				}
				val = (i ? dp[i - 1][j][mask][1]: INF);
				if(dp[i][j][mask][1] > val + 2 && good(i * 2 + 1, j * 2 + 1, 7)){
					dp[i][j][mask][1] = val + 2;
					pr[i][j][mask][1] = 7;
				}
				if(dp[i][j][newmask][0] > val + 2 && good(i * 2 + 1, j * 2 + 1, 8)){
					dp[i][j][newmask][0] = val + 2;
					pr[i][j][newmask][0] = 8;
				}
			}
		}	
	}
	for(int j = 1;j < m;j++){
		for(int i = 0;i < n;i++){
			for(int mask = 0;mask < (1 << n);mask++){		
				if(s[i * 2 + 1][j * 2 + 1] == 'X'){
					if(((mask >> i) & 1) && j){
						int newmask = mask ^ (1 << i), val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]);
						if(dp[i][j][newmask][0] > val && good(i * 2 + 1, j * 2 + 1, 1)){
							dp[i][j][newmask][0] = val;	
							pr[i][j][newmask][0] = 1;
						}
					}
					if(!((mask >> i) & 1)){
						int newmask = mask ^ (1 << i), val = (i ? dp[i - 1][j][mask][1]: INF);
						if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 2)){
							dp[i][j][mask][0] = val;
							pr[i][j][mask][0] = 2;
						}
						val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]) + 1;
						if(dp[i][j][mask][1] > val && good(i * 2 + 1, j * 2 + 1, 3)){
							dp[i][j][mask][1] = val;
							pr[i][j][mask][1] = 3;
						}
						if(dp[i][j][newmask][0] > val && good(i * 2 + 1, j * 2 + 1, 4)){
							dp[i][j][newmask][0] = val;
							pr[i][j][newmask][0] = 4;
						}
					}
				}
				else{
					if((mask >> i) & 1){
						int val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]);
						if(dp[i][j][mask][0] > val + 2 && good(i * 2 + 1, j * 2 + 1, 9)){
							dp[i][j][mask][0] = val + 2;
							pr[i][j][mask][0] = 9;
						}
						int newmask = mask ^ (1 << i);
						if(dp[i][j][newmask][1] > val + 2 && good(i * 2 + 1, j * 2 + 1, 10)){
							dp[i][j][newmask][1] = val + 2;
							pr[i][j][newmask][1] = 10;
						}
						val = (i ? dp[i - 1][j][mask][1]: INF);
						if(dp[i][j][newmask][0] > val + 1 && good(i * 2 + 1, j * 2 + 1, 11)){
							dp[i][j][newmask][0] = val + 1;
							pr[i][j][newmask][0] = 11;
						}
					}
					else{
						int val = (i ? dp[i - 1][j][mask][0]: dp[n - 1][j - 1][mask][0]);
						if(dp[i][j][mask][0] > val && good(i * 2 + 1, j * 2 + 1, 5)){
							dp[i][j][mask][0] = val;
							pr[i][j][mask][0] = 5;
						}
						int newmask = mask ^ (1 << i);
						if(dp[i][j][newmask][1] > val + 3 && good(i * 2 + 1, j * 2 + 1, 6)){
							dp[i][j][newmask][1] = val + 3;
							pr[i][j][newmask][1] = 6;
						}
						val = (i ? dp[i - 1][j][mask][1]: INF);
						if(dp[i][j][mask][1] > val + 2 && good(i * 2 + 1, j * 2 + 1, 7)){
							dp[i][j][mask][1] = val + 2;
							pr[i][j][mask][1] = 7;
						}
						if(dp[i][j][newmask][0] > val + 2 && good(i * 2 + 1, j * 2 + 1, 8)){
							dp[i][j][newmask][0] = val + 2;
							pr[i][j][newmask][0] = 8;
						}
					}	
				}	
			}
		}	
	}
	printf("%d", dp[n - 1][m - 1][0][0] + cntX / 2);
}               

Compilation message (stderr)

connect.cpp: In function 'void inputs()':
connect.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%d %d\n", &r, &c);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
connect.cpp:19:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |   getline(cin, s[i]), scanf("\n");
      |                       ~~~~~^~~~~~

• Subtask 1: 64 / 100