#include #define ll long long #define endl '\n' #define all(x) (x).begin(), (x).end() #define vi vector #define vc vector #define vvi vector #define vvc vector #define vb vector #define vvb vector #define pii pair #define loop(i, s, n) for (int i = s; i < n; i++) #define X first #define Y second using namespace std; int N, M; vvc board; vvc tmp; int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1}; int ans = 987654321; vector> cctvs; // #, i, j int dir[8]; void fill(int dir, int i, int j) { // dir: 밑변부터 시계방향으로 0 1 3 2 int mxI = tmp.size(), mxJ = tmp[0].size(); while (i >= 0 && j >= 0 && i < mxI && j < mxJ && tmp[i][j] != '6') { if (tmp[i][j] == '0') tmp[i][j] = '7'; if (dir == 0) i++; else if (dir == 1) j--; else if (dir == 2) j++; else if (dir == 3) i--; } } void combs() { int cnt = 0; while (cnt <= pow(4, cctvs.size())) { cnt++; tmp = board; loop(i, 0, cctvs.size()) { auto [no, ci, cj] = cctvs[i]; if (no == 1) { fill(dir[i], ci, cj); } else if (no == 2) { fill(dir[i], ci, cj); fill(3 - dir[i], ci, cj); } else if (no == 3) { if (dir[i] == 0) { fill(0, ci, cj); fill(1, ci, cj); } else if (dir[i] == 1) { fill(1, ci, cj); fill(3, ci, cj); } else if (dir[i] == 2) { fill(3, ci, cj); fill(2, ci, cj); } else if (dir[i] == 3) { fill(2, ci, cj); fill(0, ci, cj); } } else if (no == 4) { loop(k, 0, 4) { if (k == dir[i]) continue; fill(dir[i], ci, cj); } } else if (no == 5) { fill(0, ci, cj); fill(1, ci, cj); fill(2, ci, cj); fill(3, ci, cj); } } int tmp_cnt = 0; loop(i, 0, N) loop(j, 0, M) { if (tmp[i][j] == '0') tmp_cnt++; } int idx = 0; do { if (++dir[idx] == 4) { dir[idx++] = 0; } else { break; } } while (idx < cctvs.size()); ans = min(ans, tmp_cnt); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M; board.assign(N, vc(M)); loop(i, 0, N) { loop(j, 0, M) { cin >> board[i][j]; if (!(board[i][j] == '0' || board[i][j] == '6')) { cctvs.emplace_back(board[i][j] - '0', i, j); } } } combs(); cout << ans << endl; }

제출 #50206

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: