MTWALK - Mountain Walking
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 105
int vst[N][N], a[N][N], n, mn, mx;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
bool dfs(int u, int v) {
//printf( "%d %d %d %d %d\n", u, v, min, max, lim );
vst[u][v] = 1; if( u == n - 1 && v == n-1 ) return 1;
for(int i = 0; i < 4; ++i) {
int x = u + dx[i], y = v + dy[i];
if( x >= 0 && y >= 0 && x < n && y < n && !vst[x][y] && a[x][y] >= mn && a[x][y] <= mx )
if(dfs(x,y)) return 1;
}
return 0;
}
int main() {
// freopen("input.txt", "r", stdin);
scanf( "%d", &n );
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d",&a[i][j]);
int res = (int) 1e9;
for(mn = 0; mn <= a[0][0]; ++mn) {
int L = 0, H = 120;
while( L <= H ) {
int mid = (L+H)>>1;
mx = mn+mid;
memset(vst, 0, sizeof vst);
bool ok = dfs(0,0);
//printf( "%d %d %d\n", mn, mx, ok );
if( L == H ) {
if( !ok ) L = 1000000000;
break;
}
if(ok) H = mid;
else L = mid + 1;
}
res = min(res, L);
}
printf( "%d\n", res );
return 0;
}