레이팅 미적용최근의 예산 삭감 때문에, FJ는 농장 규모를 줄여서 소들의 방목지가 겨우 5미터 x 5미터 정사각형 들판이 되었다! 들판은 1미터 x 1미터 정사각형들로 이루어진 5x5 격자 형태이며, (1,1)이 왼쪽 위 정사각형의 위치이고 (5,5)가 오른쪽 아래 정사각형의 위치이다.
이 격자의 모든 정사각형은 맛있는 풀로 가득 차 있지만, K개 (0 <= K <= 22, K는 짝수)의 황량한 정사각형에는 풀이 없다. 소 베시(Bessie)는 항상 풀이 있는 (1,1)에서 풀을 뜯기 시작하고, 소 밀드레드(Mildred)는 역시 항상 풀이 있는 (5,5)에서 풀을 뜯기 시작한다.
30분마다 베시와 밀드레드는 각자 자기 정사각형의 풀을 모두 먹어 치우고, 각각 인접한(북, 남, 동, 서) 풀이 있는 정사각형으로 이동한다. 둘은 풀이 있는 모든 정사각형을 먹어 치우고 정확히 같은 최종 위치에서 끝나기를 원한다. 이것이 가능한 서로 다른 방법의 수를 계산하시오. 베시와 밀드레드는 항상 풀이 있는 정사각형으로만 이동하며, 남은 풀이 있는 정사각형이 딱 하나뿐인 마지막 경우가 아니라면 둘이 같은 정사각형으로 이동하는 일은 없다.
첫째 줄: 정수 K.
둘째 줄부터 1+K번째 줄까지: 각 줄에 풀이 없는 정사각형의 위치 (i,j)가 공백으로 구분된 두 정수 i와 j로 주어진다.
베시와 밀드레드가 들판을 걸으며 풀을 모두 먹고 같은 최종 위치에서 끝날 수 있는 서로 다른 방법의 수.
grazing.in · 출력을 쓸 파일 grazing.out4
3 2
3 3
3 4
3 11Output details: There is only one possible solution, with Bessie and Mildred meeting at square (3,5).
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > January > Bronze