체스 러시
시간 제한2.3초메모리 제한64 MB
R행 C열 판에서 기물이 1행의 한 열에서 R행의 목표 열까지 가는 최소 이동 횟수와, 그 횟수로 도달하는 경로의 수를 구합니다.
문제
체스 랜드는 행 열로 이루어진 직사각형 격자 세계이다. 단, 이다. 행은 1부터 까지, 열은 1부터 까지 번호가 매겨져 있다.
체스 랜드에 사는 주민은 흔히 말이라고 부른다. 폰, 룩, 비숍, 퀸, 킹 다섯 종류가 이 땅을 돌아다닌다. 체스 랜드에서 기사도는 오래전에 사라졌기 때문에 나이트는 없다.
각 말은 저마다 다른 방식으로 움직인다. 한 번의 이동에서 다음과 같이 갈 수 있다.
- 폰은 열을 바꾸지 않고 한 행 앞(행 에서 행 )으로 갈 수 있다.
- 룩은 행을 바꾸지 않고 열을 좌우로 원하는 만큼 옮길 수 있다. 또는 열을 바꾸지 않고 행을 앞뒤로 원하는 만큼 옮길 수 있다.
- 비숍은 현재 칸을 지나는 두 대각선 위의 어느 칸으로든 갈 수 있다.
- 퀸은 현재 위치에서 룩이나 비숍이 갈 수 있는 어느 칸으로든 갈 수 있다.
- 킹은 인접한 8칸 중 어느 칸으로든 갈 수 있다.
아래 그림은 각 말이 한 번의 이동으로 갈 수 있는 칸을 X로 표시한 것이다. 행은 아래에서 위로, 열은 왼쪽에서 오른쪽으로 번호가 매겨져 있다.
최근 체스 랜드를 지나던 말이 정체불명의 세력에게 예고 없이 잡혀 사라지는 일이 생기고 있다. 말들은 목적지에 되도록 적은 이동 횟수로 도착하려 한다. 최소 횟수로 도착하는 경로가 많을수록 잡힐 확률이 낮아지므로 그 경로의 수도 중요하다. 두 경로는 방문한 칸이 하나라도 다르면 서로 다른 경로로 본다.
말은 1행의 어느 열에서 체스 랜드에 들어와 행의 어느 열로 나간다. 개의 질문에 답하라. 각 질문에는 말의 종류, 1행에서 들어가는 열 , 행에서 도달해야 하는 열 이 주어진다. 최소 이동 횟수와 그 횟수로 도달하는 서로 다른 경로의 수를 구한다.
입력
첫 줄에 세 정수 , , 가 공백으로 구분되어 주어진다. 이어서 개의 줄이 주어진다. 각 줄에는 말의 종류를 나타내는 문자 (폰은 P, 룩은 R, 비숍은 B, 퀸은 Q, 킹은 K)와 정수 , 이 공백으로 구분되어 주어진다.
출력
개의 줄을 출력한다. 번째 줄에는 번째 질문의 답으로, 최소 이동 횟수와 그 횟수로 도달하는 서로 다른 경로의 수를 로 나눈 나머지를 공백으로 구분하여 출력한다. 도달할 수 없으면 0 0을 출력한다.