격자상의 경로 > 문제은행

본문 바로가기


문제은행

2795 : 격자상의 경로

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 391회    시도횟수: 1324회   



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

 

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

 

e09276dd23a0fb0b7176dbf6855f6904_1453376 

 

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

 

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

 

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

 

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

 

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


입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 O로 표시된 칸의 번호를 나타내는 정수 K (K = 0 또는 1 < K < N × M )가 차례로 주어지며, 각 값은 공백으로 구분된다.

K의 값이 0인 경우도 있는데, 이는 O로 표시된 칸이 없음을 의미한다. N 과 M 이 동시에 1인 경우는 없다.

<제약조건>
• 부분문제1: 전체 점수 100점 중 9점에 해당하며, 1 ≤ N, M ≤ 5 이고 K = 0 이다.
• 부분문제2: 전체 점수 100점 중 24점에 해당하며, 1 ≤ N, M ≤ 5 이고 1 < K < N × M 이다.
• 부분문제3: 전체 점수 100점 중 23점에 해당하며, 1 ≤ N, M ≤ 15 이고 K = 0 이다.
• 부분문제4: 전체 점수 100점 중 44점에 해당하며, 원래의 제약조건 이외에 아무제약조건이 없다.


출력의 이름은 output.txt이다.

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다.


[Copy]
3 5 8
[Copy]
9


[Copy]
7 11 0
[Copy]
8008


[Copy]
7 11 76
[Copy]
5005




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.