제출 #1154843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154843		gelastropod	Selotejp (COCI20_selotejp)	C++20	110 / 110	70 ms	80968 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
	int n, m;
	cin >> n >> m;
	string s;
	vector<vector<int>> closed(n, vector<int>(m, false));
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < m; j++) {
			if (s[j] == '#')
				closed[i][j] = true;
		}
	}
	vector<vector<vector<int>>> mem(n, vector<vector<int>>(m, vector<int>(1LL << m, -1)));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < (1LL << m); k++) {
				if (i == 0 && j == 0) {
					mem[i][j][k] = closed[i][j];
					continue;
				}
				if (!closed[i][j]) {
					mem[i][j][k] = min(mem[i - (j == 0)][(j + m - 1) % m][k], mem[i - (j == 0)][(j + m - 1) % m][k ^ (1LL << j)]);
					continue;
				}
				if (j != 0 && !((k & (1LL << j)) || (k & (1LL << (j - 1))))) {
					mem[i][j][k] = min(mem[i][j - 1][k], mem[i][j - 1][k ^ (1LL << j)]);
					if (!closed[i][j - 1]) {
						mem[i][j][k]++;
					}
				}
				if (j == 0 || (!(k & (1LL << j)) && (k & (1LL << ((j + m - 1) % m))))) {
					mem[i][j][k] = min(mem[i - (j == 0)][(j + m - 1) % m][k], mem[i - (j == 0)][(j + m - 1) % m][k ^ (1LL << j)]) + 1;
				}
				if (k & (1LL << j)) {
					if (i != 0 && closed[i - 1][j]) {
						mem[i][j][k] = min(mem[i - (j == 0)][(j + m - 1) % m][k], mem[i - (j == 0)][(j + m - 1) % m][k ^ (1LL << j)] + 1);
					}
					else {
						mem[i][j][k] = min(mem[i - (j == 0)][(j + m - 1) % m][k], mem[i - (j == 0)][(j + m - 1) % m][k ^ (1LL << j)]) + 1;
					}
				}
			}
		}
	}
	int ans = INT_MAX;
	for (int i : mem[n - 1][m - 1])
		ans = min(ans, i);
	cout << ans << '\n';
}

• Subtask 1: 35 / 35
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40