레이팅 미적용설명
농부 존의 소들이 R행 C열 격자에서 (2 <= R <= 750, 2 <= C <= 750) 사방치기의 변형 놀이를 한다. 각 칸에는 1..K 범위의 정수가 적혀 있다 (1 <= K <= R*C). 소는 왼쪽 위 칸에서 시작해 점프를 반복하여 오른쪽 아래 칸으로 이동한다. 점프는 다음 조건을 모두 만족할 때에만 유효하다:
1) 현재 칸과 다른 정수가 적힌 칸으로 점프해야 하고,
2) 점프해 가는 칸이 현재 칸보다 최소 한 행 아래에 있어야 하며,
3) 점프해 가는 칸이 현재 칸보다 최소 한 열 오른쪽에 있어야 한다.
왼쪽 위 칸에서 오른쪽 아래 칸까지 가는 서로 다른 유효한 점프 수열의 개수를 계산하도록 소들을 도와주자.
제약
입력 형식
첫째 줄에 R, C, K가 주어진다. 다음 R개의 줄 각각에 1..K 범위의 정수 C개가 주어진다.
출력 형식
왼쪽 위 칸에서 오른쪽 아래 칸으로 점프해 가는 서로 다른 방법의 수를 1000000007로 나눈 나머지를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
hopscotch.in · 출력을 쓸 파일 hopscotch.out예제 1
입력
4 4 4
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1출력
5문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > February > Gold
태그