BOJ 15999 뒤집기

사용한 알고리즘

수학

알고리즘 설명

초기의 상태로 되돌릴 수 있는 경우의 수를 새기위한 방법은 아래와 같다.
현재 상태에서 뒤집을 수 있는 판의 개수를 새는 것이다.
판을 뒤집을 수 있는 경우는 상하좌우의 색깔이 모두 자신의 색깔과 같은 경우이며, 범위를 벗어나는 경우 같은 색깔과 같은 조건이다.
이러한 판의 개수를 샌 뒤 이 개수가 K개라고 한다면, 답은 2^K이다.

풀이

// baekjoon 15999 yechan
#include <cstdio>
#include <algorithm>
using namespace	std;
typedef long long ll;
const int MAX_N=2001;
const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
const ll DIV_NUM=1000000007;

int N, M, around, nx, ny, i, j, d, ans;
char board[MAX_N][MAX_N];

ll pow(int a, int b) { // a^b
	if (b == 0) return 1;
	ll ret = pow(a, b/2);
	ret = (ret * ret) % DIV_NUM;
	if (b % 2) ret = (ret * a) % DIV_NUM;
	return ret;
}

int main() {
	scanf("%d%d", &N, &M);
	for (i=0; i<N; i++) scanf("%s", board[i]);

	for (i=0; i<N; i++) {
		for (j=0; j<M; j++) {
			around = 0;
			for (d=0; d<4; d++) {
				nx = i + dir[d][0];
				ny = j + dir[d][1];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M) around++;
				else if (board[nx][ny] == board[i][j]) around++;
			}
			if (around == 4) ans++;
		}
	}
	printf("%lld\n", pow(2, ans));
	return 0;
}