HackerRank Find the Path Problem Solution

Yashwant Parihar,

In this post, we well solve HackerRank Find the Path Problem Solution.

You are given a table, a. with n rows and m columns. The top-left corner of the table has coordinates (0, 0), and the bottom-right corner has coordinates (n-1, m-1). The th cell contains integer aj.
A path in the table is a sequence of cells (r1, 1), (r2, C2),…, (rk, Ck) such that for each {1,…,k-1}, cell (r, c) and cell (ri+1, C++1) share a side.
The weight of the path (r₁, c₁), (r₂, C2),…, (rk, Ck) is defined by 1 ar,,&, where
arc is the weight of the cell (r, c).
You must answer q queries. In each query, you are given the coordinates of two cells, (ri, ci) and (r2, C2). You must find and print the minimum possible weight of a path connecting them.
Note: A cell can share sides with at most 4 other cells. A cell with coordinates (r, c) shares sides with (r-1,c), (r+1,c), (r, c-1) and (r, c + 1).

Input Format
The first line contains 2 space-separated integers, n (the number of rows in a) and m (the number of columns in a), respectively.
Each of n subsequent lines contains m space-separated integers. The th integer in the ¿th
line denotes the value of aij.
The next line contains a single integer, q, denoting the number of queries.
Each of the q subsequent lines describes a query in the form of 4 space-separated integers:

  1. C1, r2, and c₂, respectively.

Sample Input

3 5
0 0 0 0 0
1 9 9 9 1
0 0 0 0 0
3
0 0 2 4
0 3 2 3
1 1 1 3

Sample Output

1
1
18
HackerRank Find the Path Problem Solution
HackerRank Find the Path Problem Solution

Find the Path C Solution


#include <stdio.h>
#include <stdlib.h>
#define INF 1000000000
typedef struct{
  int i;
  int j;
  int w;
} node;
int min(int x,int y);
void build(int v,int l,int r);
void solve(int v,int l,int r);
void DJ(int si,int sj,int l,int r,int **d);
void heap_insert(node *elem,int *size);
void heap_update(node *elem);
void heap_read(int *size,node *ans);
int n,r1,c1,r2,c2,ans,a[7][5000],heap_list[7][5000],****d;
node heap[40000];

