레이팅 미적용농부 존의 부엌에서 과일을 너무 많이 먹은 소 베시는 아주 이상한 꿈을 꾸고 있다! 가장 최근 꿈에서 베시는 \(N \times M\) 격자 타일 모양의 미로(\(1 \le N, M \le 1,000\))에 갇혀 있다. 베시는 왼쪽 위 타일에서 출발하여 오른쪽 아래 타일에 도착하고 싶다. 어떤 타일 위에 서 있을 때, 베시는 동서남북 네 방향의 인접한 타일로 이동할 수 있다.
그런데 잠깐! 각 타일에는 색이 있고, 색마다 다른 성질이 있다! 생각만 해도 베시는 머리가 아프다.
- 타일이 빨간색이면 지나갈 수 없다.
- 타일이 분홍색이면 평범하게 걸어갈 수 있다.
- 타일이 주황색이면 평범하게 걸어갈 수 있지만, 베시에게서 오렌지 냄새가 나게 된다.
- 타일이 파란색이면 피라냐가 있어서 베시에게서 오렌지 냄새가 날 때에만 통과시켜 준다.
- 타일이 보라색이면 베시는 그 방향의 다음 타일로 미끄러진다(그 타일을 지나갈 수 없는 경우는 제외). 다음 타일도 보라색이면, 베시는 보라색이 아닌 타일에 도착하거나 지나갈 수 없는 타일에 부딪힐 때까지 계속 미끄러진다. 타일을 미끄러져 지나가는 것도 한 번의 이동으로 센다. 보라색 타일은 베시의 냄새도 없애 버린다.
(보라색 타일이 헷갈린다면, 예제가 그 사용법을 보여 줄 것이다.)
베시가 왼쪽 위에서 오른쪽 아래까지 최소한의 이동 횟수로 갈 수 있도록 도와주자.
Problem credits: Nathan Pinsker, inspired by the game "Undertale"
Problem credits: Nathan Pinsker, inspired by the game "Undertale".
첫째 줄에 미로의 행과 열의 수를 나타내는 두 정수 \(N\)과 \(M\)이 주어진다.
다음 \(N\)개의 줄에는 각각 \(M\)개의 정수가 주어지며, 미로를 나타낸다:
- 정수 '0'은 빨간색 타일
- 정수 '1'은 분홍색 타일
- 정수 '2'는 주황색 타일
- 정수 '3'은 파란색 타일
- 정수 '4'는 보라색 타일
왼쪽 위와 오른쪽 아래의 정수는 항상 '1'이다.
베시가 미로를 건너는 데 필요한 최소 이동 횟수를 하나의 정수로 출력한다. 불가능하면 -1을 출력한다.
dream.in · 출력을 쓸 파일 dream.out4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 110In this example, Bessie walks one square down and two squares to the right (and
then slides one more square to the right). She walks one square up, one square
left, and one square down (sliding two more squares down) and finishes by
walking one more square right. This is a total of 10 moves (DRRRULDDDR).
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > December > Gold