knight moves > 문제은행



실전대비 Level8

1763 : knight moves

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 1 회    시도횟수: 1 회   



체스의 Knight는 L자 모양으로 점프할 수 있는 말이다. 

(r1, c1)에서 (r2, c2)로 점프할 수 있다는 뜻은 (r1 - r2)2 + (c1 - c2)2 = 5를 만족하는 것과 같은 의미를 가진다.

이 문제에서는 왼쪽 위 좌표(1, 1)에서 출발하여 (H, W)까지 이동하는 것이 목표이다. 

또한 이 문제에서 적용되는 두 가지 제약조건이 있는데, 첫 번째 조건은 Knight는 반드시 x, y 좌표가 증가하는 방향으로만 이동하여야 한다. 

즉 (1, 2)로 이동하거나 (2, 1)로 이동하여야 한다. [ (1, -2)나 (2, -1)은 잘못된 이동이다. ] 

두 번째 조건은 Knight가 절대로 갈 수 없는 바위가 R개(R≤10) 있다는 점이다.

당신은 (1, 1)에서 (H, W)까지 가는 경로의 수를 구하고 싶어한다. 

다만 이 수는 매우 크기 때문에 10007로 나눈 나머지를 구하려고 한다. 

참고로 10007은 소수(Prime Number)이다.




입력의 첫번째 줄에는 H W R이 입력된다(1≤W≤108 , 1≤H≤108).
그 다음 줄에는 바위의 좌표 r, c가 입력된다(1≤r≤H 1≤c≤W).




입력에 대해 (1, 1)에서 (H, W)로 이동하는 모든 경우의 수를 10007로 나눈 나머지를 출력한다.



4 4 1
2 1
2



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