int main(){
  int m,q,i,j;
  scanf("%d%d",&n,&m);
  d=(int****)malloc(m*4*sizeof(int***));
  for(i=0;i<n;i++)
    for(j=0;j<m;j++)
      scanf("%d",&a[i][j]);
  build(1,0,m-1);
  scanf("%d",&q);
  while(q--){
    scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
    ans=INF;
    solve(1,0,m-1);
    printf("%d\n",ans);
  }
  return 0;
}
int min(int x,int y){
  return (x<y)?x:y;
}
void build(int v,int l,int r){
  int tm,i,j;
  tm=(l+r)/2;
  d[v]=(int***)malloc(n*sizeof(int**));
  for(i=0;i<n;i++){
    d[v][i]=(int**)malloc(n*sizeof(int*));
    for(j=0;j<n;j++)
      d[v][i][j]=(int*)malloc((r-l+1)*sizeof(int));
    DJ(i,tm-l,l,r,d[v][i]);
  }
  if(l!=r){
    build(2*v,l,tm);
    build(2*v+1,tm+1,r);
  }
  return;
}
void solve(int v,int l,int r){
  int tm,i;
  tm=(l+r)/2;
  for(i=0;i<n;i++)
    ans=min(ans,d[v][i][r1][c1-l]+d[v][i][r2][c2-l]+a[i][tm]);
  if(c1<tm && c2<tm)
    solve(2*v,l,tm);
  else if(c1>tm && c2>tm)
    solve(2*v+1,tm+1,r);
  return;
}
void DJ(int si,int sj,int l,int r,int **d){
  int i,j,next_solve_i,next_solve_j,heap_size=0;
  node elem;
  for(i=0;i<n;i++)
    for(j=0;j<r-l+1;j++)
      d[i][j]=-1;
  d[si][sj]=0;
  next_solve_i=si;
  next_solve_j=sj;
  while(1){
    if(next_solve_i){
      if(d[next_solve_i-1][next_solve_j]==-1 || d[next_solve_i-1][next_solve_j]>d[next_solve_i][next_solve_j]+a[next_solve_i-1][next_solve_j+l]){
        elem.i=next_solve_i-1;
        elem.j=next_solve_j;
        elem.w=d[next_solve_i][next_solve_j]+a[next_solve_i-1][next_solve_j+l];
        if(d[next_solve_i-1][next_solve_j]==-1)
          heap_insert(&elem,&heap_size);
        else
          heap_update(&elem);
        d[next_solve_i-1][next_solve_j]=d[next_solve_i][next_solve_j]+a[next_solve_i-1][next_solve_j+l];
      }
    }
    if(next_solve_i+1<n){
      if(d[next_solve_i+1][next_solve_j]==-1 || d[next_solve_i+1][next_solve_j]>d[next_solve_i][next_solve_j]+a[next_solve_i+1][next_solve_j+l]){
        elem.i=next_solve_i+1;
        elem.j=next_solve_j;
        elem.w=d[next_solve_i][next_solve_j]+a[next_solve_i+1][next_solve_j+l];
        if(d[next_solve_i+1][next_solve_j]==-1)
          heap_insert(&elem,&heap_size);
        else
          heap_update(&elem);
        d[next_solve_i+1][next_solve_j]=d[next_solve_i][next_solve_j]+a[next_solve_i+1][next_solve_j+l];
      }
    }
    if(next_solve_j){
      if(d[next_solve_i][next_solve_j-1]==-1 || d[next_solve_i][next_solve_j-1]>d[next_solve_i][next_solve_j]+a[next_solve_i][next_solve_j-1+l]){
        elem.i=next_solve_i;
        elem.j=next_solve_j-1;
        elem.w=d[next_solve_i][next_solve_j]+a[next_solve_i][next_solve_j-1+l];
        if(d[next_solve_i][next_solve_j-1]==-1)
          heap_insert(&elem,&heap_size);
        else
          heap_update(&elem);
        d[next_solve_i][next_solve_j-1]=d[next_solve_i][next_solve_j]+a[next_solve_i][next_solve_j-1+l];
      }
    }
    if(next_solve_j+1+l<=r){
      if(d[next_solve_i][next_solve_j+1]==-1 || d[next_solve_i][next_solve_j+1]>d[next_solve_i][next_solve_j]+a[next_solve_i][next_solve_j+1+l]){
        elem.i=next_solve_i;
        elem.j=next_solve_j+1;
        elem.w=d[next_solve_i][next_solve_j]+a[next_solve_i][next_solve_j+1+l];
        if(d[next_solve_i][next_solve_j+1]==-1)
          heap_insert(&elem,&heap_size);
        else
          heap_update(&elem);
        d[next_solve_i][next_solve_j+1]=d[next_solve_i][next_solve_j]+a[next_solve_i][next_solve_j+1+l];
      }
    }
    if(heap_size==0)
      break;
    heap_read(&heap_size,&elem);
    next_solve_i=elem.i;
    next_solve_j=elem.j;
  }
  return;
}
void heap_insert(node *elem,int *size){
  (*size)++;
  int index=(*size);
  while(index>1 && elem->w<heap[index/2].w){
    heap[index]=heap[index/2];
    heap_list[heap[index].i][heap[index].j]=index;
    index/=2;
  }
  heap[index]=(*elem);
  heap_list[elem->i][elem->j]=index;
  return;
}
void heap_update(node *elem){
  int index=heap_list[elem->i][elem->j];
  while(index>1 && elem->w<heap[index/2].w){
    heap[index]=heap[index/2];
    heap_list[heap[index].i][heap[index].j]=index;
    index/=2;
  }
  heap[index]=(*elem);
  heap_list[elem->i][elem->j]=index;
  return;
}
void heap_read(int *size,node *ans){
  (*ans)=heap[1];
  int index=1;
  while(index*2<*size && heap[*size].w>heap[index*2].w || index*2+1<*size && heap[*size].w>heap[index*2+1].w){
    index=(heap[index*2].w>heap[index*2+1].w)?index*2+1:index*2;
    heap[index/2]=heap[index];
    heap_list[heap[index].i][heap[index].j]=index/2;
  }
  heap[index]=heap[*size];
  heap_list[heap[index].i][heap[index].j]=index;
  (*size)--;
  return;
}

Find the Path C++ Solution

#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<vector<int64_t>> G;
const int64_t INF = 1e11;

vector<vector<int64_t>> dijk(int r, int c, int L, int R) {
    set<pair<int64_t, pair<int, int>>> Q;
    vector<vector<int64_t>> D(N, vector<int64_t>(R-L+1, INF));
    Q.insert(make_pair(0, make_pair(r,c)));
    vector<vector<int>> dirs = {{1,0},{0,1},{-1,0},{0,-1}};
    while (!Q.empty()) {
        auto curr = *Q.begin();
        Q.erase(Q.begin());
        int64_t d = curr.first;
        int r = curr.second.first, c = curr.second.second;
        if (d > D[r][c-L]) {
            continue;
        }
        D[r][c-L] = d;
        for (auto dir : dirs) {
            int cr = r+dir[0];
            int cc = c+dir[1];
            if (cr < 0 || cc < L || cr >= N || cc > R)
                continue;
            int64_t cd = d + G[cr][cc];
            if (cd < D[cr][cc-L]) {
                Q.insert(make_pair(cd, make_pair(cr, cc)));
                D[cr][cc-L] = cd;
            }
        }
    }
    return D;
}

