## Saturday, February 28, 2015

### Lazy propagation in Segment Trees (SPOJ : HORRIBLE)

Lazy propagation in Segment Trees.

Read this first (the lazy propagation code): http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html

The code in the link above is for problems involving finding max in a given range.

To solve http://www.spoj.com/problems/HORRIBLE/ we need a little bit of modification in the code.

The trick is to add the new value but before that, multiplying it by the number of nodes below it during lazy updation at any node.

Code (C++):

```#include <stdio.h>
#include <math.h>

long long *segmentTree;
long long *lazy;

long long query(int qLo, int qHi, int cLo, int cHi, int stIndex);

void update(int qLo, int qHi, int cLo, int cHi, int stIndex, long long val) {
if (cHi < qLo || qHi < cLo)return;

if (lazy[stIndex] != 0) {
if (cLo == cHi) {
segmentTree[stIndex] += lazy[stIndex];
} else {
segmentTree[stIndex] += lazy[stIndex]*(cHi - cLo + 1);
lazy[stIndex * 2 + 1] += lazy[stIndex];
lazy[stIndex * 2 + 2] += lazy[stIndex];
}
lazy[stIndex] = 0;
}

if (qLo <= cLo && cHi <= qHi) {
if (cLo == cHi) {
segmentTree[stIndex] += val;
} else {
segmentTree[stIndex] += val * (cHi - cLo + 1);
lazy[stIndex * 2 + 1] += val;
lazy[stIndex * 2 + 2] += val;
}
return;
}

int mid = (cLo + cHi) / 2;
update(qLo, qHi, cLo, mid, stIndex * 2 + 1, val);
update(qLo, qHi, mid + 1, cHi, stIndex * 2 + 2, val);
int left = stIndex * 2 + 1;
int right = left + 1;
segmentTree[stIndex] = query(cLo, mid, cLo, mid, stIndex * 2 + 1) + query(mid + 1, cHi, mid + 1, cHi, stIndex * 2 + 2);
}

long long query(int qLo, int qHi, int cLo, int cHi, int stIndex) {
if (cHi < qLo || qHi < cLo)return 0;

if (lazy[stIndex] != 0) {
if (cLo == cHi) {
segmentTree[stIndex] += lazy[stIndex];
} else {
segmentTree[stIndex] += lazy[stIndex]*(cHi - cLo + 1);
lazy[stIndex * 2 + 1] += lazy[stIndex];
lazy[stIndex * 2 + 2] += lazy[stIndex];
}
lazy[stIndex] = 0;
}
if (qLo <= cLo && cHi <= qHi)return segmentTree[stIndex];

int mid = (cLo + cHi) / 2;
long long left = query(qLo, qHi, cLo, mid, stIndex * 2 + 1);
long long right = query(qLo, qHi, mid + 1, cHi, stIndex * 2 + 2);
return left + right;
}

int segSize;

void constructSegmentTree(int size) {
int height = (int) ceil(log((double) size) / log((double) 2));
segSize = (int) ceil(pow((double) 2, height + 1));
segmentTree = new long long[segSize];
lazy = new long long[segSize];
for (int i = 0; i < segSize; ++i) {
segmentTree[i] = 0;
lazy[i] = 0;
}
}

int main() {
int nCases;
scanf("%d", &nCases);
while (nCases--) {
int N, C;
scanf("%d %d", &N, &C);
constructSegmentTree(N);
for (int i = 0; i < C; ++i) {
int type, p, q;
long long v;
scanf("%d", &type);
if (type == 0) {
scanf("%d %d %lld", &p, &q, &v);
update(p - 1, q - 1, 0, N - 1, 0, v);
} else {
scanf("%d %d", &p, &q);
printf("%lld\n", query(p - 1, q - 1, 0, N - 1, 0));
}
}
delete(segmentTree);
delete(lazy);
}
}
```

## Thursday, February 26, 2015

