Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
thecscience
THECSICENCE

Learn everything about computer science

HackerRank Find the Path Problem Solution

Yashwant Parihar, May 21, 2023May 28, 2024

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 CcppCSharpHackerrank Solutionsjavajavascriptpython

Post navigation

Previous post
Next post
  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 THECSICENCE | WordPress Theme by SuperbThemes