vector<vector<int>> Qs;
vector<int64_t> ans;

vector<unordered_map<int, pair<int, vector<vector<int64_t>>>>> SPs(7);

void div_and_conq(int l, int r, vector<int> Qis) {
    if (l > r)
        return;
    int mid = (r+l)/2;
    for (int i = 0; i < N; ++i) {
        SPs[i][mid] = make_pair(l, dijk(i, mid, l, r));
    }
    vector<int> Qls, Qrs;
    for (int i : Qis) {
        
        if (Qs[i][1] < mid && Qs[i][3] < mid) {
            Qls.push_back(i);
        } else if (Qs[i][1] > mid && Qs[i][3] > mid) {
            Qrs.push_back(i);
        } else {
            for (int j = 0; j < N; ++j) {
                for (auto& kv : SPs[j]) {
                    int mid = kv.first;
                    int upperl = kv.second.first;
                    auto& SP = kv.second.second;
                    int64_t d = SP[Qs[i][0]][Qs[i][1]-upperl]+SP[Qs[i][2]][Qs[i][3]-upperl]+G[j][mid];
                    ans[i] = min(ans[i], d);
                }
            }
        }
    }
    div_and_conq(l, mid-1, Qls);
    div_and_conq(mid+1, r, Qrs);
    for (int i = 0; i < N; ++i) {
        SPs[i].erase(mid);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> M;
    G.assign(N, vector<int64_t>(M));
    for (auto &v : G) {
        for (int64_t& i : v) {
            cin >> i;
        }
    }
    int Q;
    cin >> Q;
    Qs.resize(Q);
    ans.assign(Q, INF);
    vector<int> Qis;
    for (int i = 0; i < Q; ++i) {
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        Qs[i] = {a,b,c,d};
        Qis.push_back(i);
    }
    div_and_conq(0, M-1, Qis);
    for (int64_t i : ans) {
        cout << i << endl;
    }
    return 0;
}

Find the Path C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

struct Node
{
    public int w;
    public int r;
    public int c;
    
    public Node(int w, int r, int c){
        this.w = w;
        this.r = r;
        this.c = c;
    }
}

class Heap
{
    public int length = 0;
    private Node[] heap;
    
    public Heap(int n, int m){
        this.heap = new Node[(int)(n*m*0.67)];
    }
    
    public void initialize(){
        this.length = 0;
    }
    
    public void push (Node node){
        this.heap[this.length] = node;
        this.length++;
        int node_w=node.w, node_i=this.length-1, parent_i;
        while (node_i>0){
            parent_i = (node_i-1)/2;
            if (node_w>=this.heap[parent_i].w){
                break;
            }
            else{
                this.heap[node_i] = this.heap[parent_i];
                this.heap[parent_i] = node;
                node_i = parent_i;
            }
        }
    }
    
    public Node pop(){
        Node node=this.heap[this.length-1], node_return=this.heap[0];
        this.heap[0] = node;
        this.length--;
        int node_w=node.w, node_i=0, 
            child_l_i=node_i*2+1, child_r_i=child_l_i+1, child_s_i;
        while (child_l_i<this.length){
            if (child_r_i<this.length){
                if (this.heap[child_r_i].w<this.heap[child_l_i].w){
                    child_s_i = child_r_i;
                }
                else{
                    child_s_i = child_l_i;
                }
            }
            else{
                child_s_i = child_l_i;
            }
            if (node_w<this.heap[child_s_i].w){
                break;
            }
            else{
                this.heap[node_i] = this.heap[child_s_i];
                this.heap[child_s_i] = node;
                node_i = child_s_i;
                child_l_i = node_i*2+1;
                child_r_i = child_l_i+1;
            }
        }
        return node_return;
    }
}

class Collectively
{
    private int n, m, max_w;
    private int [] middle_w;
    private int [,,] map;
    private List<List<int>> a;
    private Heap heap;
    
    
    public Collectively(List<List<int>> a, int n, int m, int max_w){
        this.a = a;
        this.n = n;
        this.m = m;
        this.max_w = max_w;
        this.middle_w = new int[this.n];
        this.map = new int[this.n, this.n, this.m];
        this.heap = new Heap(n, m);
    }
    
    public float update_map(int left, int middle, int right){
        int to_fill=(right-left+1)*this.n, filled=1, filled_all=1, w, r, r_, c, c_;
        bool[,] explored;
        Node node;
        for (int i_n=0; i_n<this.n; i_n++){
            this.middle_w[i_n] = this.a[i_n][middle];
            explored = new bool[this.n, this.m];
            heap.initialize();
            heap.push(new Node(this.a[i_n][middle], i_n, middle));
            explored[i_n, middle] = true;
            this.map[i_n, i_n, middle] = this.a[i_n][middle];
            filled = 1;
            filled_all = 1;
            while (true){
                node = heap.pop();
                if (filled>=to_fill){
                    break;
                }
                w = node.w;
                c = node.c;
                r = node.r;
                c_ = c;
                if (r>0){
                    r_ = r-1;
                    if (!explored[r_, c_]){
                        heap.push(new Node(this.a[r_][c_]+w, r_, c_));
                        explored[r_, c_] = true;
                        this.map[i_n, r_, c_] = this.a[r_][c_]+w;
                        filled_all += 1;
                        if (c_>=left && c_<=right){
                            filled++;
                        }
                    }
                }
                if (r<this.n-1){
                    r_ = r+1;
                    if (!explored[r_, c_]){
                        heap.push(new Node(this.a[r_][c_]+w, r_, c_));
                        explored[r_, c_] = true;
                        this.map[i_n, r_, c_] = this.a[r_][c_]+w;
                        filled_all += 1;
                        if (c_>=left && c_<=right){
                            filled++;
                        }
                    }
                }
                r_ = r;
                if (c>0){
                    c_ = c-1;
                    if (!explored[r_, c_]){
                        heap.push(new Node(this.a[r_][c_]+w, r_, c_));
                        explored[r_, c_] = true;
                        this.map[i_n, r_, c_] = this.a[r_][c_]+w;
                        filled_all += 1;
                        if (c_>=left && c_<=right){
                            filled++;
                        }
                    }
                }
                if (c<this.m-1){
                    c_ = c+1;
                    if (!explored[r_, c_]){
                        heap.push(new Node(this.a[r_][c_]+w, r_, c_));
                        explored[r_, c_] = true;
                        this.map[i_n, r_, c_] = this.a[r_][c_]+w;
                        filled_all += 1;
                        if (c_>=left && c_<=right){
                            filled++;
                        }
                    }
                }
            }
        }
        return (float)(filled_all) / (float)(filled);
    }
    
    public int get_min_w(List<int> query){
        int min_w = this.max_w, w;
        for (int i_n=0; i_n<this.n; i_n++){
            w = this.map[i_n, query[0], query[1]] +
                this.map[i_n, query[2], query[3]] - 
                this.middle_w[i_n];
            if (w<min_w){
                min_w = w;
            }
        }
        return min_w;
    }
}

class Individually
{
    private int n, m;
    private List<List<int>> a;
    private Heap heap;
    
    public Individually(List<List<int>> a, int n, int m){
        this.a = a;
        this.n = n;
        this.m = m;
        this.heap = new Heap(n, m);
    }
    
    public int get_min_w(List<int> query){
        int w, distance, r, r_, c, c_,
            r_1 = query[0], c_1 = query[1], r_2 = query[2], c_2 = query[3];
        bool[,] explored = new bool[this.n, this.m];
        Node node;
        heap.initialize();
        explored[r_1, c_1] = true;
        heap.push(new Node(this.a[r_1][c_1], r_1, c_1));
        while (true){
            node = heap.pop();
            w = node.w;
            c = node.c;
            r = node.r;
            distance = Math.Abs(r-r_2)+Math.Abs(c-c_2);
            if (distance<=1){
                if (distance==1){
                    return w+a[r_2][c_2];
                }
                else{
                    return w;
                }
            }
            c_ = c;
            if (r>0){
                r_ = r-1;
                if (!explored[r_, c_]){
                    heap.push(new Node(a[r_][c_]+w, r_, c_));
                    explored[r_, c_] = true;
                }
            }
            if (r<n-1){
                r_ = r+1;
                if (!explored[r_, c_]){
                    heap.push(new Node(a[r_][c_]+w, r_, c_));
                    explored[r_, c_] = true;
                }
            }
            r_ = r;
            if (c>0){
                c_ = c-1;
                if (!explored[r_, c_]){
                    heap.push(new Node(a[r_][c_]+w, r_, c_));
                    explored[r_, c_] = true;
                }
            }
            if (c<m-1){
                c_ = c+1;
                if (!explored[r_, c_]){
                    heap.push(new Node(a[r_][c_]+w, r_, c_));
                    explored[r_, c_] = true;
                }
            }
        }
    }
}

class WorkSpace
{
    private int n, m;
    public int[] result;
    private List<List<int>> a, queries, index_remained;
    private bool[] index_solved;
    private Collectively collectively;
    private Individually individually;
    
    public WorkSpace(List<List<int>> a, List<List<int>> queries){
        this.n = a.Count();
        this.m = a[0].Count();
        this.result = new int[queries.Count()];
        this.a = a;
        this.queries = queries;
        // this.index_remained = new List<List<int>>();
        this.index_solved = new bool[queries.Count()];
        this.collectively = new Collectively(a, n, m, 3000*n*m+1);
        this.individually = null;
    }
    
    public void solve(List<int> index_to_solve, int left, int right){
        int middle = (int)((left + right) / 2);
        List<int> index_solving = new List<int>();
        List<int> index_unsolved_left = new List<int>();
        List<int> index_unsolved_right = new List<int>();
        foreach (int index in index_to_solve){
            int dc_1 = this.queries[index][1] - middle,
                dc_2 = this.queries[index][3] - middle;
            if (dc_1*dc_2<=0){
                index_solving.Add(index);
            }
            else if (dc_1<0){
                index_unsolved_left.Add(index);
            }
            else if (dc_1>0){
                index_unsolved_right.Add(index);
            }
        }
        if (index_solving.Count()>this.n){
            float ratio = this.collectively.update_map(left, middle, right);
            foreach (int index in index_solving){
                this.result[index] = this.collectively.get_min_w(this.queries[index]);
                this.index_solved[index] = true;
            }
            if (ratio<6.0){
                this.solve(index_unsolved_left, left, middle-1);
                this.solve(index_unsolved_right, middle+1, right);
            }
        }
    }
    
    public void solve_remained(){
        this.collectively = null;
        this.individually = new Individually(a, n, m);
        for (int index=0; index<this.index_solved.Count(); index++){
            if (!index_solved[index]){
                this.result[index] = this.individually.get_min_w(this.queries[index]);
            }
        }
    }
}

class Result
{
    public static List<int> shortestPath(List<List<int>> a, List<List<int>> queries)
    {
        int m=a[0].Count();
        WorkSpace work_space = new WorkSpace(a, queries);
        work_space.solve(Enumerable.Range(0, queries.Count()).ToList(), 0, m-1);
        work_space.solve_remained();
        return new List<int>(work_space.result);
    }
}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

        int n = Convert.ToInt32(firstMultipleInput[0]);

        int m = Convert.ToInt32(firstMultipleInput[1]);

        List<List<int>> a = new List<List<int>>();

        for (int i = 0; i < n; i++)
        {
            a.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(aTemp => Convert.ToInt32(aTemp)).ToList());
        }

        int q = Convert.ToInt32(Console.ReadLine().Trim());

        List<List<int>> queries = new List<List<int>>();

        for (int i = 0; i < q; i++)
        {
            queries.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(queriesTemp => Convert.ToInt32(queriesTemp)).ToList());
        }

        List<int> result = Result.shortestPath(a, queries);

        textWriter.WriteLine(String.Join("\n", result));

        textWriter.Flush();
        textWriter.Close();
    }
}