### Segment Trees : SPOJ.com problem GSS1 & GSS3 solution.

Segment Trees Tutorials:

C++ Code  - GSS1:

```#include <stdio.h>
#include <math.h>

class Node {
public:
int lMax;
int rMax;
int anyMax;
int sum;

Node(int l, int a, int r, int s) {
lMax = l;
rMax = r;
anyMax = a;
sum = s;
}
};

Node **segmentTree;
int *array;

int max(int a, int b) {
if (a > b)return a;
else return b;
}

void segmentTreeConstructor(int arrayLo, int arrayHi, int stIndex) {
if (arrayLo == arrayHi) {
segmentTree[stIndex] = new Node(array[arrayLo], array[arrayLo], array[arrayLo], array[arrayLo]);
return;
}

int mid = (arrayLo + arrayHi) / 2;
segmentTreeConstructor(arrayLo, mid, stIndex * 2 + 1);
segmentTreeConstructor(mid + 1, arrayHi, stIndex * 2 + 2);

Node *current = segmentTree[stIndex] = new Node(0, 0, 0, 0);
Node *leftChild = segmentTree[stIndex * 2 + 1];
Node *rightChild = segmentTree[stIndex * 2 + 2];

current->lMax = max(leftChild->lMax, leftChild->sum + rightChild->lMax);
current->rMax = max(leftChild->rMax + rightChild->sum, rightChild->rMax);
current->anyMax = max(leftChild->anyMax, max(leftChild->rMax + rightChild->lMax, rightChild->anyMax));
current->sum = leftChild->sum + rightChild->sum;
}

Node& find(int stIndex, int qLow, int qHi, int currentLo, int currentHi) {
if (qLow == currentLo && qHi == currentHi)return *(segmentTree[stIndex]);
int mid = (currentLo + currentHi) / 2;
if (qHi <= mid)return find(2 * stIndex + 1, qLow, qHi, currentLo, mid);
else if (qLow > mid)return find(2 * stIndex + 2, qLow, qHi, mid + 1, currentHi);
else {
Node *currentResult = new Node(0, 0, 0, 0);
Node leftResult = find(2 * stIndex + 1, qLow, mid, currentLo, mid);
Node rightResult = find(2 * stIndex + 2, mid + 1, qHi, mid + 1, currentHi);

currentResult->lMax = max(leftResult.lMax, leftResult.sum + rightResult.lMax);
currentResult->rMax = max(leftResult.rMax + rightResult.sum, rightResult.rMax);
currentResult->anyMax = max(leftResult.anyMax, max(leftResult.rMax + rightResult.lMax, rightResult.anyMax));
currentResult->sum = leftResult.sum + rightResult.sum;

return *currentResult;
}
}

void constructSegmentTree(int* array, int size) {
int height = (int) ceil(log((double) size) / log((double) 2));
segmentTree = new Node*[(int) ceil(pow((double) 2, height + 1))];
segmentTreeConstructor(0, size - 1, 0);
}

int main() {
int nElements;
scanf("%d", &nElements);
array = new int[nElements];
for (int i = 0; i < nElements; ++i)scanf("%d", &array[i]);
constructSegmentTree(array, nElements);
int nQueries;
scanf("%d", &nQueries);
while (nQueries--) {
int l, h;
scanf("%d %d", &l, &h);
Node result = find(0, l - 1, h - 1, 0, nElements - 1);
printf("%d\n", result.anyMax);
}
}```

C++ GSS3 Code:

