생일선물사기(젖소 심마니) timer 1초 memory 32MB

오늘은 은비의 생일이어서 초대를 받은 서연이는 약속장소로 가려고 한다. 

아직 생일선물을 준비하지 못한 서연이는 은비가 좋아하는 ‘시테니깡’ 사탕을 사가지고 가려 한다. 

가능한 빨리 약속장소로 가고 싶은 서연이는 스마트폰 앱을 이용하여 '시테니깡' 사탕을 파는 상점을 검색하였다. 

서연이와 은비가 사는 도시는 평면 격자구조로 되어있으며 한 위치에서 상하좌우로만 이동할 수 있다. 

한 칸 이동할 때 1의 시간이 걸린다.

서연이는 '시테니깡'사탕을 사지 않은 상태에서 은비가 있는 장소를 통과할 수 없음에 유의하라.

앱에 표시된 정보를 이용하여 서현이가 ’시테니깡‘ 사탕을 산 후 약속장소로 이동하는 최단시간을 구하는 프로그램을 작성하시오.

앱에 표시된 정보는 다음과 같다.

0 : 서연이가 이동할 수 있는 곳 1 : 서연이가 이동할 수 없는 곳 2 : 서연이의 현재 위치 3 : 은비와 약속장소 4 : ‘시테니깡’ 사탕을 파는 상점으로 여러 곳이 있을 수 있다.