https://www.acmicpc.net/problem/14712
#14712: Nemmonemmo (쉬움)
Nemo는 POOXXX 게임에 깊은 인상을 받아 직사각형 그리드와 “Nemmo”라는 신비한 생물을 사용하는 “Nemmonemmo”라는 게임을 만들었습니다. 이 게임의 규칙은 매우 간단합니다. 회로망
www.acmicpc.net
문제
Nemo는 POOXXX 게임에 깊은 인상을 받아 직사각형 그리드와 “Nemmo”라는 신비한 생물을 사용하는 “Nemmonemmo”라는 게임을 만들었습니다. 이 게임의 규칙은 매우 간단합니다. 그리드에서 무작위로 빈 사각형을 선택하고 그 위에 “Nemmo”를 배치하거나 4개의 “Nemmos”가 있는 2×2 사각형을 찾아 모든 “Nemmos”를 제거하는 데 지칠 때까지 반복합니다.
불행하게도, 그 게임은 그다지 재미있지 않았고 Nemo는 매우 빨리 지루해졌습니다. 실망한 니모는 적당히 게임을 하다가 ‘니모’를 없애고 싶을 때 게임을 끝내기로 결정하지만, 그리드에는 그가 없애야 할 ‘니모’가 없다. Nemo가 게임을 종료할 때 발생할 수 있는 “Nemmo”의 가능한 배치 수를 찾으십시오.
기입
첫 번째 행에는 그리드의 행 수 N과 열 수 M(1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25)이 공백으로 구분되어 제공됩니다.
누르다
“Nemmos”가 있는 사각형이 2 × 2 사각형을 형성하지 않는 첫 번째 행에 주어진 격자의 모든 가능한 배열의 가능한 배열 수를 출력하십시오.
샘플 입력 1
2 2예제 출력 1
15
샘플 입력 2
2 3샘플 출력 2
57
샘플 입력 3
3 5샘플 출력 3
22077import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int M;
static int()() arr;
static int result;
private static void nemmo(int x, int y) {
// 마지막 인덱스인 경우
if(x == N && y == M) {
// 현재 인덱스에 넴모를 두지 않는 경우는 일단 배치 가능
result++;
// 현재 인덱스에 넴모를 두는 경우 없앨 수 있는 넴모가 생겼는지 체크
arr(x)(y) = 1;
if(!check(x, y)) { // 안생겼다면
result++;
}
arr(x)(y) = 0;
return;
}
// 현재 인덱스에 넴모를 두지 않는 경우
// 현재 인덱스에 해당하는 배열 값은 유지한 채 다음 칸으로 넘어감
if(y == M) nemmo(x + 1, 1);
else nemmo(x, y + 1);
// 현재 인덱스에 넴모를 두는 경우
arr(x)(y) = 1;
// 현재 인덱스에 넴모를 둠으로써 없앨 수 있는 넴모가 생겼나 체크
if(check(x, y)) { // 없앨 수 있는 넴모가 생겼으면 return
arr(x)(y) = 0;
return;
}
else { // 아니라면 다음 인덱스로 넘어감
if(y == M) nemmo(x + 1, 1);
else nemmo(x, y + 1);
}
arr(x)(y) = 0;
}
private static boolean check(int x, int y) { // 현재 인덱스에 넴모를 둠으로써 없앨 수 있는 넴모가 생겼나 체크
if(arr(x - 1)(y - 1) + arr(x - 1)(y) + arr(x)(y - 1) + arr(x)(y) == 4
|| arr(x - 1)(y) + arr(x - 1)(y + 1) + arr(x)(y) + arr(x)(y + 1) == 4
|| arr(x)(y - 1) + arr(x)(y) + arr(x + 1)(y - 1) + arr(x + 1)(y) == 4
|| arr(x)(y) + arr(x)(y + 1) + arr(x + 1)(y) + arr(x + 1)(y + 1) == 4)
return true; // 없앨 수 있는 넴모가 생겼다면 true
return false; // 아니라면 false
}
public static void main(String() args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// N, M 입력
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// N x M 배열
arr = new int(N + 2)(M + 2);
// 넴모 배치 가짓수 구하기
nemmo(1, 1);
// 답 출력
System.out.println(result);
}
}