[BOJ] 백준 14939번: 불 끄기

첫 줄에서 스위치를 누를수 있는 모든 경우 (1024가지)를 미리 정해놓고

두번째 줄부터 이전 줄의 전구의 켜짐 상태를 그리디하게 끄면서 마지막 줄에 켜진 전구의 유무로 경우의 수를 구하는 문제 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <memory.h>
#include <math.h>
#define INF (10001)
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int nx[5] = { 0,0,0,-1,1 };
int ny[5] = { 0,-1,1,0,0 };
char map[11][11];
char tmp[11][11];
void click(int x, int y) {
	for (int i = 0; i < 5; i++) {
		int _x = x + nx[i];
		int _y = y + ny[i];
		if (_x < 0 || _y < 0 || _x >= 10 || _y >= 10) {
			continue;
		}
		tmp[_x][_y] = (tmp[_x][_y] == '#' ? 'O' : '#');
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	for (int i = 0; i < 10; i++) {
		cin >> map[i];
	}
	int ans = INF;
	for (int init = 0; init < 1024 ; init++) {
		// map 복사
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				tmp[i][j] = map[i][j];
			}
		}
		// 초기 값설정
		int cnt = 0;
		for (int i = 0; i < 10; i++) {
			if (init & (1 << i)) { 
				cnt += 1;
				click(0, i);
			}
		}
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 10; j++) {
				if (tmp[i][j] == 'O') {
					click(i + 1, j);
					cnt += 1;
				}
			}
		}
		int flag = 1;
		for (int i = 0; i < 10; i++) {
			if (tmp[9][i] == 'O') {
				flag = 0;
				break;
			}
		}
		if (flag) ans = min(ans, cnt);
	}
	cout << (ans != INF ? ans : -1);
}