Cross Country Skiing

import java.io.*;
import java.util.*;
 
public class CrossCountrySkiing {
	static int n, m;
	static int startI, startJ;     // Guarda la posición inicial de cada flood fill
	static int[][] course;         // Guarda las alturas del circuito de esquí
	static boolean[][] waypoints;  // Guardados como booleanos en vez de 1s y 0s
	static boolean[][] vis;        // Arreglo de visitados para flood fill
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("ccski");
 
		n = io.nextInt();
		m = io.nextInt();
 
		int minHeight = Integer.MAX_VALUE;
		int maxHeight = Integer.MIN_VALUE;
 
		course = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				course[i][j] = io.nextInt();
				minHeight = Math.min(minHeight, course[i][j]);
				maxHeight = Math.max(maxHeight, course[i][j]);
			}
		}
 
		waypoints = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (io.nextInt() == 1) {
					waypoints[i][j] = true;
 
					// Guardamos uno de los waypoints como posición inicial
					startI = i;
					startJ = j;
				} else {
					waypoints[i][j] = false;
				}
			}
		}
 
		// Búsqueda binaria del menor valor posible de d que funciona
		// Podemos fijar "hi" a maxHeight - minHeight porque ese será el
		// valor máximo de d que necesitamos probar
		int lo = 0;
		int hi = maxHeight - minHeight;
		int minD = -1;
		while (lo <= hi) {
			int d = (lo + hi) / 2;
			if (reachable(d)) {
				minD = d;
				hi = d - 1;
			} else {
				lo = d + 1;
			}
		}
 
		io.println(minD);
		io.close();
	}
 
	// i y j guardan la posición actual
	// d guarda el valor actual de d
	// prevHeight guarda la altura de la celda anterior
	static void floodfill(int i, int j, int d, int prevHeight) {
		// Comprobamos si estamos fuera de los límites
		if (i < 0 || i >= n || j < 0 || j >= m) { return; }
		// Comprobamos si la posición actual ya fue visitada
		if (vis[i][j]) { return; }
		// Comprobamos si se puede visitar la posición actual desde la anterior
		if (Math.abs(course[i][j] - prevHeight) > d) { return; }
 
		// Marcamos la posición como visitada si pasan todas las comprobaciones
		vis[i][j] = true;
 
		// Visitamos cada celda adyacente
		floodfill(i + 1, j, d, course[i][j]);
		floodfill(i - 1, j, d, course[i][j]);
		floodfill(i, j + 1, d, course[i][j]);
		floodfill(i, j - 1, d, course[i][j]);
	}
 
	static boolean reachable(int d) {
		// Reiniciamos el arreglo de visitados y empezamos flood fill (DFS) desde el inicio
		vis = new boolean[n][m];
		floodfill(startI, startJ, d, course[startI][startJ]);
 
		// Revisamos cada celda: si es un waypoint y no fue visitado,
		// sabemos que no todos los waypoints son alcanzables entre sí
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (waypoints[i][j] && !vis[i][j]) { return false; }
			}
		}
 
		return true;
	}
 
	// CodeSnip{Kattio}
}

#include <bits/stdc++.h>
using namespace std;
 
 
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, -1, 0, 1};
constexpr int MAX_N = 500;
 
int m, n;
int wy, wx;
 
vector<vector<int>> grid(MAX_N, vector<int>(MAX_N));
vector<vector<bool>> wp(MAX_N, vector<bool>(MAX_N));
vector<vector<bool>> mark(MAX_N, vector<bool>(MAX_N));
 
/** Flood fill de todos los nodos alcanzables dado un valor de D */
void floodfill(int d) {
	queue<pair<int, int>> q;
 
	q.push(make_pair(wy, wx));
	mark[wy][wx] = 1;
 
	while (!q.empty()) {
		pair<int, int> p = q.front();
		q.pop();
 
		for (int i = 0; i < 4; i++) {
			int ny = p.first + dy[i];
			int nx = p.second + dx[i];
			if (ny >= 0 && ny < m && nx >= 0 && nx < n) {
				/*
				 * si la celda destino no fue visitada antes
				 * y la diferencia de elevación está dentro de D
				 * metemos la celda en la cola
				 */
				if (!mark[ny][nx] && abs(grid[p.first][p.second] - grid[ny][nx]) <= d) {
					q.push(make_pair(ny, nx));
					mark[ny][nx] = true;
				}
			}
		}
	}
}
 
/** Comprueba si todos los waypoints son alcanzables con el D dado */
bool reachable(int d) {
	// reiniciamos la grilla que guarda los puntos alcanzables
	mark = vector<vector<bool>>(m, vector<bool>(n));
 
	floodfill(d);
 
	// comprobamos si hay algún waypoint inalcanzable
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (wp[i][j] && !mark[i][j]) { return false; }
		}
	}
	return true;
}
 
int main() {
	freopen("ccski.in", "r", stdin);
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) { cin >> grid[i][j]; }
	}
 
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			int is_waypoint;
			cin >> is_waypoint;
			wp[i][j] = is_waypoint != 0;
			// guardamos uno de los waypoints como punto de partida
			if (wp[i][j]) {
				wy = i;
				wx = j;
			}
		}
	}
 
	// búsqueda binaria de la diferencia de elevación
	int l = 0;
	int r = INT32_MAX;
	while (l < r) {
		int d = (l + r) / 2;
		if (reachable(d)) {
			r = d;
		} else {
			l = d + 1;
		}
	}
 
	freopen("ccski.out", "w", stdout);
	cout << l << endl;
}