14939 ๋ถ๋๊ธฐ
์๊ณ ๋ฆฌ์ฆ(๋ธ๋ฃจํธ, ๊ทธ๋ฆฌ๋, ๋นํธ๋ง์คํน)
1. ์ต์ํ์ผ๋ก ๋๋ฌ์ผํ๋ ๊ฒฝ์ฐ : ํ ์นธ์ ํ๋ฒ๋ง ๋๋ฌ์ผํจ. ๋๋ฒ ์ด์๋๋ฅด๋ฉด ์ต์๊ฐ ์๋๊ณ , ๋ฌดํ ๋ฃจํ๊ฐ ๋ ์ ์์
2. ๋ชจ๋ ๋ฐฉ๋ฒ์ ๋ค ๊ฒ์ฌํด๋ด์ผ ์ ๋ต์ ์ป์ ์ ์์ -> ๋ธ๋ฃจํธ ํฌ์ค
3. ํ๋ฒ์ฉ๋ง ๋๋ฅด๋ฉด ๋๋ฅด๋ ์์๋ ์ค์ํ์ง์์ -> ์ฒซ์ค๋ถํฐ ์ฐจ๋ก๋๋ก ๋๋ฆ
4. ์ด๋ ์ฒซ๋ฒ์งธ์ค์ ๋ชจ๋ ๊ฒฝ์ฐ๋ก ๋๋ฅธ๋ค๊ณ ์น๊ณ , ๋๋ฒ์งธ ์ค๋ถํฐ๋ ์์ ์ ๊ตฌ๊ฐ ์ผ์ง ๊ฒฝ์ฐ๋ง ๋๋ฌ๋ ํด๊ฒฐ์ด ๊ฐ๋ฅํ๋ค. -> ๊ทธ๋ฆฌ๋
5. ๋ชจ๋ ๊ฒฝ์ฐ๋ 0~1023๊น์ง ๋นํธ๋ง์คํน ๋ฐฉ์์ผ๋ก ๋๋ฅด์ -> ๋นํธ๋ง์คํน
์ฝ๋
#include <bits/stdc++.h>
using namespace std;
bool smap[10][10], tempMap[10][10];
int brute();
int rest();
void swit(int r, int c);
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
for (int i = 0; i < 10; i++) {
char t;
for (int j = 0; j < 10; j++) {
cin >> t;
if (t == '#')
smap[i][j] = 0;
else if (t == 'O')
smap[i][j] = 1;
}
}
int result = brute();
if (result >= 2000000000)
cout << -1;
else
cout << result;
}
int brute() {
int result = 2000000000;
for (int i = 0; i <= 1023; i++) {
memcpy(tempMap, smap, sizeof(smap));
int k = 0, count = 0;
for (int j = 512; j >= 1; j /= 2) {
if (i & j) {
swit(0, k);
count++;
}
k++;
}
int r = rest();
result = min(result, count + r);
}
return result;
}
int rest() {
int count = 0;
for (int i = 1; i < 10; i++)
for (int j = 0; j < 10; j++)
if (tempMap[i - 1][j]) {
swit(i, j);
count++;
}
for (int j = 0; j < 10; j++) {
if (tempMap[9][j])
count = 2000000000;
}
return count;
}
void swit(int r, int c) {
tempMap[r][c] = !(tempMap[r][c]);
if (r > 0)
tempMap[r - 1][c] = !(tempMap[r - 1][c]);
if (c < 9 )
tempMap[r][c + 1] = !(tempMap[r][c + 1]);
if (r < 9)
tempMap[r + 1][c] = !(tempMap[r + 1][c]);
if (c > 0)
tempMap[r][c - 1] = !(tempMap[r][c - 1]);
}