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]);
}