```#include <stdio.h>
#include <math.h>

class Node {
public:
int lMax;
int rMax;
int anyMax;
int sum;

Node(int l, int a, int r, int s) {
lMax = l;
rMax = r;
anyMax = a;
sum = s;
}

void toString() {
printf("[%d %d %d %d]\n", lMax, rMax, anyMax, sum);
}
};

Node **segmentTree;
int *array;

int max(int a, int b) {
if (a > b)return a;
else return b;
}

void segmentTreeConstructor(int arrayLo, int arrayHi, int stIndex) {
if (arrayLo == arrayHi) {
segmentTree[stIndex] = new Node(array[arrayLo], array[arrayLo], array[arrayLo], array[arrayLo]);
return;
}

int mid = (arrayLo + arrayHi) / 2;
segmentTreeConstructor(arrayLo, mid, stIndex * 2 + 1);
segmentTreeConstructor(mid + 1, arrayHi, stIndex * 2 + 2);

Node *current = segmentTree[stIndex] = new Node(0, 0, 0, 0);
Node *leftChild = segmentTree[stIndex * 2 + 1];
Node *rightChild = segmentTree[stIndex * 2 + 2];

current->lMax = max(leftChild->lMax, leftChild->sum + rightChild->lMax);
current->rMax = max(leftChild->rMax + rightChild->sum, rightChild->rMax);
current->anyMax = max(leftChild->anyMax, max(leftChild->rMax + rightChild->lMax, rightChild->anyMax));
current->sum = leftChild->sum + rightChild->sum;
}

Node& find(int stIndex, int qLow, int qHi, int currentLo, int currentHi) {
if (qLow == currentLo && qHi == currentHi)return *(segmentTree[stIndex]);
int mid = (currentLo + currentHi) / 2;
if (qHi <= mid)return find(2 * stIndex + 1, qLow, qHi, currentLo, mid);
else if (qLow > mid)return find(2 * stIndex + 2, qLow, qHi, mid + 1, currentHi);
else {
Node *currentResult = new Node(0, 0, 0, 0);
Node leftResult = find(2 * stIndex + 1, qLow, mid, currentLo, mid);
Node rightResult = find(2 * stIndex + 2, mid + 1, qHi, mid + 1, currentHi);

currentResult->lMax = max(leftResult.lMax, leftResult.sum + rightResult.lMax);
currentResult->rMax = max(leftResult.rMax + rightResult.sum, rightResult.rMax);
currentResult->anyMax = max(leftResult.anyMax, max(leftResult.rMax + rightResult.lMax, rightResult.anyMax));
currentResult->sum = leftResult.sum + rightResult.sum;

return *currentResult;
}
}

void modify(int stIndex, int target, int currentLo, int currentHi, int newVal) {
if (target == currentLo && currentLo == currentHi) {
Node &target = *(segmentTree[stIndex]);
target.sum = newVal;
target.lMax = newVal;
target.rMax = newVal;
target.anyMax = newVal;
return;
}

int mid = (currentLo + currentHi) / 2;
if (target <= mid) modify(2 * stIndex + 1, target, currentLo, mid, newVal);
else if (target > mid) modify(2 * stIndex + 2, target, mid + 1, currentHi, newVal);

Node *currentResult = segmentTree[stIndex];

Node leftResult = *(segmentTree[2 * stIndex + 1]);
Node rightResult = *(segmentTree[2 * stIndex + 2]);

currentResult->lMax = max(leftResult.lMax, leftResult.sum + rightResult.lMax);
currentResult->rMax = max(leftResult.rMax + rightResult.sum, rightResult.rMax);
currentResult->anyMax = max(leftResult.anyMax, max(leftResult.rMax + rightResult.lMax, rightResult.anyMax));
currentResult->sum = leftResult.sum + rightResult.sum;
}

void constructSegmentTree(int* array, int size) {
int height = (int) ceil(log((double) size) / log((double) 2));
segmentTree = new Node*[(int) ceil(pow((double) 2, height + 1))];
n = (int) ceil(pow((double) 2, height + 1));
segmentTreeConstructor(0, size - 1, 0);
}

int main() {
int nElements;
scanf("%d", &nElements);
array = new int[nElements];
for (int i = 0; i < nElements; ++i)scanf("%d", &array[i]);
constructSegmentTree(array, nElements);
int nQueries;
scanf("%d", &nQueries);
while (nQueries--) {
int type, l, h;
scanf("%d %d %d", &type, &l, &h);
if (type == 1) {
Node result = find(0, l - 1, h - 1, 0, nElements - 1);
printf("%d\n", result.anyMax);
} else {
modify(0, l - 1, 0, nElements - 1, h);
}
}
}```

