[백준] 23880번 : Walking Home (C++)

23880번 : Walking Home

---

문제)

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.

 

 

 

입력 :

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.

 

 

 

출력 :

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

 

 

 

We'll denote Bessie's possible paths as strings of D's and R's, indicating that Bessie moved either down or right, respectively.

In the first sub-test case, Bessie's two possible walks are DDRR and RRDD.

In the second sub-test case, Bessie's four possible walks are DDRR, DRRD, RDDR, and RRDD.

In the third sub-test case, Bessie's six possible walks are DDRR, DRDR, DRRD, RDDR, RDRD, and RRDD.

In the fourth sub-test case, Bessie's two possible walks are DDRR and RRDD.

In the fifth and sixth sub-test cases, it is impossible for Bessie to walk back to the barn.

In the seventh sub-test case, Bessie's six possible walks are DDRDRR, DDRRDR, DDRRRD, RRDDDR, RRDDRD, and RRDRDD.

 

 

풀이)

 

// 23880. Walking Home
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int n, k;
vector<string> vec;
int dx[2] = { 1, 0 };
int dy[2] = { 0, 1 };
 
int dp[60][60][4][3];
 
int recur(int x, int y, int change, int dir)
{
    if (x == n - 1 && y == n - 1) return 1;
 
    if (dp[x][y][change][dir] != -1) return dp[x][y][change][dir];
 
    int ret = 0;
 
    // 방향 전환을 다 쓰지 않았을 경우
    if (change <= k)
    {
        for (int i = 0; i < 2; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            // 목초지를 벗어났을 경우
            if (nx >= n || ny >= n) continue;
            // 가려는 곳이 건초인 경우
            if (vec[nx][ny] == 'H') continue;
 
            if (dir == i) ret += recur(nx, ny, change, i);
            else ret += recur(nx, ny, change + 1, i);
        }
    }
    // 방향 전환을 다 썼을 경우 -> 현재 방향으로만 전진한다.
    else
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
 
        // 목초지를 벗어난 것과, 건초인 경우를 제외한다.
        if (!(nx >= n || ny >= n) && vec[nx][ny] != 'H')
            ret += recur(nx, ny, change, dir);
    }
 
    dp[x][y][change][dir] = ret;
 
    return ret;
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
    cin >> t;
    while (t--)
    {
        vec.clear();
        fill(&dp[0][0][0][0], &dp[59][59][3][3], -1);
 
        cin >> n >> k;
 
        vec.resize(n);
        for (string& ele : vec) cin >> ele;
 
        cout << recur(0, 0, 0, 3) << '\n';
    }
 
    return 0;
}
 

---

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

23880번: Walking Home