Find the Path Java Solution

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class C {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    void solve()
    {
        int n = ni(), m = ni();
        int[][] a = new int[m][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                a[j][i] = ni();
            }
        }
        d = new long[m][n][][];
        
        build(0, m, a);
        
        int Q = ni();
        for(int q = 0;q < Q;q++){
            int sc = ni(), sr = ni();
            int tc = ni(), tr = ni();
            if(sr > tr){
                {int du = tr; tr = sr; sr = du;}
                {int du = tc; tc = sc; sc = du;}
            }
            out.println(go(0, m, sr, sc, tr, tc, a));
        }
        
    }
    
    static long go(int L, int R, int sr, int sc, int tr, int tc, int[][] a)
    {
        int M = L+R>>>1;
        int m = a[0].length;
        long ret = Long.MAX_VALUE;
        for(int i = 0;i < m;i++){
            ret = Math.min(ret, d[M][i][sr-L][sc] + d[M][i][tr-L][tc] - a[M][i]);
        }
        if(sr <= M && M <= tr){
            return ret;
        }
        if(R-L <= 1)return ret;
        if(tr < M){
            return Math.min(ret, go(L, M, sr, sc, tr, tc, a));
        }else{
            return Math.min(ret, go(M, R, sr, sc, tr, tc, a));
        }
    }
    
    static long[][][][] d;
    
    static void build(int L, int R, int[][] a)
    {
        int m = a[0].length;
        int M = L+R>>>1;
        if(d[M][0] != null)return;
        for(int i = 0;i < m;i++){
            d[M][i] = dijk(a, M, i, L, R);
        }
        if(R-L <= 1)return;
        build(L, M, a);
        build(M, R, a);
    }
    
    public static long[][] dijk(int[][]  a, int sr, int sc, int L, int R)
    {
        int m = a[0].length;
        long[][] td = new long[R-L][m];
        for(int i = 0;i < R-L;i++){
            Arrays.fill(td[i], Long.MAX_VALUE / 3);
        }
        td[sr-L][sc] = 0;
        MinHeapL q = new MinHeapL((R-L)*m);
        q.add((sr-L)*m+sc, 0L);
        td[sr-L][sc] = a[sr][sc];
        
        int[] dr = { 1, 0, -1, 0 };
        int[] dc = { 0, 1, 0, -1 };
        
        while(q.size() > 0){
            int cur = q.argmin();
            q.remove(cur);
            
            int r = cur / m, c = cur % m;
            for(int k = 0;k < 4;k++){
                int nr = r + dr[k], nc = c + dc[k];
                if(nr >= L-L && nr < R-L && nc >= 0 && nc < m){
                    long nd = td[r][c] + a[nr+L][nc];
                    if(nd < td[nr][nc]){
                        td[nr][nc] = nd;
                        q.update(nr*m+nc, nd);
                    }
                }
            }
        }
        
        return td;
    }
    
    public static class MinHeapL {
        public long[] a;
        public int[] map;
        public int[] imap;
        public int n;
        public int pos;
        public static long INF = Long.MAX_VALUE;
        
        public MinHeapL(int m)
        {
            n = Integer.highestOneBit((m+1)<<1);
            a = new long[n];
            map = new int[n];
            imap = new int[n];
            Arrays.fill(a, INF);
            Arrays.fill(map, -1);
            Arrays.fill(imap, -1);
            pos = 1;
        }
        
        public long add(int ind, long x)
        {
            int ret = imap[ind];
            if(imap[ind] < 0){
                a[pos] = x; map[pos] = ind; imap[ind] = pos;
                pos++;
                up(pos-1);
            }
            return ret != -1 ? a[ret] : x;
        }
        
        public long update(int ind, long x)
        {
            int ret = imap[ind];
            if(imap[ind] < 0){
                a[pos] = x; map[pos] = ind; imap[ind] = pos;
                pos++;
                up(pos-1);
            }else{
                a[ret] = x;
                up(ret);
                down(ret);
            }
            return x;
        }
        
        public long remove(int ind)
        {
            if(pos == 1)return INF;
            if(imap[ind] == -1)return INF;
            
            pos--;
            int rem = imap[ind];
            long ret = a[rem];
            map[rem] = map[pos];
            imap[map[pos]] = rem;
            imap[ind] = -1;
            a[rem] = a[pos];
            a[pos] = INF;
            map[pos] = -1;
            
            up(rem);
            down(rem);
            return ret;
        }
        
        public long min() { return a[1]; }
        public int argmin() { return map[1]; }
        public int size() {    return pos-1; }
        
        private void up(int cur)
        {
            for(int c = cur, p = c>>>1;p >= 1 && a[p] > a[c];c>>>=1, p>>>=1){
                long d = a[p]; a[p] = a[c]; a[c] = d;
                int e = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = e;
                e = map[p]; map[p] = map[c]; map[c] = e;
            }
        }
        
        private void down(int cur)
        {
            for(int c = cur;2*c < pos;){
                int b = a[2*c] < a[2*c+1] ? 2*c : 2*c+1;
                if(a[b] < a[c]){
                    long d = a[c]; a[c] = a[b]; a[b] = d;
                    int e = imap[map[c]]; imap[map[c]] = imap[map[b]]; imap[map[b]] = e;
                    e = map[c]; map[c] = map[b]; map[b] = e;
                    c = b;
                }else{
                    break;
                }
            }
        }
    }    
    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new C().run(); }
    
    private byte[] inbuf = new byte[1024];
    private int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

