4485
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
#include <stdio.h>
#include <limits.h>
#define min(a, b) (((a)>(b)) ? (b):(a))
int cave[126][126];
int al[126][126];
int visit[126][126];
int main(void) {
int N;
int t=1;
int first=1;
while(1){
scanf("%d", &N);
if(N==0)
break;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
scanf("%d", &cave[i][j]);
//initial al
al[i][j] = INT_MAX;
visit[i][j] = 0;
}
}
//calc
al[0][0] = cave[0][0];
al[0][1] = al[0][0] + cave[0][1];
al[1][0] = al[0][0] + cave[1][0];
visit[0][0] = 1;
while(1){
int x=-1;
int y=-1;
int minimal=INT_MAX;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(visit[i][j]==0 && al[i][j]<minimal){
x=i;
y=j;
minimal = al[i][j];
}
}
}
if(x==-1 || y==-1) break;
visit[x][y] = 1;
if(y-1>=0){
al[x][y-1] = min(al[x][y]+cave[x][y-1], al[x][y-1]);
if(al[x][y]+cave[x][y-1] < al[x][y-1] && visit[x][y-1]==1)
visit[x][y-1] = 0;
}
if(y+1<N){
al[x][y+1] = min(al[x][y]+cave[x][y+1], al[x][y+1]);
if(al[x][y]+cave[x][y+1] < al[x][y+1] && visit[x][y+1]==1)
visit[x][y+1] = 0;
}
if(x-1>=0){
al[x-1][y] = min(al[x][y]+cave[x-1][y], al[x-1][y]);
if(al[x][y]+cave[x-1][y] < al[x-1][y] && visit[x-1][y]==1)
visit[x-1][y] = 0;
}
if(x+1<N){
al[x+1][y] = min(al[x][y]+cave[x+1][y], al[x+1][y]);
if(al[x][y]+cave[x+1][y] < al[x+1][y] && visit[x+1][y]==1)
visit[x+1][y] = 0;
}
}
if(!first){
printf("\n");
}
first=0;
printf("Problem %d: %d", t, al[N-1][N-1]);
t++;
}//E: while
return 0;
}
C
INFO