[BOJ-10164]격자상의경로

문제에 적힌대로 구현하면 되는 문제였다.

1,1 -> N,M 까지 가는 경로의 수를 구하는 문제.

중간에 O 를 한 부분이 있으면 (O는 최대 한개만 주어짐, 없을 수도 있음) 무조건 그 경로를 들린 경우만 구해야 한다.

움직일 수 있는 것은 아래, 혹은 오른쪽

나머지 방향으로는 움직일 수 없음. 그래서 문제 풀기 쉬움.

1,1 부터 1,M 까지는 모두 경우의 수는 1 

1,1 부터 N,1 까지도 모두 경우의 수는 1 

이제 경우의 수를 모두 더해준다. 

위에서 내려오는 경우, 왼쪽에서 오는 경우를 더해 위 (1,1)~(1,M) 와 (1,1)~(N,1) 경우를 제외하고

 

하게 되면 위에 명시된 이동조건으로 N,M까지의 모든 경우의 수를 구할 수 있음. 그러면? 

이제 O 를 표시한 지점 부터 다시 저 경우를 다시 구함. 

만약에 O 표시가 없다면 board[row-1][col-1] 이 답이 되고,

그래서 place_row 와 place_col을 구한 다음, 위 시행을 똑같이 다시 해줌. 그러면 답을 구할 수 있음.

#include<cstdio>
#define MAX 22
int row, col, check;
 
int imap[MAX][MAX];
 
int main(){
    scanf("%d%d%d",&row ,&col, &check);
 
    int place_row = (check-1)/col;
    int place_col = (check-1)%col;
 
    for(int r = 0 ; r < row ; r++){
        for(int c = 0 ; c < col ; c++){
            if(r==0) imap[r][c] = 1;
            else if(c==0) imap[r][c] = 1;
            else imap[r][c] = imap[r-1][c] + imap[r][c-1];
        }
    }
 
    if(check > 0){ // place O
        for(int r = place_row ; r < row ; r++){
            for(int c = place_col ; c < col ; c++){
                if(r == place_row) imap[r][c] = imap[place_row][place_col];
                else if(c == place_col) imap[r][c] = imap[place_row][place_col];
                else imap[r][c] = imap[r-1][c] + imap[r][c-1];
            }
        }
    }
 
    printf("%d",imap[row-1][col-1]);
    return 0;
}