import java.util.*;
public class Solution {
    int[][] DIRS = new int[][] {
            {0, 1}, {0, -1}, {1, 0}, {-1, 0}
    };
    boolean[][] visited;
    int M, N;
    int res;

    public int minimumInitHealth(int[][] rooms, int[] startPoint, int[] endPoint) {
        res = Integer.MIN_VALUE;

        M = rooms.length;
        N = rooms[0].length;
        visited = new boolean[M][N];

        dfs(rooms, startPoint[0], startPoint[1], endPoint[0], endPoint[1], 0, 0);
        return -res + 1;
    }

    private void dfs(int[][] rooms, int i, int j, int x, int y, int health, int minHealth) {
        health += rooms[i][j];
        minHealth = Math.min(minHealth, health);

        if (x == i && y == j) {
            res = Math.max(res, minHealth);
            return;
        }

        visited[i][j] = true;
        for (int w = 0; w < 4; w++) {
            int newI = i + DIRS[w][0];
            int newJ = j + DIRS[w][1];

            if (newI >= 0 && newI < M && newJ >= 0 && newJ < N && !visited[newI][newJ]) {
                dfs(rooms, newI, newJ, x, y, health, minHealth);
            }
        }
        visited[i][j] = false;
    }
}