[1505] 불 켜기

https://www.acmicpc.net/problem/1505

1505번: 불 켜기

<문제>

첫 행, 첫 열을 브루트포스하게 선택한 뒤, (1, 1)부터 (n-1, m-1)까지 순차적으로 훑으며

(i-1, j-1)이 꺼져있을 때 (i, j)를 켠다는 그리디적 방식으로 완전탐색이 가능하다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, dy[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1},
               dx[9] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
bool a[10][10];
bool cloneMap[10][10];
void toggle(int y, int x) {
    cnt++;
    for (int i = 0; i < 9; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny >= 1 && ny <= n && nx >= 1 && nx <= m) a[ny][nx] = 1 - a[ny][nx];
    }
}
bool isAllOn(void) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 0) return false;
    return true;
}
int main(void) {
    cin >> n >> m;
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) {
            char x;
            cin >> x;
            if (x == '*') a[i][j] = 1;
            cloneMap[i][j] = a[i][j];
        }
    int bitX = (1 << m);
    int bitY = (1 << n);
    int ans = 54321;
    for (int btx = 0; btx < bitX; btx++) {
        for (int bty = 0; bty < bitY; bty++) {
            for (i = 1; i <= n; i++)
                for (j = 1; j <= m; j++) a[i][j] = cloneMap[i][j];
            cnt = 0;
            for (i = 0; i < m; i++)
                if (btx & (1 << i)) toggle(1, i + 1);
            for (i = 0; i < n; i++)
                if (bty & (1 << i)) toggle(i + 1, 1);
            for (i = 2; i <= n; i++)
                for (j = 2; j <= m; j++)
                    if (a[i - 1][j - 1] == 0) toggle(i, j);
            if (isAllOn()) ans = min(cnt, ans);
        }
    }
    if (ans == 54321) ans = -1;
    cout << ans;
    return 0;
}