[BOJ] 23880 - Walking Home

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

BOJ - Walking Home

문제 유형: 다이나믹 프로그래밍

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 1024MB

 

문제

Bessie the cow is trying to walk from her favorite pasture back to her barn.

The pasture and farm are on an N×N grid (2≤N≤50), with her pasture in the top-left corner and the barn in the bottom-right corner. Bessie wants to get home as soon as possible, so she will only walk down and to the right. There are haybales in some locations that Bessie cannot walk through; she must walk around them.

Bessie is feeling a little tired today, so she wants to change the direction she walks at most K times (1≤K≤3) .

How many distinct paths can Bessie walk from her favorite pasture to the barn? Two paths are distinct if Bessie walks in a square in one path but not in the other.

 

소 Bessie는 초원에서 헛간으로 돌아가려고 한다.

N x N의 크기의 matrix에서 맨 왼쪽 위에서 맨 오른쪽 아래로 가야 한다.

'.'으로 갈 수 있고, 'H'로는 갈 수 없다.

그녀는 힘들기에, 최대 K번만 방향을 바꿀 수 있다.

몇 가지의 경우의 수로 갈 수 있을까?

 

입력

The input for each test case contains T sub-test cases, each describing a different farm and each of which must be answered correctly to pass the full test case. The first line of input contains T (1≤T≤50). Each of the T sub-test cases follow.

Each sub-test case starts with a line containing N and K.

The next N lines each contain a string of N characters. Each character is either . if it is empty or H if it has a haybale. It is guaranteed the top-left and bottom-right corners of the farm will not contain haybales.

 

첫째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스에는 N과 K가 주어지고, 다음 N개의 줄에는 N길이의 문자열이 주어진다.

 

출력

Output T lines, the ith line containing the number of distinct paths Bessie can take in the ith sub-test case.

T개의 결과를 출력하시오.

 

풀이

dp[행][열][남은횟수][방향] = {행, 열, 남은횟수, 방향}으로 올 수 있는 경우의 수를 담는다.

그러고 왼쪽 또는 아랫쪽으로 전이 가능한 대로 전이시킨다.

만약 오른쪽으로 왔었다면, 오른쪽으로는 k를 소모하지 않고 전이가능하고, 아래로는 k를 소모하고 전이해야 한다.

마찬가지로, 아래를 보며 왔었다면, 아래로는 k를 소모하지 않고 전이가능하고, 오른쪽으로는 k를 소모하고 전이해야 한다.

 

최종적으로 dp[i][j]의 모든 (남은횟수, 방향)조합의 합을 다 더해서 출력하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int N, K;
    cin >> N >> K;
    vector<string> mat(N);
    vector<vector<vector<vector<ll>>>> dp(
        N, vector<vector<vector<ll>>>(
               N, vector<vector<ll>>(K + 1, vector<ll>(2, 0))));
    for (int i = 0; i < N; i++) {
        cin >> mat[i];
    }
    if (N == 1) {
        cout << "1\n";
        return;
    }

    if (mat[0][1] == '.') dp[0][1][K][0] = 1;
    if (mat[1][0] == '.') dp[1][0][K][1] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (mat[i][j] != '.') continue;
            for (int k = 0; k <= K; k++) {
                int r = dp[i][j][k][0];
                if (j + 1 < N && mat[i][j + 1] == '.') {
                    dp[i][j + 1][k][0] += r;
                }
                if (k > 0 && i + 1 < N && mat[i + 1][j] == '.') {
                    dp[i + 1][j][k - 1][1] += r;
                }
                int d = dp[i][j][k][1];
                if (i + 1 < N && mat[i + 1][j] == '.') {
                    dp[i + 1][j][k][1] += d;
                }
                if (k > 0 && j + 1 < N && mat[i][j + 1] == '.') {
                    dp[i][j + 1][k - 1][0] += d;
                }
            }
        }
    }
    ll ans = 0;
    for (int k = K; k >= 0; k--) {
        ans += dp[N - 1][N - 1][k][0];
        ans += dp[N - 1][N - 1][k][1];
    }
    cout << ans << "\n";
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}