27469번 - 퀸 움직이기 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 270 | 46 | 40 | 38.835% |
문제
숙제를 하지 않고 체스와 조합론에 빠져있던 은재가 생활관에 체스판을 하나 들고 왔다. 이 체스판은 특이해서 $8 \times 8$ 형태의 기본적인 판 뿐만 아니라 $17 \times 19$ 크기나 심지어 $1 \times 100$의 크기처럼 자유자재로 판의 크기를 조절할 수 있다.
체스 고수가 되기 위해서 열심히 체스를 두던 은재는 수많은 패배 끝에, 상대 기물의 수비가 약한 약점 칸을 찾아서 공략하는 것이 중요하다는 걸 깨닫게 되었다. 조합론에 빠진 은재는 퀸을 움직여서 상대의 약점 칸으로 보내는 방법이 얼마나 있을지 궁금해서 하라는 체스는 두지 않고 다음과 같은 질문을 던지게 된다.
체스에서 퀸이 가장 중요한 기물인데, 지금 내 퀸이 있는 위치에서 정확하게 $K$번 움직여서 원하는 위치로 보내는 방법이 얼마나 될까?
현재 체스판에는 퀸의 이동을 방해하는 장애물들과 은재의 퀸이 있다. 장애물이 없을 수도 있다.
체스판은 $N$행 $M$열로 구성되어 있고, $r$행 $c$열의 칸은 $(r, c)$로 나타낸다. $(1 \le r \le N$; $1 \le c \le M)$ 또한, 체스판의 각 칸은 장애물이 있는 칸이거나 없는 칸이다.
초기에 퀸의 위치는 $(R_s, C_s)$, 퀸을 보내고자 하는 위치는 $(R_e, C_e)$이며, 아래 규칙에 따라 퀸을 움직일 수 있다.
- 현재 칸을 $(R, C)$라고 할 때, 다음 $8$가지 방향 중 하나의 방향으로 원하는 거리만큼 움직일 수 있다.
- 위 — $(R - 1, C), (R - 2, C), (R - 3, C), \cdots$
- 아래 — $(R + 1, C), (R + 2, C), (R + 3, C), \cdots$
- 왼쪽 — $(R, C - 1), (R, C - 2), (R, C - 3), \cdots$
- 오른쪽 — $(R, C + 1), (R, C + 2), (R, C + 3), \cdots$
- 왼쪽 위 대각선 — $(R - 1, C - 1), (R - 2, C - 2), (R - 3, C - 3), \cdots$
- 오른쪽 위 대각선 — $(R - 1, C + 1), (R - 2, C + 2), (R - 3, C + 3), \cdots$
- 왼쪽 아래 대각선 — $(R + 1, C - 1), (R + 2, C - 2), (R + 3, C - 3), \cdots$
- 오른쪽 아래 대각선 — $(R + 1, C + 1), (R + 2, C + 2), (R + 3, C + 3), \cdots$
- 정한 방향으로 움직일 때 장애물이 있는 칸을 지날 수 없다.
- 체스판 밖으로 나가거나 장애물이 있는 칸으로 움직일 수 없다.
- 두 번 연속으로 같은 방향으로 움직일 수 없다.
- 퀸을 제자리에 두고 턴을 넘기는 것은 불가능하다.
은재를 위해 은재가 퀸을 $K$번 움직여서 $(R_e, C_e)$ 칸으로 보낼 수 있는 경우의 수를 구하는 프로그램을 작성해보자!
입력
첫 번째 줄에 세 정수 $N$, $M$, $K$가 주어진다.
$i + 1$번째 줄에 문자열 $S_i = S_{i1} S_{i2} \cdots S_{iM}$이 주어진다. $(i, j)$ 칸에 장애물이 있으면 $S_{ij}=$#이고, $(i, j)$ 칸에 장애물이 없으면 $S_{ij}=$.이다. $(1 \le i \le N$; $1 \le j \le M)$
$N+2$번째 줄에 두 정수 $R_s$, $C_s$가 주어진다.
$N+3$번째 줄에 두 정수 $R_e$, $C_e$가 주어진다.
출력
문제의 정답을 $998\,244\,353$으로 나눈 나머지를 출력한다.
제한
- $1 \le N, M, K \le 100$
- $1 \le R_s, R_e \le N$
- $1 \le C_s, C_e \le M$
- $(R_s, C_s)$와 $(R_e, C_e)$에는 장애물이 없음
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $K = 1$ |
| 2 | 11 | $N, M, K \le 5$ |
| 3 | 35 | $N, M, K \le 30$ |
| 4 | 47 | 추가 제약 조건 없음 |
예제 입력 1
3 5 3 #.#.# .#.#. #.#.# 2 1 2 5
예제 출력 1
2
은재가 다음과 같은 두 가지의 방법으로 퀸을 움직일 수 있다.
예제 입력 2
8 8 3 #...#... #.#.#... .#...... ........ ....#... ..#..... ##...### #.....#. 4 5 2 6
예제 출력 2
75
실제로 은재가 백으로 둔 체스 경기 중 하나에서 따온 것이다. 경기 진행은 여기에서 볼 수 있다.
위 예제는 상대의 기권으로 경기가 끝났을 때의 보드 상태이다. 편의상 상대 퀸의 위치를 약점 칸으로 취급한다.
예제 입력 3
3 3 1 ### #.# ### 2 2 2 2
예제 출력 3
0
제자리에 두는 것은 불가능하므로 한 턴 후에 퀸이 $(2, 2)$에 있을 경우의 수는 $0$이다.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호