import LeetCode.MonthlyChallenges_21.Sept21.ImageOverlap;

import java.util.*;
import java.util.Arrays;

public class Main {


    int minimumDistance = Integer.MIN_VALUE;

    int rowNbr[]
            = new int[]{-1, 0, 1, 0};
    int colNbr[]
            = new int[]{0, -1, 0, 1};
    HashSet<String> monsterArea;
    HashMap<String, TreeSet<Integer>> map;
    HashMap<String, Integer> dp;

    int findbestpath(int n, int m, int sr, int sc, int er, int ec, List<Integer> mr, List<Integer> mc) {
        map = new HashMap<>();
        monsterArea = new HashSet<>();
        dp = new HashMap<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < mr.size(); k++) {
                    int mcr = mr.get(k);
                    int mcc = mc.get(k);
                    monsterArea.add(mcr + "-" + mcc);
                    if (mcr == i && mcc == j) {
                        continue;
                    }
                    String str = i + "-" + j;
                    int distance = Math.abs(i - mcr) + Math.abs(mcc - j);
                    map.putIfAbsent(str, new TreeSet<>());
                    map.get(str).add(distance);

                }
            }
        }

        return dfs(n, m, sr, sc, mr, mc, er, ec, new HashSet<String>());
    }

    private int dfs(int n, int m, int sr, int sc, List<Integer> mr, List<Integer> mc, int er, int ec, HashSet<String> visited) {
        String key = sr + "-" + sc;
        visited.add(key);
        if (dp.containsKey(key)) {
            return dp.get(key);
        }

        if (sr == er && sc == ec) {

            return map.get(key).first();
        }

        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < rowNbr.length; i++) {
            int nextRow = sr + rowNbr[i];
            int nextCol = sc + colNbr[i];
            String str = nextRow + "-" + nextCol;
            if (!visited.contains(str) && isValid(nextRow, nextCol, n, m) && !monsterArea.contains(str)) {
                int value = Math.min(dfs(n, m, nextRow, nextCol, mr, mc, er, ec, visited), map.get(key).first());
                ans = Math.max(ans, value);
            }


        }
        visited.remove(key);
        // dp.put(key, ans);
        return ans;
    }

    private boolean isValid(int nextRow, int nextCol, int n, int m) {
        return nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < m;
    }

    public static void main(String[] args) {
        System.out.println(new Main().findbestpath(5, 3, 1, 1, 4, 2, Arrays.asList(0, 2), Arrays.asList(2, 2)));
    }
}