백준 17070 파이프 옮기기1

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int N;
int map[20][20];
int ax, ay, bx, by;
int cache[20][20][4];


int solve(int sx, int sy, int status) {
	if (sx == N && sy == N) return 1;
	int &ret = cache[sx][sy][status];
	if (ret != -1) return ret;
	ret = 0;
	switch (status) {
	case 1://가로일때
		//가로
		if (sy + 1 <= N && !map[sx][sy+1]) {
			ret += solve(sx, sy + 1, 1);
		}
		//대각선
		if (sx+1 <= N && sy + 1 <= N && !map[sx + 1][sy + 1] && !map[sx][sy + 1] && !map[sx + 1][sy]) {
			ret += solve(sx + 1, sy + 1, 3);
		}
		break;
	case 2://세로
		//세로
		if (sx + 1 <= N && !map[sx + 1][sy]) {
			ret += solve(sx+1, sy, 2);
		}
		//대각선
		if (sx + 1 <= N && sy + 1 <= N && !map[sx + 1][sy + 1] && !map[sx][sy + 1] && !map[sx + 1][sy]) {
			ret += solve(sx + 1, sy + 1, 3);
		}
		break;
	case 3://대각선
		//가로
		if (sy + 1 <= N && !map[sx][sy + 1]) {
			ret += solve(sx, sy + 1, 1);
		}
		//세로
		if (sx + 1 <= N && !map[sx+1][sy]) {
			ret += solve(sx+1, sy, 2);
		}
		//대각선
		if (sx + 1 <= N && sy + 1 <= N && !map[sx + 1][sy + 1] && !map[sx][sy + 1] && !map[sx + 1][sy]) {
			ret += solve(sx + 1, sy + 1, 3);
		}
		break;
	}
	return ret;
}
int main() {
	memset(cache, -1, sizeof(cache));
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	printf("%d", solve(1, 2, 1));
	return 0;
}