import java util ArrayList import java util Arrays import java util Sc

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.lang.Math;
class point {
int index=-2;
int key;
point parent;
int distance;
int cap;
ArrayList<point> list = new ArrayList<point>();
}
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].key > this.heap[i].key){
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].key < heap[j].key)) j = l;
if(r < this.count && (heap[r].key < heap[j].key)) 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.key=y;
while(i > 0 && this.heap[(i-1)/2].key > 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 Factorial {
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<n;i++)
{
for(j=0;j<n;j++)
{
matrix[i][j]=sc.nextInt();
graph[i][j]=new point();
}
}
for(i=0;i<n;i++) {
for (j = 0; j < n; j++) {
graph[i][j].parent = null;
graph[i][j].distance = -1000;
graph[i][j].distance_to = matrix[i][j];
if (i > 0) {
graph[i][j].list.add(graph[i - 1][j]);
}
if (i < n - 1) {
graph[i][j].list.add(graph[i + 1][j]);
}
if (j > 0) {
graph[i][j].list.add(graph[i][j - 1])
}
if (j < n - 1) {
graph[i][j].list.add(graph[i][j + 1])
}
}
}
PriorityQueue q = new PriorityQueue(n*n);
q.insert(graph[0][0]);
}
}