4485

Run Settings
LanguageC
Language Version
Run Command
#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; }
Editor Settings
Theme
Key bindings
Full width
Lines