Find the Path JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the shortestPath function below.
 */
class MinHeap {
    constructor() {
        this._arr = [];
    }
    insert(value, data) {
        let i = this._arr.length;
        let j = (i - 1) >> 1;
        while (j >= 0 && value < this._arr[j][0]) {
            this._arr[i] = this._arr[j];
            i = j;
            j = (i - 1) >> 1;
        }
        this._arr[i] = [value, data];
    }
    extract() {
        const result = this._arr[0];
        const [value, data] = this._arr.pop();
        if (this._arr.length) {
            let i = 0;
            let j = 1;
            while (true) {
                if (j + 1 < this._arr.length && this._arr[j][0] >= this._arr[j + 1][0]) j++; // Get child with least value
                if (j >= this._arr.length || value <= this._arr[j][0]) break;
                this._arr[i] = this._arr[j];
                i = j;
                j = j * 2 + 1;
            }
            this._arr[i] = [value, data];
        }
        return result;
    }
}

function shortestPath(a, queries) {
    const chunk = Math.floor(2500 / a.length);
    // Create graph
    const width = a[0].length;
    const nodes = [].concat(...a.map((row, y) => row.map((weight, x) => ({ weight, x, y, distTo: new Map, gates: [] }))));
    const gates = Array.from({ length: (Math.floor((width - 1) / chunk) + 1) }, (_, x) =>
        a.map((_, y) => nodes[y * width + x * chunk])
    );
    nodes.forEach((node, i) => {
        node.neighbors = [-1, 1, -width, width]
            .map(d => i + d)
            .map((j, k) => (k > 1 || j % width - i % width === j - i) && nodes[j])
            .filter(Boolean);
        node.gates = gates.slice(Math.floor(node.x / chunk));
    });
    gates.forEach((gate, x) => {
        const min = Math.max(0, (x - 1) * chunk);
        const max = Math.min(width, (x + 1) * chunk);
        gate.forEach((centre, y) => {
            flood(centre, min, max);
            // Make jumps between more distant gates
            if (!x) return;
            gates.slice(0, x - 1).forEach((gate, j) => {
                for (const start of gate) {
                    start.distTo.set(centre, Math.min(...gates[x - 1].map(mid => distanceVia(start, mid, centre))));
                }
            });
        });
    });

    function distanceVia(a, b, c) {
        if (a === b) return b.distTo.get(c);
        if (b === c) return a.distTo.get(b);
        return a.distTo.get(b) + b.distTo.get(c) - b.weight;
    }

    function flood(centre, min, max) {
        const heap = new MinHeap();
        heap.insert(centre.weight, centre);
        const visited = new Set;
        for (let count = (max - min) * a.length; count;) {
            const [dist, node] = heap.extract();
            if (visited.has(node)) continue;
            visited.add(node);
            if (node.x >= min && node.x < max) {
                node.distTo.set(centre, dist);
                count--;
            }
            for (const neighbor of node.neighbors) {
                if (!visited.has(neighbor)) heap.insert(dist + neighbor.weight, neighbor);
            }
        }
    }

    function distance(a, b) {
        if (a === b) return a.weight;
        if (a.x > b.x) [a, b] = [b, a];
        const i = Math.floor(a.x / chunk);
        const j = Math.floor(b.x / chunk);

        const heap = new MinHeap();
        const visited = new Set;
        if (j - i > 1) { // Separated by multiple gates
            return Math.min(...a.gates[1].map(start =>
                a.distTo.get(start) - start.weight +
                Math.min(...b.gates[0].map(end =>
                    start.distTo.get(end) + b.distTo.get(end) - end.weight
                ))
            ));
        }
        if (j > i) { // Separated by one gate
            return Math.min(...a.gates[1].map(mid =>
                a.distTo.get(mid) + b.distTo.get(mid) - mid.weight
            ));
        }
        // Within same pair of gates:
        // Get distance via one of both surrounding gates:
        const dist = Math.min(
            ...a.gates[0].concat(a.gates[1] || []).map(centre => a.distTo.get(centre) + b.distTo.get(centre) - centre.weight),
        );
        // ... That way we don't have to search beyond the nearby gates.
        heap.insert(a.weight, a);
        heap.insert(dist, b);
        while (true) {
            const [dist, node] = heap.extract();
            if (visited.has(node)) continue;
            if (node === b) return dist;
            visited.add(node);
            // If node is in a gate, do not include neighbors on the other side of it, but
            // instead add the gate-nodes, with their relative distances
            for (const neighbor of node.neighbors) {
                if (!visited.has(neighbor) && Math.floor(neighbor.x / chunk) === i) {
                    heap.insert(dist + neighbor.weight, neighbor);
                }
            }
        }
    }
    return queries.map(([ai, aj, bi, bj]) => distance(nodes[ai * width + aj], nodes[bi * width + bj]));
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nm = readLine().split(' ');

    const n = parseInt(nm[0], 10);

    const m = parseInt(nm[1], 10);

    let a = Array(n);

    for (let aRowItr = 0; aRowItr < n; aRowItr++) {
        a[aRowItr] = readLine().split(' ').map(aTemp => parseInt(aTemp, 10));
    }

    const q = parseInt(readLine(), 10);

    let queries = Array(q);

    for (let queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
        queries[queriesRowItr] = readLine().split(' ').map(queriesTemp => parseInt(queriesTemp, 10));
    }

    let result = shortestPath(a, queries);

    ws.write(result.join("\n") + "\n");

    ws.end();
}