## Thursday, February 19, 2015

### Checking if a given graph is Bipartite (BFS) JAVA

Algorithm:

1. Use a queue q.
2. Add any node to q.
3. For all those nodes that are connected to the current node polled from q, check if they have been assigned a color, if they have a color and it is the same as the current node, the graph is not bipartite and we need to stop the procedure else if they don't have any color add them to queue also (only if they have not been added previously [ use a boolean array or a HashSet for checking this ] ).
4. If the queue q is empty in the end it means that the given graph is bipartite.

Note: In case the graph is disjoint, we need to add all the given nodes to the queue and then check for all components connected to the current node popped from the queue.

Source:

```import java.util.*;

public class BipartiteCheck {
public static void main(String[] args) throws Exception{
//Indices start from 1
int graph[][] = {
{0,0,0,0,0,0,0,0,0},
{0,0,1,0,1,0,1,0,0},
{0,1,0,1,0,1,0,0,0},
{0,0,1,0,1,0,0,0,0},
{0,1,0,1,0,1,0,0,0},
{0,0,1,0,1,0,1,0,0},
{0,1,0,0,0,1,0,1,0},
{0,0,0,0,0,0,1,0,1},
{0,0,0,0,0,0,0,1,0},
};

int[] color = new int[graph.length];
color[1] = 1;

Queue<Integer> q = new LinkedList<>();

//Can also use a HashSet
boolean checked[] = new boolean[graph[0].length];

boolean check = true;

//In case the graph has disjoint nodes, add all of them to queue
//This is the case when every node of the graph is reachable from every other node
while(!q.isEmpty()){
int node = q.poll();
//                System.out.println("Checking node "+node);
for(int i=node+1;i<graph[0].length;++i){
if(graph[node][i]==1){
//                        System.out.println("node "+node+" is connected to node "+i);
if(!checked[i]){ q.add(i); checked[i] = true;}
if(color[i] == color[node]){
check = false;
break;
}
//                        System.out.println("Assigning color = "+(-color[node])+" to node "+i);
color[i] = -color[node];
}
}
if(!check)break;
}
System.out.println(Arrays.toString(color));
if(check) System.out.println("Given graph is bipartite!");
else System.out.println("Given graph is NOT bipartite!");
}
}```

Output:

[0, 1, -1, 1, -1, 1, -1, 1, -1]
Given graph is bipartite!

### Graph Coloring Problem : Backtracking Solution Java Implementation

Source:

```import java.util.*;
import java.io.*;
import java.math.*;

public class GraphColoring {
static int connected[][];
static int[] colors;
static int nColors;
static int nNodes;

static int getNodeColor(int k){
do{
int j;
//Assign the next color
colors[k] = colors[k]+1;

//If all colors have been tested on this node,
//return because there are no more new colors left
//to be considered for this node
if(colors[k]==nColors+1)return 0;

//Check to see if some connected node already has this color
for(j=1;j<=nNodes;++j){
if(connected[k][j] == 1 && colors[k] == colors[j] && k!=j){
break;
}
}
if(j==nNodes+1)return colors[k];
}while(true);
}

static void mColoring(int k){
do{
//get a color for this node
colors[k] = getNodeColor(k);

//if no more colors can be applied to this node, return
if(colors[k] == 0)return;

//if all the nodes have been assigned colors successfully, print the color assignments
if(k==nNodes){System.out.println("Color Assignment: "+Arrays.toString(colors));
//return /*don't quit until all possible assignments have been found*/
}
//consider the next node
else mColoring(k+1);
}while(true);
}

public static void main(String[] args) throws Exception{
nColors = 3;
connected = new int[][]{
{0, 0, 0, 0, 0},
{0, 1, 1, 0, 1},
{0, 1, 1, 1, 1},
{0, 0, 1, 1, 1},
{0, 1, 1, 1, 1},
};
nNodes = connected.length-1;
colors = new int[nNodes+1];

mColoring(1);
}
}```

