moutaintest
quoc14
c_cpp
a month ago
2.0 kB
3
Indexable
Never
caidat
#include <iostream> using namespace std; int n; int a[105][105]; struct point { int r, c; }; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int visit[105][105]; int min_h, max_h; bool inside(int x, int y) { if (x >= 1 && x <= n && y >= 1 && y <= n) { return true; } return false; } int x_next, y_next, ok; void dfs(int x, int y, int h, int min_h, int max_h) { if (ok == 1) { return; } if (x == n && y == n) { ok = 1; return; } for (int i = 0 ; i < 4; i++) { x_next = x + dx[i]; y_next = y + dy[i]; if (inside(x_next, y_next) && visit[x_next][y_next] == 0) { int min_tmp = 999999; int max_tmp = -1; if (a[x_next][y_next] > max_h) { max_tmp = a[x_next][y_next]; } else { max_tmp = max_h; } if (a[x_next][y_next] < min_h) { min_tmp = a[x_next][y_next]; } else { min_tmp = min_h; } if (max_tmp - min_tmp <= h) { visit[x][y] = 1; //cout << x_next << " " << y_next << " " << min_tmp << " " << max_tmp << endl; dfs(x_next, y_next, h, min_tmp, max_tmp); visit[x][y] = 0; } } } } bool checkk(int h) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { visit[i][j] = 0; } } ok = 0; visit[1][1] = 1; dfs(1, 1, h, a[1][1], a[1][1]); if (ok == 1) return true; return false; } void solve(int testcase) { cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cin >> a[i][j]; } } int lo = 0; int hi = 110; int ans = 0; while (lo < hi) { int mid = (lo + hi) / 2; if (checkk(mid) == true) { //cout << mid << endl; ans = mid; hi = mid - 1; } else { lo = mid + 1; } } cout << "#" << testcase << " " << ans << endl; } int main() { freopen("Text.txt", "r", stdin); int t; cin >> t; for (int i = 1; i <= t; i++) { solve(i); } return 0; }
Leave a Comment