Find the Path Python Solution

# Enter your code here. Read input from STDIN. Print output to STDOUT

import sys
from heapq import *

Row_Count = 0
Col_Count = 0
Query_Count = 0
Table = []
Query_Dict = {}
Query_Results = []
Shortest_Paths = []
Visited = []


def readInput():
    global Row_Count, Col_Count, Query_Count, Table, Query_Dict, Query_Results, Shortest_Paths, Visited
    
    Row_Count, Col_Count = map(int, raw_input().split())
    for i in xrange(Row_Count):
        row = []
        entry_list = raw_input().split()
        for j in xrange(Col_Count):
            row.append(int(entry_list[j]))
        Table.append(row)

    Shortest_Paths = [ [ sys.maxint for j in range(Col_Count) ] for i in range(Row_Count) ]
    Visited = [ [ False for j in range(Col_Count) ] for i in range(Row_Count) ]  
    
    Query_Count = int(raw_input())
    for i in xrange(Query_Count):
        Query_Results.append(sys.maxint)
        query = map(int, raw_input().split())
        if query[1] > query[3]:
            query = (query[2], query[3], query[0], query[1])
        else:
            query = (query[0], query[1], query[2], query[3])
        
        if not Query_Dict.has_key(query):
            Query_Dict[query] = []
        Query_Dict[query].append(i)
    
    