Output:

Color Assignment: [0, 1, 2, 1, 3]
Color Assignment: [0, 1, 3, 1, 2]
Color Assignment: [0, 2, 1, 2, 3]
Color Assignment: [0, 2, 3, 2, 1]
Color Assignment: [0, 3, 1, 3, 2]
Color Assignment: [0, 3, 2, 3, 1]

## Tuesday, February 17, 2015

### A Sorting Algorithm

I thought of this algorithm this evening and implemented it for fun. It's not very good but anyways:

Time Complexity : O(n^2)
Space Complexity : O(n^2)

Algorithm:

We have an array of elements.

Start with first element. Store it in a stack. Iterate over remaining elements and check to see if they are greater than the last biggest found element in this stack. If it is bigger, store it in the stack and change bigger to contain this element. If it is less, skip it.

Now for the remaining elements, start with the first remaining element. Put it in a stack. Now do the same process with this stack (Iterate over the remaining elements to see if they are bigger than the current biggest element in this stack, skipping if they are smaller).

Do this until all of the elements have been put in some stack.

It is possible to have stacks containing only one element.

Now, compare the stack tops and pop that stack which has the biggest of all stack top elements.
Put the popped element in the original array at location i (i=0 to length of the array).

Do this until all of the stacks become empty.

The array is sorted.

Consider the array:

3, 7, 7, 4, 2, -3, 0

Stacks:

7
7                        0
3       4       2       -3
S1      S2      S3      S4

Now merge these stacks

Max(7, 4, 2, 0) = 7
Max(7, 4, 2, 0) = 7
Max(3, 4, 2, 0) = 4
Max(3, 2, 0)     = 3
Max(2, 0)         = 2
Max(0)             = 0
Max(-3)            = -3

Sorted Array  = 7, 7, 4, 3, 2, 0, -3

Elements have been sorted!
Code:

```import java.util.Arrays;

public class ASort {

public static void main(String[] args) throws Exception {
int array[] = {6, 4, 8, 9, 6, 5, -8, -9, 5, 6, -99, -5, 5, 0, 2, 3, 5,5,6,7,8,8,9,0, 0, 2, 5, 6, 9, -9, -8, -56};

int[][] stackAr = new int[array.length][array.length];
int[] indices = new int[array.length];
Arrays.fill(indices, -1);
int index = 0;

for (int i = 0; i < array.length; ++i) {
if (array[i] != Integer.MAX_VALUE) {
stackAr[index][++indices[index]] = array[i];
int greater = array[i];

for (int j = i + 1; j < array.length; ++j) {
if (array[j] != Integer.MAX_VALUE && array[j] >= greater) {
stackAr[index][++indices[index]] = array[j];
greater = array[j];
array[j] = Integer.MAX_VALUE;
}
}
index++;
}
}

index = 0;
for (int i = 0; i < array.length; ++i) {
int max = Integer.MIN_VALUE;
int indexOfTarget = 0;
for (int j = 0; j < array.length; ++j) {
if (indices[j] != -1) {
if (stackAr[j][indices[j]] > max) {
max = stackAr[j][indices[j]];
indexOfTarget = j;
}
}
}
array[i] = stackAr[indexOfTarget][indices[indexOfTarget]--];
}

for (int i = array.length - 1; i > -1; --i) {
System.out.print(array[i] + ", ");
}
System.out.println();
}
}```

Output:

-99, -56, -9, -9, -8, -8, -5, 0, 0, 0, 2, 2, 3, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 8, 8, 8, 9, 9, 9,

## Sunday, February 8, 2015

