시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 474 | 111 | 90 | 25.210% |
야심한 밤, 잠입 전문가 최 상병은 적군의 비밀을 탈취하기 위해 적군의 기지로 침투하는 비밀 작전을 수행하고 있다.
적군의 기지는 $N$행과 $M$열의 칸으로 이루어진 $2$차원 그리드로 나타낼 수 있으며, 최 상병은 기지 입구인 $\left(1, 1\right)$에서 출발하여 목표 지점인 $\left(N, M\right)$으로 이동해야 한다. 최 상병은 매초 상하좌우로 한 칸 이동하거나 움직이지 않을 수 있다.
적군의 기지에는 잠입을 감지하는 레이저 센서들이 설치되어 있다. 각각의 센서는 행과 행 사이의 경계에만 설치되어 있으며, 왼쪽 또는 오른쪽으로 레이저를 발사하고 있다. 레이저는 벽이나 다른 레이저 센서에 닿기 전까지 계속 뻗어가며, 레이저 센서는 한 경계에 최대 $2$개까지만 설치되어 있다. 만약 발사된 레이저에 닿거나 센서를 밟아 최 상병이 감지된다면, 최 상병의 잠입이 발각되어 작전은 실패로 돌아간다.
게다가 최 상병이 기지 입구에서 출발한 후 1초가 지났을 때, 자율 방범 로봇이 기지 입구로 뒤따라 들어왔다. 자율 방범 로봇은 최 상병과 마찬가지로 매초 상하좌우로 한 칸 이동하거나 움직이지 않을 수 있다. 하지만 로봇은 최 상병과 달리 이동 중에 레이저 센서에 닿아도 아무런 일이 일어나지 않는다. 자율 방범 로봇과 최 상병이 같은 칸에 위치하면 최 상병의 잠입이 발각되어 작전은 실패로 돌아간다.
항상 최고로 안전한 잠입을 선호하는 최 상병은 자율 방범 로봇이 어떻게 움직이더라도 발각되지 않고 목표 지점으로 도달하는 경로를 찾고자 한다.
최 상병을 위해, 자율 방범 로봇이 어떻게 움직이더라도 발각되지 않고 목표지점인 $\left(N, M\right)$에 도착하는 것이 가능한지 알려주자.
첫 번째 줄에 적군의 기지의 행 크기과 열 크기를 나타내는 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(2\leq N\leq 100\,000;$ $2\leq M\leq 10^9)$
두 번째 줄부터 $N$번째 줄까지, $N-1$개의 경계에 대하여 $i$번째 행과 $i+1$번째 행 사이의 경계에 놓인 레이저 센서의 개수 $x_i$와, 이어서 $x_i$개의 $($레이저 센서의 열 위치 $c_{ij}$, 센서가 바라보는 방향 $d_{ij})$ 쌍이 공백으로 구분되어 주어진다. 이때 $d_{ij}$가 L
이면 센서가 왼쪽을, R
이면 센서가 오른쪽을 바라보고 있다는 뜻이다. $(0\leq x_i\leq 2;$ $1\leq c_{ij}\leq M;$ $c_{ij} < c_{i(j+1)})$
각 레이저 센서는 벽이나 다른 레이저 센서에 닿기 전까지, 열 위치를 포함한 바라보는 방향의 열을 모두 감지할 수 있도록 배치되어 있다. 동일한 위치에 서로 다른 레이저 센서가 설치되어 있는 입력은 주어지지 않는다.
최 상병이 자율 방범 로봇과 레이저 센서에 발각되지 않고 $\left(N, M\right)$에 도달하는 경로가 존재하면 YES
, 존재하지 않으면 NO
를 출력한다.
10 8 0 2 1 R 3 L 1 5 R 1 4 L 0 2 5 R 7 L 0 0 1 7 L
YES
입력의 $2$차원 그리드는 다음과 같다.
8 8 2 1 R 4 L 2 2 L 6 R 0 2 3 L 5 L 2 7 R 8 R 1 7 R 1 8 L
NO
Contest > 보라매컵 > 제1회 보라매컵 예선 D번