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

 

 

문제 설명

문제 링크

http://icpc.me/17070

17070번: 파이프 옮기기 1

문제 풀이

dp를 이용하여 풀 수 있다.

dp[x][y][state] : (1, 1)에서 가장 오른쪽 아래 점 (x, y)까지 state(가로, 세로, 대각선)로 올 수 있는 개수

코드

#include <cstdio>
#include <cstring>

int arr[20][20];
int dp[20][20][3], n;

bool check(int y, int x) { // 대각선 체크
    if (!arr[y + 1][x] && !arr[y + 1][x + 1] && !arr[y][x + 1]) return true;
    return false;
}

int dpf(int y, int x, int s) {
    int &ret = dp[y][x][s];
    if (~ret) return ret;
    if (y == n && x == n) return 1;
    if (y > n || x > n) return 0;
    ret = 0;
    if (s == 0) { // 가로
        if (!arr[y][x + 1]) ret += dpf(y, x + 1, 0);
        if  (check(y, x)) ret += dpf(y + 1, x + 1, 2);
    } else if (s == 1) { // 세로
        if (!arr[y + 1][x]) ret += dpf(y + 1, x, 1);
        if (check(y, x)) ret += dpf(y + 1, x + 1, 2);
    } else { // 대각선
        if (!arr[y][x + 1]) ret += dpf(y, x + 1, 0);
        if (!arr[y + 1][x]) ret += dpf(y + 1, x, 1);
        if (check(y, x)) ret += dpf(y + 1, x + 1, 2);
    }
    return ret;
}

int main() {
    memset(dp, -1, sizeof dp);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &arr[i][j]);
    printf("%d", dpf(1, 2, 0));
}