1137 words
6 minutes
[BOJ] 불 켜기
| TimeLimit | MemoryLimit | Condition | TAG |
|---|---|---|---|
| 2s | 128MB | (1 ≤ N, M ≤ 8) | BruteForce, Greedy |
솔직히 그냥 풀면 되는데… 처음에 가지치기 없이 그냥 풀었다가 머리 깡 당하고, 가만히 있다가 예…
더 생각해보니.. 뭔가 어떤 전구 문제 플레에 있었는데 분명 이거 브포밖에 답이 없는데 막 이러다 그리디로 접근해보자 하고 각잡고 생각하니까 겨우 풀었네요…
완전 어려운 난이도는 아니었는데 왜 이렇게 못 풀었는지 모르겠습니다.. 아직 실력이 많이 부족한가 봅니다. 오류 수정 2시간 동안 너무 힘들었습니다. ㅠ
정답 코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
using namespace std;
using ll = long long;
ll MOD = 1'000'000'007;
int n, m;
set<ll> visited;
//map<ll, int> visited;
ll push(ll current, pair<int, int> yx){
auto [y, x] = yx;
int my = min(y+2, n);
y = max(0, y - 1);
int mx = min(x + 2, m);
x = max(0, x - 1);
// cout << y << " " << my << " " << x << " " << mx << "\n";
for(int cy = y; cy < my; cy++){
for(int cx = x; cx < mx; cx++){
current ^= (1LL << (cy * 8 + cx));
}
}
return current;
}
int main() {
cin >> n >> m;
// 이거 greedy가 맞는듯.
// 그니까 결국 끝에서 바꾸는걸 포인트로 잡는건 맞고
// 순차적으로 들어가는건데 맵 윗줄은 확정적으로 만들어야하니까 그것만 좀 알아서 잘 찾아내서 돌리고, 이후에 greedy하게 왼쪽 대각선있는 놈이 꺼져있으면 키도록 만들면 되는거 아님?
// 그러면 마지막에도 되겠지 뭐
ll state = 0;
for(int i = 0; i < n; i++){
char tmp;
for(int j = 0; j < m; j++){
cin >> tmp;
if(tmp == '*') state |= 1LL << (j + i * 8);
}
}
ll target = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
target |= (1LL << (i * 8 + j));
}
}
// 순차적으로 돌렷는데 못 만드는 모양이면 그냥 못만드는 거니까 미련가지지 않으면 됨.
ll result =LLONG_MAX;
ll check = (1LL << (n+1));
for(ll fy = 0; fy < (1LL << n); fy++){
for(ll fx = 0; fx < (1LL << m); fx++){
ll current = state;
// fy가 첫번째 줄 이ㅐㅅ키임
//fx는 처음 시작 col ㅇㅣㅁ
ll cnt = 0;
bool debug = false;
// for(int i = 0; i < 5; i++){
// if(fx & (1 << i)) cout << 1;
// else cout << 0;
// }
// cout << " " << fx;
// cout << "\n";
//
// if(fy == 15) debug = true;
if(debug) cout << fy << " " << fx << "\n";
for(int i = 0; i < n; i++){
if(fy & (1LL << ((i)))) {
current = push(current, {i, 0});
cnt ++;
}
}
// cout << "\n" << cnt << "\n";
if(debug){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!(current & 1LL << (i * 8 + j))) cout << 0;
else cout << 1;
}
cout << "\n";
}
cout << "\n";
}
for(int i = 0; i < m; i++){
if(fx & (1LL << (i))){
current = push(current, {0, i});
cnt++;
}
}
//
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
// cout << i << " " << j << " " << (target & (1LL << ((i-1) * 8 + (j-1)))) << "\n";
//
// if(i == 3 && j == 3){
// for(int i = 0; i < n; i++){
// for(int j = 0; j < m; j++){
// if(!(current & 1LL << (i * 8 + j))) cout << 0;
// else cout << 1;
// }
// cout << "\n";
// }
// cout << "\n";
//
//
// for(int i = 0; i < n; i++){
// for(int j = 0; j < m; j++){
// if(!(((1LL << ((i-1) * 8 + (j-1)))) & 1LL << (i * 8 + j))) cout << 0;
// else cout << 1;
// }
// cout << "\n";
// }
// cout << "\n";
//
// }
//
if(!(current & (1LL << ((i-1) * 8 + (j-1))))) {
current = push(current, {i, j});
cnt++;
}
}
}
if(debug){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!(current & 1LL << (i * 8 + j))) cout << 0;
else cout << 1;
}
cout << "\n";
}
cout << "\n";
}
if(target == current)
result = min(result, cnt);
}
}
//
if(result == LLONG_MAX) cout << -1;
else cout << result;
// cout << bfs(state);
// if(visited.find(LLONG_MAX) == visited.end()) cout << -1;
// else cout << visited[LLONG_MAX];
return 0;
}
/*
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!(state & 1 << (i * 8 + j))) cout << 0;
else cout << 1;
}
cout << "\n";
}
state = push(state, {2, 2});
cout << "\n";
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!(state & 1 << (i * 8 + j))) cout << 0;
else cout << 1;
}
cout << "\n";
}
state = push(state, {2, 2});
cout << "\n";
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!(state & 1 << (i * 8 + j))) cout << 0;
else cout << 1;
}
cout << "\n";
}
*/