Problemas
세영이가 미로 탈출 로봇 대회에 참가하였다.
미로는 NxN 크기의 격자로 된 판 위에 장애물이 있고 미로는 로봇이 밖으로 나가지 못하게 벽으로 둘러 쌓여있다.
이 대회는 좀 특이하게 미로를 빠져 나가는 것이 아니라 가장 먼 거리를 찾아 가는 로봇이 우승을 하게 된다.
대회의 규칙은 다음과 같다.
- 로봇은 상, 하, 좌, 우 아무방향이나 움직일 수 있으나. 한번 지나간 길을 다시 갈 수 없으며, 장애물이나 벽 앞에서만 방향을 바꿀 수 있다.
- 거리는 로봇이 1칸을 이동하는 것을 1로 한다.
- 로봇의 시작 위치는 항상 왼쪽 아래(△)다.
다음은 6x6 크기의 미로에 4개의 장애물이 있는 예이다.
위 예제의 각 거리는 그림 1은 20, 그림 2는 18, 그림 3은 22, 그림 4는 26으로 그림 4번이 가장 먼 거리가 된다.
우승을 하려면 세영이의 로봇이 얼마나 먼 거리를 가야 하는지 구하여 보자.
Entrada
입력의 첫 줄에는 미로의 크기 N(3≤N≤19)과 장애물의 개수 M(0≤M≤100)이 들어온다.
다음 줄부터 M개의 줄에 장애물의 위치를 나타내는 행, 열이 공백으로 구분하여 들어온다.
Salida
출력의 첫줄에 가장 먼 거리를 출력한다.
Ejemplo
6 4
1 1
2 5
4 3
6 4
26
Fuente
pai2
Debes iniciar sesión para escribir código.