답안 #363670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363670 2021-02-06T19:10:26 Z dolphingarlic Connect (CEOI06_connect) C++14
100 / 100
70 ms 51044 KB
#include <bits/stdc++.h>
using namespace std;

struct State {
	State *prv;
	int cost, type;

	State(int _cost = 10000) : prv(nullptr), cost(_cost), type(-1) {}
	State(State *_prv, int _type) : prv(_prv), type(_type), cost(_prv->cost) {
		if (type < 4) cost++;
		else if (type < 10) cost += 2;
	}
};

State *construct(State *A, int typeA, State *B = nullptr, int typeB = -1) {
	if (!A && !B) return nullptr;
	if (!A) return new State(B, typeB);
	if (!B) return new State(A, typeA);
	if (A->cost < B->cost) return new State(A, typeA);
	return new State(B, typeB);
}

string grid[25];
State *dp[12][40][1 << 13];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int r, c;
	cin >> r >> c;
	getline(cin, grid[0]); // Buffer stuff >:(
	for (int i = 0; i < r; i++) getline(cin, grid[i]);
	int n = r >> 1, m = c >> 1;

	dp[n - 1][0][0] = new State(0);
	for (int j = 1; j <= m; j++) {
		for (int i = 0; i < n; i++) {
			for (int mask = 0; mask < (1 << n + 1); mask++) {
				int r = mask & (1 << i), d = mask & (1 << i + 1);
				// You can't connect over a blocked corridor
				if (r && grid[2 * i + 1][2 * j] == '|') continue;
				if (d && grid[2 * i + 2][2 * j - 1] == '-') continue;
				// An 'X' can't have more than 1 paths going out from it
				if (r && d && grid[2 * i + 1][2 * j - 1] == 'X') continue;
				// Casework for the DP
				if (!i) {
					int prv_base = (mask >> 2) << 1;
					if (grid[2 * i + 1][2 * j - 1] == 'X') {
						if (r || d) {
							if (r) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 1);
							if (d) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 2);
						} else dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base + 1], 3);
					} else {
						if (r && d) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 7);
						else if (r || d) {
							if (r) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base + 1], 8);
							if (d) dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base + 1], 9);
						} else dp[i][j][mask] = construct(dp[n - 1][j - 1][prv_base], 10);
					}
				} else {
					int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
					if (grid[2 * i + 1][2 * j - 1] == 'X') {
						if (r || d) {
							if (r) dp[i][j][mask] = construct(dp[i - 1][j][prv_base], 1);
							if (d) dp[i][j][mask] = construct(dp[i - 1][j][prv_base], 2);
						} else dp[i][j][mask] = construct(
								dp[i - 1][j][prv_base + (1 << i)], 0,
								dp[i - 1][j][prv_base + (1 << i + 1)], 3);
					} else {
						if (r && d) dp[i][j][mask] = construct(dp[i - 1][j][prv_base], 7);
						else if (r || d) {
							if (r) dp[i][j][mask] = construct(
									dp[i - 1][j][prv_base + (1 << i)], 4,
									dp[i - 1][j][prv_base + (1 << i + 1)], 8);
							if (d) dp[i][j][mask] = construct(
									dp[i - 1][j][prv_base + (1 << i)], 5,
									dp[i - 1][j][prv_base + (1 << i + 1)], 9);
						} else dp[i][j][mask] = construct(
								dp[i - 1][j][prv_base + (1 << i) + (1 << i + 1)], 6,
								dp[i - 1][j][prv_base], 10);
					}
				}
			}
		}
	}
	cout << dp[n - 1][m][0]->cost << '\n';
	State *curr = dp[n - 1][m][0];
	for (int j = m - 1; ~j; j--) for (int i = n - 1; ~i; i--) {
		if (curr->type == 0) grid[2 * i][2 * j + 1] = '.';
		else if (curr->type == 1) grid[2 * i + 1][2 * j + 2] = '.';
		else if (curr->type == 2) grid[2 * i + 2][2 * j + 1] = '.';
		else if (curr->type == 3) grid[2 * i + 1][2 * j] = '.';
		else if (curr->type == 4) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j + 2] = '.';
		else if (curr->type == 5) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 2][2 * j + 1] = '.';
		else if (curr->type == 6) grid[2 * i][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.';
		else if (curr->type == 7) grid[2 * i + 1][2 * j + 2] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 2][2 * j + 1] = '.';
		else if (curr->type == 8) grid[2 * i + 1][2 * j + 2] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.';
		else if (curr->type == 9) grid[2 * i + 2][2 * j + 1] = grid[2 * i + 1][2 * j + 1] = grid[2 * i + 1][2 * j] = '.';
		curr = curr->prv;
	}
	for (int i = 0; i < r; i++) cout << grid[i] << '\n';
	return 0;
}

Compilation message

connect.cpp: In constructor 'State::State(State*, int)':
connect.cpp:6:12: warning: 'State::type' will be initialized after [-Wreorder]
    6 |  int cost, type;
      |            ^~~~
connect.cpp:6:6: warning:   'int State::cost' [-Wreorder]
    6 |  int cost, type;
      |      ^~~~
connect.cpp:9:2: warning:   when initialized here [-Wreorder]
    9 |  State(State *_prv, int _type) : prv(_prv), type(_type), cost(_prv->cost) {
      |  ^~~~~
connect.cpp: In function 'int main()':
connect.cpp:37:38: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   37 |    for (int mask = 0; mask < (1 << n + 1); mask++) {
      |                                    ~~^~~
connect.cpp:38:49: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   38 |     int r = mask & (1 << i), d = mask & (1 << i + 1);
      |                                               ~~^~~
connect.cpp:60:38: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   60 |      int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
      |                                    ~~^~~
connect.cpp:60:69: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   60 |      int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
      |                                                                   ~~^~~
connect.cpp:60:59: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   60 |      int prv_base = mask & (((1 << n + 1) - 1) ^ (1 << i) + (1 << i + 1));
      |                                                  ~~~~~~~~~^~~~~~~~~~~~~~
connect.cpp:67:41: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   67 |         dp[i - 1][j][prv_base + (1 << i + 1)], 3);
      |                                       ~~^~~
connect.cpp:73:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   73 |          dp[i - 1][j][prv_base + (1 << i + 1)], 8);
      |                                        ~~^~~
connect.cpp:76:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   76 |          dp[i - 1][j][prv_base + (1 << i + 1)], 9);
      |                                        ~~^~~
connect.cpp:78:52: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   78 |         dp[i - 1][j][prv_base + (1 << i) + (1 << i + 1)], 6,
      |                                                  ~~^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 16 ms 12140 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Correct 1 ms 1260 KB Output is correct
9 Correct 2 ms 2284 KB Output is correct
10 Correct 4 ms 3564 KB Output is correct
11 Correct 4 ms 3052 KB Output is correct
12 Correct 7 ms 5868 KB Output is correct
13 Correct 8 ms 6636 KB Output is correct
14 Correct 8 ms 7788 KB Output is correct
15 Correct 10 ms 9964 KB Output is correct
16 Correct 14 ms 13164 KB Output is correct
17 Correct 20 ms 15212 KB Output is correct
18 Correct 31 ms 28396 KB Output is correct
19 Correct 70 ms 51044 KB Output is correct
20 Correct 41 ms 33192 KB Output is correct