package question;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Question778 {
 public int swimInWater(int[][] grid) {
 int n = grid.length;
 Queue<Entity> queue = new PriorityQueue<>((e1, e2) -> e1.weight - e2.weight);
 for (int i = 0; i < n; i++) {
 for (int j = 0; j < n; j++) {
 if (i + 1 < n)
 queue.offer(new Entity(Math.max(grid[i][j], grid[i + 1][j]), i*n+j, i*n+n+j));
 if (j + 1 < n)
 queue.offer(new Entity(Math.max(grid[i][j], grid[i][j + 1]), i*n+j, i*n+j+1));
 }
 }
 UnionFind unionFind = new UnionFind(n * n);
 int res = 0;
 while (unionFind.find(n*n-1)!=0) {
 Entity entity = queue.poll();
 res = Math.max(res, entity.weight);
 unionFind.merge(entity.x, entity.y);
 }
 return res;
 }

 private class Entity {
 int weight;
 int x, y;

 public Entity(int weight, int x, int y) {
 this.weight = weight;
 this.x = x;
 this.y = y;
 }
 }

 private class UnionFind {
 int[] p;

 public UnionFind(int n) {
 this.p = new int[n];
 for (int i = 0; i < p.length; i++) {
 p[i] = i;
 }
 }

 public int find(int x) {
 if (x == p[x]) return x;
 p[x] = find(p[x]);
 return p[x];
 }

 public boolean merge(int x, int y) {
 x = find(x);
 y = find(y);
 if (x == y) return true;
 if (x < y) p[y] = x;
 else p[x] = y;
 return false;
 }
 }

 public int swimInWater2(int[][] heights) {
 int n = heights.length;
 int m = heights[0].length;
 int[][] f = new int[n][m];
 for (int[] ints : f) {
 Arrays.fill(ints, Integer.MAX_VALUE);
 }
 f[0][0] = 0;
 Queue<Integer> queue = new LinkedList<>();
 queue.add(0);
 while (!queue.isEmpty()) {
 Integer poll = queue.poll();
 int x = poll / m;
 int y = poll % m;
 for (int[] ints : step) {
 int fx = x + ints[0];
 int fy = y + ints[1];
 if (fx < 0 || fx >= n || fy < 0 || fy >= m) continue;
 int t = Math.max(f[x][y], Math.max(heights[fx][fy], heights[x][y]));
 if (t >= f[fx][fy]) continue;
 f[fx][fy] = t;
 queue.offer(fx * m + fy);
 }
 }
 return f[n - 1][m - 1];
 }

 private static int[][] step = new int[][]{
 {0, 1}, {0, -1}, {1, 0}, {-1, 0}
 };
}