Untitled
unknown
plain_text
a year ago
2.1 kB
7
Indexable
Never
package Mountain_Walking; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, res, hmin, hmax; static int[][] a, visit, value; static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 }; static int[] qx = new int[10000], qy = new int[10000]; static boolean checkOut(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= n) return false; return true; } static boolean BFS(int mid) { int L = hmin; while(L <= hmax-mid) { int R = L + mid; if (a[0][0] < L || a[0][0] > R){ L++; }else{ visit = new int[n][n]; visit[0][0] = 1; int front = 0, rear = 1; qx[front] = 0; qy[front] = 0; while (front < rear) { int xt = qx[front], yt = qy[front]; if(xt == n-1 && yt == n-1) return true; for(int i = 0; i < 4; i++){ int nx = xt + dx[i], ny = yt + dy[i]; if(checkOut(nx, ny) && visit[nx][ny] == 0 && a[nx][ny] >= L && a[nx][ny] <= R){ qx[rear] = nx; qy[rear] = ny; rear++; visit[nx][ny] = 1; } } front++; } L++; } } return false; } public static void main(String[] args) { try { System.setIn(new FileInputStream("input.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { n = scanner.nextInt(); a = new int[n][n]; visit = new int[n][n]; hmin = 110; hmax = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a[i][j] = scanner.nextInt(); hmin = Math.min(hmin, a[i][j]); hmax = Math.max(hmax, a[i][j]); } } int L = 0, R = hmax - hmin; while (L <= R) { int mid = (L + R) / 2; if (BFS(mid)) { res = mid; R = mid - 1; } else { L = mid + 1; } } System.out.println("#" + t + " " + res); } scanner.close(); } }