-
[1455] 뒤집기 IIBOJ 2022. 2. 24. 19:31
https://www.acmicpc.net/problem/1455
1455번: 뒤집기 II
세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고
www.acmicpc.net
오른쪽 아래부터 동전을 뒤집어주면 더이상 toggle될 필요가 없으면서 앞면인, 완성된 영역을 늘려나갈 수 있다.
#include <bits/stdc++.h>using namespace std;#ifdef ONLINE_JUDGEconstexpr bool local = false;#elseconstexpr bool local = true;#endifusing ll = long long;using pi = pair<ll, ll>;int n, m, ans, a[105][105];void toggle(int y, int x) {ans++;for (int i = 0; i <= y; i++)for (int j = 0; j <= x; j++) a[i][j] = 1 - a[i][j];}bool f(void) {for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)if (a[i][j] == 1) return false;return true;}int main(void) {if (!local) ios_base::sync_with_stdio(0), cin.tie(0);cin >> n >> m;int i, j;for (i = 0; i < n; i++)for (j = 0; j < m; j++) {char x;cin >> x;a[i][j] = (x - '0');}while (1) {bool ret = f();if (ret == true) break;for (i = n - 1; i >= 0; i--) {for (j = m - 1; j >= 0; j--) {if (a[i][j] == 1) {toggle(i, j);goto skip;}}}skip:;}cout << ans;return 0;}
'BOJ' 카테고리의 다른 글
[1727] 커플 만들기 (0) 2022.02.25 [13904] 과제 (0) 2022.02.25 [16120] PPAP (0) 2022.02.24 [3991] 한번 쏘면 멈출 수 없어 (0) 2022.02.23 [21554] 마법의 돌 장난감 (0) 2022.02.22