import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; import java.lang.Math; class point { int index=-2; point parent; int distance; int distance_to; int cap; ArrayList list = new ArrayList(); } class PriorityQueue{ int count; point[] heap; PriorityQueue(int n){ int i; this.heap = new point[n]; for(i = 0; i < n; i++){ this.heap[i] = new point(); } this.count = 0; } public void insert(point u){ int i = this.count++; point temp; this.heap[i] = u; while (i > 0 && this.heap[(i-1)/2].distance > this.heap[i].distance){ temp = this.heap[(i-1)/2]; this.heap[(i-1)/2] = this.heap[i]; this.heap[i] = temp; this.heap[i].index=i; i = (i-1)/2; } this.heap[i].index=i; } public point ExtractMin(){ point temp; temp = this.heap[0]; this.count--; if(this.count > 0){ this.heap[0] = this.heap[this.count]; this.heap[0].index=0; heapify(this.heap, 0); } return temp; } public void heapify(point[] heap, int i){ int l, r, j; point temp; for(;;){ l = 2*i+1; r = l+1; j = i; if(l < this.count && (heap[l].distance < heap[j].distance)) j = l; if(r < this.count && (heap[r].distance < heap[j].distance)) j = r; if(i == j) break; temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; this.heap[i].index=i; this.heap[j].index=j; i = j; } } public void increaseKey(point x, int y){ int i = x.index; point temp; x.distance=y; while(i > 0 && this.heap[(i-1)/2].distance > y){ temp = this.heap[(i-1)/2]; this.heap[(i-1)/2] = this.heap[i]; this.heap[i] = temp; this.heap[i].index=i; i = (i-1)/2; } x.index=i; } } public class MapRoute { public static void main(String[] arg) { Scanner sc = new Scanner(System.in); int i=0,j=0,n=sc.nextInt(),distance=0,k=0; point [][] graph=new point[n][n]; int[][] matrix=new int[n][n]; for(i=0;i 0) { graph[i][j].list.add(graph[i - 1][j]); graph[i][j].cap++; } if (i < n - 1) { graph[i][j].list.add(graph[i + 1][j]); graph[i][j].cap++; } if (j > 0) { graph[i][j].list.add(graph[i][j - 1]); graph[i][j].cap++; } if (j < n - 1) { graph[i][j].list.add(graph[i][j + 1]); graph[i][j].cap++; } } } PriorityQueue q = new PriorityQueue(n*n); graph[0][0].distance=graph[0][0].distance_to; q.insert(graph[0][0]); point v=new point(); point u=new point(); point answer=new point(); while(q.count>0) { v=q.ExtractMin(); if(v.equals(graph[n-1][n-1])) { answer = v; break; } for(i=0;i