[백준] 17070 파이프 옮기기 1

[백준] 17070 파이프 옮기기 1

• https://www.acmicpc.net/problem/17070

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<vector<int>> board;

//state 0: 가로, 1: 세로, 2: 대각선
int cache[17][17][3];

//파이프의 위치 파이프의 좌측 상단 기준으로 함
vector<vector<pair<int, int>>> cond0 = { {{0, 2}} , {{0, 2}, {1, 1}, {1, 2}} };
vector<vector<pair<int, int>>> cond1 = { {{2, 0}} , {{1, 1}, {2, 0}, {2, 1}} };
vector<vector<pair<int, int>>> cond2 = { {{1, 2}} , {{2, 1}},  {{1, 2}, {2, 1}, {2, 2}} };

bool inRange(int r, int c) {
	if ((r < 0) || (r >= N)) return false;
	if ((c < 0) || (c >= N)) return false;
	return true;
}

//(r, c)에서 state인 상태일 때 (N-1, N-1)까지 갈 수 있는 방법의 수
int solve(int r, int c, int state) {
	//목적지 도착
	if (state == 0) {
		if ((r == (N - 1)) && (c == (N - 2))) return 1;
	}
	else if (state == 1) {
		if ((r == (N - 2)) && (c == (N - 1))) return 1;
	}
	else if (state == 2) {
		if ((r == (N - 2)) && (c == (N - 2))) return 1;
	}

	int& ret = cache[r][c][state];
	if (ret != -1) return ret;

	ret = 0;
	//현재 파이프 가로 상태
	if (state == 0) {
		//다음 상태 가로
		bool possible = true;
		for (int i = 0; i < cond0[0].size(); ++i) {
			int nextR = r + cond0[0][i].first;
			int nextC = c + cond0[0][i].second;
			if (!inRange(nextR, nextC) || (board[nextR][nextC] == 1)) {
				possible = false;
				break;
			}
		}
		if (possible) ret += solve(r, c + 1, 0);

		//다음 상태 대각선
		possible = true;
		for (int i = 0; i < cond0[1].size(); ++i) {
			int nextR = r + cond0[1][i].first;
			int nextC = c + cond0[1][i].second;
			if (!inRange(nextR, nextC) || (board[nextR][nextC] == 1)) {
				possible = false;
				break;
			}
		}
		if (possible) ret += solve(r, c + 1, 2);

	}
	//현재 파이프 세로 상태
	else if (state == 1) {
		//다음 상태 세로
		bool possible = true;
		for (int i = 0; i < cond1[0].size(); ++i) {
			int nextR = r + cond1[0][i].first;
			int nextC = c + cond1[0][i].second;
			if (!inRange(nextR, nextC) || (board[nextR][nextC] == 1)) {
				possible = false;
				break;
			}
		}
		if (possible) ret += solve(r+1, c, 1);

		//다음 상태 대각선
		possible = true;
		for (int i = 0; i < cond1[1].size(); ++i) {
			int nextR = r + cond1[1][i].first;
			int nextC = c + cond1[1][i].second;
			if (!inRange(nextR, nextC) || (board[nextR][nextC] == 1)) {
				possible = false;
				break;
			}
		}
		if (possible) ret += solve(r + 1, c, 2);

	}
	//현재 파이프 대각선 상태
	else if (state == 2) {
		//다음 상태 가로
		bool possible = true;
		for (int i = 0; i < cond2[0].size(); ++i) {
			int nextR = r + cond2[0][i].first;
			int nextC = c + cond2[0][i].second;
			if (!inRange(nextR, nextC) || (board[nextR][nextC] == 1)) {
				possible = false;
				break;
			}
		}
		if (possible) ret += solve(r+1, c + 1, 0);
		
		//다음 상태 세로
		possible = true;
		for (int i = 0; i < cond2[1].size(); ++i) {
			int nextR = r + cond2[1][i].first;
			int nextC = c + cond2[1][i].second;
			if (!inRange(nextR, nextC) || (board[nextR][nextC] == 1)) {
				possible = false;
				break;
			}
		}
		if (possible) ret += solve(r+1, c + 1, 1);

		//다음 상태 대각선
		possible = true;
		for (int i = 0; i < cond2[2].size(); ++i) {
			int nextR = r + cond2[2][i].first;
			int nextC = c + cond2[2][i].second;
			if (!inRange(nextR, nextC) || (board[nextR][nextC] == 1)) {
				possible = false;
				break;
			}
		}
		if (possible) ret += solve(r+1, c + 1, 2);
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; ++i) {
		vector<int> inputV;
		for (int j = 0; j < N; ++j) {
			int input;
			cin >> input;
			inputV.push_back(input);
		}
		board.push_back(inputV);
	}

	//캐시 초기화
	for (int i = 0; i < 17; ++i) {
		for (int j = 0; j < 17; ++j) {
			cache[i][j][0] = -1;
			cache[i][j][1] = -1;
			cache[i][j][2] = -1;
		}
	}

	cout << solve(0, 0, 0);

	return 0;
}