### A* Shortest Path Finding Algorithm Implementation in Java

A nice Tutorial : https://www.youtube.com/watch?v=-L-WgKMFuhE

Pseudo code:

OPEN //the set of nodes to be evaluated
CLOSED //the set of nodes already evaluated
add the start node to OPEN

loop
current = node in OPEN with the lowest f_cost
remove current from OPEN
add current to CLOSED

if current is the target node //path has been found
return

foreach neighbour of the current node
if neighbour is not traversable or neighbour is in CLOSED

if new path to neighbour is shorter OR neighbour is not in OPEN
set f_cost of neighbour
set parent of neighbour to current
if neighbour is not in OPEN
add neighbour to OPEN

Source:

```import java.util.*;

public class AStar {
public static final int DIAGONAL_COST = 14;
public static final int V_H_COST = 10;

static class Cell{
int heuristicCost = 0; //Heuristic cost
int finalCost = 0; //G+H
int i, j;
Cell parent;

Cell(int i, int j){
this.i = i;
this.j = j;
}

@Override
public String toString(){
return "["+this.i+", "+this.j+"]";
}
}

//Blocked cells are just null Cell values in grid
static Cell [][] grid = new Cell[5][5];

static PriorityQueue<Cell> open;

static boolean closed[][];
static int startI, startJ;
static int endI, endJ;

public static void setBlocked(int i, int j){
grid[i][j] = null;
}

public static void setStartCell(int i, int j){
startI = i;
startJ = j;
}

public static void setEndCell(int i, int j){
endI = i;
endJ = j;
}

static void checkAndUpdateCost(Cell current, Cell t, int cost){
if(t == null || closed[t.i][t.j])return;
int t_final_cost = t.heuristicCost+cost;

boolean inOpen = open.contains(t);
if(!inOpen || t_final_cost<t.finalCost){
t.finalCost = t_final_cost;
t.parent = current;
}
}

public static void AStar(){

//add the start location to open list.

Cell current;

while(true){
current = open.poll();
if(current==null)break;
closed[current.i][current.j]=true;

if(current.equals(grid[endI][endJ])){
return;
}

Cell t;
if(current.i-1>=0){
t = grid[current.i-1][current.j];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);

if(current.j-1>=0){
t = grid[current.i-1][current.j-1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}

if(current.j+1<grid[0].length){
t = grid[current.i-1][current.j+1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}
}

if(current.j-1>=0){
t = grid[current.i][current.j-1];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);
}

if(current.j+1<grid[0].length){
t = grid[current.i][current.j+1];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);
}

if(current.i+1<grid.length){
t = grid[current.i+1][current.j];
checkAndUpdateCost(current, t, current.finalCost+V_H_COST);

if(current.j-1>=0){
t = grid[current.i+1][current.j-1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}

if(current.j+1<grid[0].length){
t = grid[current.i+1][current.j+1];
checkAndUpdateCost(current, t, current.finalCost+DIAGONAL_COST);
}
}
}
}

/*
Params :
tCase = test case No.
x, y = Board's dimensions
si, sj = start location's x and y coordinates
ei, ej = end location's x and y coordinates
int[][] blocked = array containing inaccessible cell coordinates
*/
public static void test(int tCase, int x, int y, int si, int sj, int ei, int ej, int[][] blocked){
System.out.println("\n\nTest Case #"+tCase);
//Reset
grid = new Cell[x][y];
closed = new boolean[x][y];
open = new PriorityQueue<>((Object o1, Object o2) -> {
Cell c1 = (Cell)o1;
Cell c2 = (Cell)o2;

return c1.finalCost<c2.finalCost?-1:
c1.finalCost>c2.finalCost?1:0;
});
//Set start position
setStartCell(si, sj);  //Setting to 0,0 by default. Will be useful for the UI part

//Set End Location
setEndCell(ei, ej);

for(int i=0;i<x;++i){
for(int j=0;j<y;++j){
grid[i][j] = new Cell(i, j);
grid[i][j].heuristicCost = Math.abs(i-endI)+Math.abs(j-endJ);
//                  System.out.print(grid[i][j].heuristicCost+" ");
}
//              System.out.println();
}
grid[si][sj].finalCost = 0;

/*
Set blocked cells. Simply set the cell values to null
for blocked cells.
*/
for(int i=0;i<blocked.length;++i){
setBlocked(blocked[i][0], blocked[i][1]);
}

//Display initial map
System.out.println("Grid: ");
for(int i=0;i<x;++i){
for(int j=0;j<y;++j){
if(i==si&&j==sj)System.out.print("SO  "); //Source
else if(i==ei && j==ej)System.out.print("DE  ");  //Destination
else if(grid[i][j]!=null)System.out.printf("%-3d ", 0);
else System.out.print("BL  ");
}
System.out.println();
}
System.out.println();

AStar();
System.out.println("\nScores for cells: ");
for(int i=0;i<x;++i){
for(int j=0;j<x;++j){
if(grid[i][j]!=null)System.out.printf("%-3d ", grid[i][j].finalCost);
else System.out.print("BL  ");
}
System.out.println();
}
System.out.println();

if(closed[endI][endJ]){
//Trace back the path
System.out.println("Path: ");
Cell current = grid[endI][endJ];
System.out.print(current);
while(current.parent!=null){
System.out.print(" -> "+current.parent);
current = current.parent;
}
System.out.println();
}else System.out.println("No possible path");
}

public static void main(String[] args) throws Exception{
test(1, 5, 5, 0, 0, 3, 2, new int[][]{{0,4},{2,2},{3,1},{3,3}});
test(2, 5, 5, 0, 0, 4, 4, new int[][]{{0,4},{2,2},{3,1},{3,3}});
test(3, 7, 7, 2, 1, 5, 4, new int[][]{{4,1},{4,3},{5,3},{2,3}});

test(1, 5, 5, 0, 0, 4, 4, new int[][]{{3,4},{3,3},{4,3}});
}
}```

