레이팅 미적용베시와 친구들은 새로운 게임을 발명했다. 게임 이름은 정확하긴 하지만 그다지 창의적이지는 않다. 소들은 이 게임을 "헛간에서 상자를 밀어 올바른 자리에 넣되 건초는 건드리지 않기" 게임이라고 부른다 (이게 과하다고 생각한다면, 소들이 코드를 짤 때 쓰는 변수 이름들을 봐야 한다...).
헛간은 \(N \times M\) 직사각형 격자로 모델링할 수 있다. 일부 격자 칸에는 건초가 있다. 베시는 이 격자의 한 칸을 차지하고 있고, 큰 나무 상자가 다른 한 칸을 차지하고 있다. 베시와 상자는 동시에 같은 칸에 있을 수 없으며, 둘 다 건초가 있는 칸에는 들어갈 수 없다.
베시는 건초 속으로 걸어 들어가지 않는 한 4개의 직교 방향 (북, 동, 남, 서)으로 이동할 수 있다. 베시가 상자가 있는 칸으로 걸어가려 하면, 상자 반대편에 빈 칸이 있는 경우에 한해 상자가 그 방향으로 한 칸 밀려난다. 빈 칸이 없으면 베시는 그 이동을 할 수 없다.
특정 격자 칸이 목표 지점으로 지정되어 있다. 베시의 목표는 상자를 그 위치로 옮기는 것이다.
상자와 소의 시작 위치, 상자의 목표 위치를 포함한 헛간의 배치가 주어질 때, 게임에서 이길 수 있는지 판별하라.
참고: 이 문제는 기본 제한인 256MB보다 큰 512MB의 메모리 사용을 허용한다.
Problem credits: Nathan Pinsker
Problem credits: Nathan Pinsker
첫째 줄에 세 수 \(N\), \(M\), \(Q\)가 주어지는데, \(N\)은 격자의 행 수이고 \(M\)은 열 수이다.
- \(1 \le N,M \le 1500\).
- \(1 \le Q \le 50,000\).
다음 \(N\)개의 줄에 격자의 모습이 주어지는데, 각 문자는 빈 칸 (.), 건초 (#), 베시의 시작 위치 (A), 상자의 초기 위치 (B)를 나타낸다.
이어서 \(Q\)개의 줄에 각각 정수 쌍 \((R, C)\)가 주어진다. 각 쌍에 대해, 헛간의 초기 상태에서 시작하여 상자를 \(R\)행 \(C\)열의 칸으로 옮길 수 있는지 판별해야 한다. 가장 위쪽 행이 1행이고, 가장 왼쪽 열이 1열이다.
\(Q\)개의 줄에 각각 문자열 "YES" 또는 "NO"를 출력한다.
pushabox.in · 출력을 쓸 파일 pushabox.out5 5 4
##.##
##.##
A.B..
##.##
##.##
3 2
3 5
1 3
5 3NO
YES
NO
NOTo push the box to the position (3, 5), the cow just needs to move 3 spaces to
the right.
None of the other three positions are attainable.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > December > Platinum