사장님 달려가고 있습니다
면접 대비시간 제한1초메모리 제한1024 MB
칸마다 통제 시작 시각이 있는 N x N 격자에서, 같은 방향으로 계속 달리면 매초 한 칸씩 가속하는 규칙 아래 오른쪽 아래 칸에 도착하는 최소 시간을 구한다.
문제
알바 첫날인 정훈이는 늦잠을 잤다. 다행히도 정훈이는 달리기가 정말 빨라서 괜찮다고 생각했지만, 오늘은 공사로 인해 길을 통제하는 중이었다. 첫날부터 늦을 수 없는 정훈이는 가장 빠른 경로를 생각하며 달린다.
- 공사 지도 N x N가 있다.
- 정훈이는 0초에 맨 왼쪽 위(1, 1)에서 출발하고 맨 오른쪽 아래(N, N)에 도착해야 한다.
- 달리는 방향은 상,하,좌,우로 달릴 수 있다.
- 매초 1칸을 갈 수 있고 전과 같은 방향으로 달린다면 가속도가 붙어 1초 안에 전보다 1칸을 더 갈 수 있다. (전에 오른쪽으로 1칸을 갔다면 오른쪽으로 2칸을 1초에 갈 수 있다.)
- 가속도를 주체할 수 없으므로 방향전환을 해야만 다시 1초에 1칸을 갈 수 있다.
- 정훈이는 현재 위치에서 달려갈 때 1초 후 지도 밖에 서 있다면 갈 수 없다고 판단한다.
공사로 인해 통제하는 구역은 N x N 지도에 통제 시작시각이 초 단위로 주어지며 통제를 시작하기 전까지만 그 구역을 들어갈 수 있다. 통제 시작시각과 그 구역에 도착시각이 같은 시간일 경우에는 구역에 들어갈 수 없다.
입력
정수 N (1 ≤ N ≤ 100)이 주어진다.
둘째 줄부터 N개의 줄에 공사 지도의 정보가 주어진다. 지도에는 각 구역 통제 시작 시각 X (0 ≤ X ≤ 100)이 정수로 주어진다. X가 0이라면 통제를 하지 않는다.
출력
정훈이가 (N, N)에 도착할 수 있는 최소 시간을 출력한다.
(N, N)에 도착할 수 없다면 "Fired"를 출력한다.