Output:

Test Case #1
Grid:
SO  0   0   0   BL
0   0   0   0   0
0   0   BL  0   0
0   BL  DE  BL  0
0   0   0   0   0

Scores for cells:
0   14  27  41  BL
14  17  29  42  56
27  29  BL  45  59
39  BL  43  BL  0
52  55  0   0   0

Path:
[3, 2] -> [2, 1] -> [1, 1] -> [0, 0]

Test Case #2
Grid:
SO  0   0   0   BL
0   0   0   0   0
0   0   BL  0   0
0   BL  0   BL  0
0   0   0   0   DE

Scores for cells:
0   17  33  48  BL
17  20  35  49  62
33  35  BL  52  64
48  BL  52  BL  67
62  65  64  67  77

Path:
[4, 4] -> [3, 4] -> [2, 3] -> [1, 2] -> [1, 1] -> [0, 0]

Test Case #3
Grid:
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   SO  0   BL  0   0   0
0   0   0   0   0   0   0
0   BL  0   BL  0   0   0
0   0   0   BL  DE  0   0
0   0   0   0   0   0   0

Scores for cells:
40  35  37  40  53  68  0
22  17  20  34  48  63  0
17  0   15  BL  48  61  75
20  15  18  31  43  56  70
34  BL  31  BL  46  58  73
48  48  43  BL  56  61  0
63  61  56  59  0   0   0

Path:
[5, 4] -> [4, 4] -> [3, 3] -> [3, 2] -> [2, 1]

Test Case #1
Grid:
SO  0   0   0   0
0   0   0   0   0
0   0   0   0   0
0   0   0   BL  BL
0   0   0   BL  DE

Scores for cells:
0   17  33  48  62
17  20  35  49  62
33  35  38  51  63
48  49  51  BL  BL
62  62  63  BL  0

No possible path

Add a comment if you find any error :)