Untitled
unknown
plain_text
6 months ago
2.6 kB
1
Indexable
Never
import java.util.Scanner; public class OptimizedMountainWalking { static int n; static int[][] mountain = new int[100][100]; static int front, rear; static boolean[][] visited = new boolean[100][100]; static int[] dx = {0, -1, 0, 1}; static int[] dy = {-1, 0, 1, 0}; static int[] queueX = new int[1000000]; static int[] queueY = new int[1000000]; public static void walk(int x, int y, int start, int end) { if (mountain[x][y] < start || mountain[x][y] > end) return; front = rear = 0; queueX[rear] = x; queueY[rear] = y; rear++; while (front < rear) { int xx = queueX[front]; int yy = queueY[front]; front++; for (int i = 0; i < 4; i++) { int _x = xx + dx[i]; int _y = yy + dy[i]; if (_x >= 0 && _x < n && _y >= 0 && _y < n) { if (!visited[_x][_y]) { if (mountain[_x][_y] >= start && mountain[_x][_y] <= end) { visited[_x][_y] = true; queueX[rear] = _x; queueY[rear] = _y; rear++; } } } } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int test_case; int T; T = sc.nextInt(); for (test_case = 1; test_case <= T; ++test_case) { n = sc.nextInt(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { mountain[i][j] = sc.nextInt(); } } int left = 0, right = 111; while (left < right) { int mid = (left + right) / 2; boolean check = false; for (int i = 0; i <= 110; i++) { for (int k = 0; k < n; k++) { for (int j = 0; j < n; j++) { visited[k][j] = false; } } visited[0][0] = true; walk(0, 0, i, i + mid); if (visited[n - 1][n - 1]) { check = true; break; } } if (check) right = mid; else left = mid + 1; } System.out.println("#" + test_case + " " + left); } } }