포탈은 1인칭 퍼즐 게임으로, 이 게임의 주인공은 벽에 두 개의 포탈을 만들어서, 한쪽 포탈에 들어가면 반대쪽 포탈로 나올 수 있다.

이 문제는 비슷한 아이디어에서 출발한다. (R, C) 크기의 격자판이 있다.

당신은 이 격자판 어딘가에 위치해 있고, 또 다른 위치에는 맛있는 케이크가 놓여져 있다.

당신은 매우 배가 고프기 때문에 최대한 빨리 이 케이크를 먹고 싶어한다.

당신은 현재 위치에서 동서남북 네 방향으로 이동할 수 있으며, 당신에게는 포탈총이 있어 포탈을 만들어서 이동할 수도 있다. 당신은 포탈총을 이용하여 두 가지 포탈 (노란색, 파란색)을 만들 수 있으며, 무조건 직진하는 성질을 가지고 있다.

또한 케이크가 있더라도 그대로 투과하는 성질을 가지고 있다. 다만 포탈총은 동서남북 네 방향으로만 발사할 수 있다. 노란색과 파란색 포탈을 만들었다면, 당신은 이 포탈을 통해 이동할 수 있다.

노란색 포탈로 들어갔다면 파란색 포탈로 나오게 되며, 그 반대의 경우도 성립한다.

당신은 포탈총을 사용함으로써 더 빨리 케이크를 먹을 수 있게 될 수 있을 것이다!

아래의 그림을 살펴보자.

회색 칸은 벽을 나타내고 흰색 칸은 아무것도 없는 빈 공간을 나타낸다. 또한 빨간색 점은 당신의 위치이다.

오른쪽을 향해 파란색 포탈 건을 발사하면 위의 그림과 같이 파란색 포탈이 생긴다.

아래쪽을 향해 노란색 포탈 건을 발사한 후의 상태이다.

남쪽으로 한번 이동하였다.

한번 더 남쪽으로 이동하였다. 아래쪽의 노란색 포탈을 통해 파란색 포탈로 순간이동하게 되었다.

똑같은 색깔의 포탈은 최대 1개만 존재한다.

현재 위치에서 파란색 포탈을 왼쪽으로 쏘면 위의 그림과 같이 된다.

포탈은 무조건 벽에만 만들 수 있으며, 포탈이 없는 벽으로는 이동할 수 없다.

포탈 건을 사용하는 것은 이동횟수로 세지 않는다고 가정한다.

케이크를 먹을 수 있는 최소 이동횟수를 구하시오.

포탈1 timer 1s memory 64MB

포탈1 1s 64MB