[17070] 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

<문제>

하나의 상태는 파이프의 한쪽 끝 좌표 (y, x)와 방향으로 구성할 수 있다.

이를 bfs나 dp로 계산하면 되는데, 회전은 45도로만 가능하다는 부분에 유의할 필요가 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, a[20][20], dp[20][20][3];
int main(void) {
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    dp[1][2][0] = 1;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (i == 1 && j == 1 || i == 1 && j == 2) continue;
            if (a[i][j] == 1) continue;
            dp[i][j][0] += dp[i][j - 1][0] + dp[i][j - 1][2];
            dp[i][j][1] += dp[i - 1][j][1] + dp[i - 1][j][2];
            if (a[i + 1][j - 1] == 0 && a[i + 1][j] == 0) {
                dp[i + 1][j][2] += dp[i][j - 1][0];
                dp[i + 1][j][2] += dp[i][j - 1][2];
                dp[i + 1][j][2] += dp[i][j - 1][1];
            }
        }
    }
    cout << dp[n][n][0] + dp[n][n][1] + dp[n][n][2];
    return 0;
}