問題
최근 북한에서는 대북방송을 듣고 남쪽으로 귀순하는 병사들이 생길 것을 우려하여 비무장지대에 대인지뢰를 매설하고 있다.
국방부에서는 지뢰를 제거하는 로봇을 투입하여 지뢰매설 정보가 입수되는 대로 로봇이 이동하여 지뢰를 제거하도록 하였다.
로봇 하나가 담당하는 크기는 가로와 세로가 각각 N개인 정사각형 형태로 되어 있어서
각각의 위치는 (1. 1)부터 (N, N)까지 좌표형태로 나타낼 수 있다.
그런데 어떤 위치에는 나무나 바위와 같은 장애물이 있어서 로봇이 이동할 수 없다.
로봇은 앞으로 전진하거나 한번에 90도를 회전할 수 있다.
앞으로 전진하는 것은 전혀 어려움이 없지만 회전하는 데에는 상당한 부담이 되기 때문에 가능한 회전을 적게 하는 것이 좋다.
지뢰의 매설위치가 확인되는 대로 로봇에게 제거를 지시하면 로봇은 지시받은 순서대로 지뢰의 위치로 이동하여 제거하여야 한다.
로봇이 모든 지뢰를 제거하는데 필요한 최소의 회전횟수를 출력하는 프로그램을 작성하라.
入力
첫째 줄에 로봇이 처리해야 하는 비무장지대의 한변의 길이 N과 지뢰의 개수 M이 입력된다. N(2 <= N, M <= 100)
다음 줄에는 3 개의 정수 sr, sc, sd가 입력되는데 현재 로봇의 좌표와 방향을 나타낸다. (1 <= sr, sc <= N, 1 <= sd <= 4)
sr는 위에서 아래로 행 번호를 나타내며, sc은 왼쪽에서 오른쪽으로 열 번호를 나타낸다.
sd가 1 이면 동쪽(오른쪽), 2 면 서쪽(왼쪽), 3 이면 남쪽(아래), 4 이면 북쪽(위)를 나타낸다.
둘째 줄부터 N줄에 걸쳐 각 좌표의 상태를 나타내는 0 과 1 로 이루어진 N개의 숫자가 입력되는데 0 은 이동이 가능한 곳이고 1 은 장애물이 있는 곳이다.
다음줄부터 M개의 줄에 걸쳐 제거해야 하는 지뢰의 좌표가 입력된다. 좌표의 크기는 1 이상 N 이하이다.
出力
제거해야 하는 지뢰를 입력되는 순서대로 제거하기 위한 로봇의 최소회전 횟수를 출력한다.
例題
6 3
2 2 1
0 0 1 0 0 1
0 0 0 0 0 0
1 0 0 1 0 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
3 3
6 5
2 3
4
ログインしないとコードを書けません。