def isValidSquare(row, col, left_bound, right_bound):
    return row >= 0 and row < Row_Count and col >= left_bound and col <= right_bound

    
def processSingleSquare(start_row, start_col, left_bound, right_bound):
    global Shortest_Paths, Visited
    
    for i in range(Row_Count):
        for j in range(left_bound, right_bound + 1):
            Shortest_Paths[i][j] = sys.maxint
            Visited[i][j] = False  
    
    bfs_heap = []
    Shortest_Paths[start_row][start_col] = Table[start_row][start_col]
    heappush(bfs_heap, (Table[start_row][start_col], start_row, start_col))
    
    while bfs_heap:
        weight, row, col = heappop(bfs_heap)
        if Visited[row][col]:
            continue         
            
        Visited[row][col] = True
        
        if isValidSquare(row - 1, col, left_bound, right_bound) and not Visited[row - 1][col] :
            if weight + Table[row - 1][col] < Shortest_Paths[row - 1][col]:
                Shortest_Paths[row - 1][col] = weight + Table[row - 1][col]
                heappush(bfs_heap, (weight + Table[row - 1][col], row - 1, col))
        if isValidSquare(row + 1, col, left_bound, right_bound) and not Visited[row + 1][col]:
            if weight + Table[row + 1][col] < Shortest_Paths[row + 1][col]:
                Shortest_Paths[row + 1][col] = weight + Table[row + 1][col]
                heappush(bfs_heap, (weight + Table[row + 1][col], row + 1, col))
        if isValidSquare(row, col - 1, left_bound, right_bound) and not Visited[row][col - 1]:
            if weight + Table[row][col - 1] < Shortest_Paths[row][col - 1]:
                Shortest_Paths[row][col - 1] = weight + Table[row][col - 1]
                heappush(bfs_heap, (weight + Table[row][col - 1], row, col - 1))               
        if isValidSquare(row, col + 1, left_bound, right_bound) and not Visited[row][col + 1]:
            if weight + Table[row][col + 1] < Shortest_Paths[row][col + 1]:
                Shortest_Paths[row][col + 1] = weight + Table[row][col + 1]
                heappush(bfs_heap, (weight + Table[row][col + 1], row, col + 1))
                        

