백준 17069번 파이프 옮기기2

https://www.acmicpc.net/problem/17069

17069번: 파이프 옮기기 2

 

 

 

 

 

<접근방법>

완전탐색으로 할 경우 시간초과가 납니다.

dp로 중복탐색을 없애야 합니다.

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

int n, map[33][33];
long long cache[33][33][3];
int dy[3] = {0, 1, 1};
int dx[3] = {1, 0, 1};

long long dfs(int y, int x, int d) {
	//기저사례
	if (y == n - 1 && x == n - 1) return 1;

	//중복방문
	long long &res = cache[y][x][d];
	if (res != -1) return res;
	res = 0;
	
	for (int i = 0; i < 3; i++) {
		if (d == 0 && i == 1) continue;
		if (d == 1 && i == 0) continue;

		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 | ny >= n | nx < 0 | nx >= n | map[ny][nx] == 1) continue;
		if (i == 2 && (map[y + 1][x] == 1 || map[y][x + 1] == 1)) continue;

		res += dfs(ny, nx, i);
	}
	return res;
}

int main() {
	memset(cache, -1, sizeof(cache));

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	cout << dfs(0, 1, 0) << '\n';

	return 0;
}