package com.company;

import java.util.*;

public class DijkstraOnSteroids {

    public static void main(String[] args) {
        int n = 2;
        int m = 3;
        int[][] graph = {{3, 5, 6}, {4, 2, 1}};
        System.out.println(Solution.solve(n, m, graph));
    }
}

class Solution {

    public static int solve(int n, int m, int[][] graph) {
        /*
        //
        // Come up with an iterative dynamic programming solution to the ladder problem.
        // TODO mem[0] = ...; // Base case
        // TODO mem[i] = ...;
        */

        int[][] mem = new int[n][m];
        TreeSet<Integer> changedLast = new TreeSet<>();
        TreeSet<Integer> changedCurrent = new TreeSet<>();
        mem[0][0] = 0;
        int maxLadder = 0;
        int nodes = n * m;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                mem[i][j] = Integer.MAX_VALUE;
                changedLast.add(i * m + j);
            }
        }
        for (int i = 1; i <= nodes - 1; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (changedLast.contains(j * m + k)) {
                        if (j != 0) {
                            int ladderCost = graph[j - 1][k] - graph[j][k];
                            if (ladderCost < 0) {
                                ladderCost = 0;
                            }
                            if (mem[j - 1][k] > mem[j][k] + ladderCost) {
                                mem[j - 1][k] = mem[j][k] + ladderCost;
                                changedCurrent.add(j * m + k);
                                if (ladderCost < maxLadder) {
                                    maxLadder = ladderCost;
                                }
                            }
                        }
                        if (j != n - 1) {
                            int ladderCost = graph[j + 1][k] - graph[j][k];
                            if (ladderCost < 0) {
                                ladderCost = 0;
                            }
                            if (mem[j + 1][k] > mem[j][k] + ladderCost) {
                                changedCurrent.add(j * m + k);
                                if (ladderCost > maxLadder) {
                                    maxLadder = ladderCost;
                                }
                            }
                        }
                        if (k != 0) {
                            int ladderCost = graph[j][k - 1] - graph[j][k];
                            if (ladderCost < 0) {
                                ladderCost = 0;
                            }
                            if (mem[j][k - 1] > mem[j][k] + ladderCost) {
                                changedCurrent.add(j * m + k);
                                if (ladderCost > maxLadder) {
                                    maxLadder = ladderCost;
                                }
                            }
                        }
                        if (k != m - 1) {
                            int ladderCost = graph[j][k + 1] - graph[j][k];
                            if (ladderCost < 0) {
                                ladderCost = 0;
                            }
                            if (mem[j][k + 1] > mem[j][k] + ladderCost) {
                                changedCurrent.add(j * m + k);
                                if (ladderCost > maxLadder) {
                                    maxLadder = ladderCost;
                                }
                            }
                        }
                    }
                }
            }
            changedLast = changedCurrent;
            changedCurrent = new TreeSet<>();
        }

        return mem[n-1][m-1];
    }
}