격자상의 경로

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


풀이

로봇은 오른쪽과 아래쪽으로만 이동할 수 있다.
때문에 격자에 도착할 수 있는 경우의 수는 격자의 위 요소와 왼쪽 요소의 도착할 수 있는 경우의 수의 합이다.
즉, 현재 격자가 a[i][j]일 때 도착할 수 있는 경우의 수는 a[i-1][j]+a[i][j-1]이다.
(가장 위쪽, 오른쪽 행, 열은 1이다.)
이런 성질을 바탕으로 a[n-1][m-1]의 경우의 수를 찾으면 된다.
주의할 점으로 무조건 표식이 있는 지점을 지나야 하므로 0,0 에서 표식 지점까지 경우의 수를 찾고
표식 지점부터 n-1, m-1지점까지 위 아이디어를 사용하여 경우의 수를 찾으면 된다.
(표식 지점 기준으로 가장 위쪽, 오른쪽 행, 열은 표식 지점의 경우의 수이다.)