알고리즘 13주차 격자상의 경로 10164 C++

문제

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.) 

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 

• 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
• 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다. 

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

• 1 → 2 → 3 → 8 → 9 → 10 → 15
• 1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라. 

---

->N*M인 격자에 번호가 1부터 순서대로 있는데 0가 적힌 칸을 반드시 지나면서 (1,1)에서 (n,m)으로 가는 경우의 수

#include <iostream>
using namespace std;
typedef long long ll;

ll arr[16][16];
ll dp[16][16];
int main(void){
    
 
    int number = 1;
 
    int n,m,k;
    cin >> n >> m >> k;
 
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            arr[i][j] = number;
            number++;
            dp[i][j] = 1;
        }
    }
 
 
    /*(1,1) -> (n,m)로 가는 모든 경로 */
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(j != 1){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
            
        }
    }
    
    ll cur_dp_count = dp[n][m]; 
    ll zero_dp = 0;
    int x = 0;
    int y = 0;
 
    /* 동그라미가 적힌 수를 찾기 */
    bool is_find = false;
    for(int i = 1;i<=15;i++){
        for(int j = 1;j<=15;j++){
            if(arr[i][j] == k){
                is_find = true;
                dp[i][j] = 0;
                x = i;
                y = j;
                break;
            }
        }
        if(is_find == true){
            break;
        }
    }
 
    /*동그라미가 적힌 칸을 거치지 않고 가는 경우*/
    for(int i = x;i<=n;i++){
        for(int j = y;j<=m;j++){
            if(i == x && j == y){
                dp[i][j] = 0;
            }
            else{
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }

 
    zero_dp = dp[n][m];
    if(cur_dp_count == zero_dp){
        cout << dp[n][m];
        return 0;
    }
    else{
        cout << cur_dp_count - zero_dp;
        return 0;
    }
 

}