Informatica Online Judge

  길 찾기 [1687 / 0697]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 57   Total Tried : 76


The Champion of this Problem (C++) : ajou709 - ms / 355byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [elener]

Background

(1,1)인 S에서 (n,m)까지의 E까지 가는 모든 경우를 알아보고자 한다.

갈 수 있는 길은 1, 지나갈 수 없는 벽은 0으로 표시되어 있다.

단, S 에서 E까지 가는 경로가 하나도 없는 경우는 없으며, 오른쪽 또는 아래쪽으로만 이동할 수 있다.



Input

첫째줄에는 지도의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1<=N,M<=100)이 입력된다.
두 번째 줄부터는 길(1)과 벽(0)을 행, 열로 주어지며, 각 값은 공백으로 구분된다.

Output

오른쪽 또는 아래쪽으로만 이동한다고 할 때, (1,1) 에서 (n,m)까지 갈 수 있는 경우의 수를 구하여라.

IO Example

입력
5 5
1 1 1 1 0
1 1 0 0 1
1 1 1 1 1
1 0 1 0 1
0 1 1 1 1

출력
6

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]