백준 6510 (C++)

최초 업로드: 2025-10-19 12:51:52

최근 수정 시간: 2025-10-19 12:51:52

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] Annoying painting tool

[문제 링크](https://www.acmicpc.net/problem/6510)

## 문제 설명

Maybe you wonder what an annoying painting tool is? First of all, the painting tool we speak of supports only black and white. Therefore, a picture consists of a rectangular area of pixels, which are either black or white. Second, there is only one operation how to change the colour of pixels:

Select a rectangular area of r rows and c columns of pixels, which is completely inside the picture. As a result of the operation, each pixel inside the selected rectangle changes its colour (from black to white, or from white to black).

Initially, all pixels are white. To create a picture, the operation described above can be applied several times. Can you paint a certain picture which you have in mind?

## 입력

The input contains several test cases. Each test case starts with one line containing four integers n, m, r and c. (1 ≤ r ≤ n ≤ 100, 1 ≤ c ≤ m ≤ 100), The following n lines each describe one row of pixels of the painting you want to create. The ith line consists of m characters describing the desired pixel values of the ith row in the finished painting ('0' indicates white, '1' indicates black).

The last test case is followed by a line containing four zeros.

## 출력

For each test case, print the minimum number of operations needed to create the painting, or -1 if it is impossible.

## 풀이
맨 왼쪽 위에서부터 만들고 싶은 것과 다른 경우 그리디하게 한번씩 뒤집어보면 된다. 입력된 상태에서 0을 만들도록 구현하였다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int n, m, r, c;
bool arr[100][100];

bool chk() {
 for(int i=0;i<n;i++) {
 for(int j=0;j<m;j++) {
 if(arr[i][j]) return false;
 }
 }
 return true;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 while(true) {
 cin >> n >> m >> r >> c;
 if(!n) break;
 for(int i=0;i<n;i++) {
 string s; cin >> s;
 for(int j=0;j<m;j++) arr[i][j] = s[j]-'0';
 }

int cnt=0;
 for(int i=0;i<=n-r;i++) {
 for(int j=0;j<=m-c;j++) {
 if(arr[i][j]) {
 cnt++;
 for(int k=0;k<r;k++) {
 for(int l=0;l<c;l++) {
 arr[i+k][j+l]^=1;
 }
 }
 }
 }
 }
 cout << (chk() ? cnt : -1) << '\n';
 }
}
```