def processOnlyOneColumn(start_row, col_index):
    shortest_paths = [ sys.maxint for i in range(Row_Count) ]
    shortest_paths[start_row] = Table[start_row][col_index]
    
    weight = Table[start_row][col_index]
    for i in reversed(range(0, start_row)):
        weight = weight + Table[i][col_index]
        shortest_paths[i] = weight
    
    weight = Table[start_row][col_index]
    for i in range(start_row + 1, Row_Count):
        weight = weight + Table[i][col_index]
        shortest_paths[i] = weight
        
    return shortest_paths
    
    
def processQueriesByColumn(left_col, right_col, whole_queries):
    global Query_Results
        
    if not whole_queries:
        return

    if left_col  >= right_col:
        for query in whole_queries:
            query_indexes = whole_queries[query]
            paths = processOnlyOneColumn(query[0], left_col)
            new_min = min(Query_Results[query_indexes[0]], paths[query[2]])
            for q_index in query_indexes:
                Query_Results[q_index] = new_min
        return
    
    paths = []
    middle_col = (left_col + right_col) / 2
    for i in xrange(Row_Count):
        processSingleSquare(i, middle_col, left_col, right_col)
        for query in whole_queries:
            query_indexes = whole_queries[query]
            tmp_w = Shortest_Paths[query[0]][query[1]] + Shortest_Paths[query[2]][query[3]] - Table[i][middle_col]
            if tmp_w < Query_Results[query_indexes[0]]:
                for q_index in query_indexes:
                    Query_Results[q_index] = tmp_w
    
    queries_on_left = {}
    queries_on_right = {}
    for query in whole_queries:
        query_indexes = whole_queries[query]
        if query[3] < middle_col:
            queries_on_left[query] = query_indexes
        if query[1] > middle_col:
            queries_on_right[query] = query_indexes
                            
    processQueriesByColumn(left_col, middle_col - 1, queries_on_left)
    processQueriesByColumn(middle_col + 1, right_col, queries_on_right)
        
        
def printQueryResults():
    for q_result in Query_Results:
        print q_result
    
    
if __name__ == '__main__':
    readInput()
    processQueriesByColumn(0, Col_Count - 1, Query_Dict)
    printQueryResults()
c C# C++ HackerRank Solutions java javascript python