# HackerRank Find the Path problem solution

In this HackerRank Find the Path problem solution You must answer q queries. In each query, you are given the coordinates of two cells, (r1,c1) and (r2, c2). You must find and print the minimum possible weight of a path connecting them.

## Problem solution in Java.

```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);
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;

{
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);
}
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;
}
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;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#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;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <assert.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))

#define MAX_N 7
#define MAX_M 5000
#define LOG2_MAX_M 13
#define MAX_Q 30000
#define INFINITY INT_MAX

#define N(r, c) ((r) * (m) + (c))
#define ROW(n) ((n) / (m))
#define COL(n) ((n) % (m))

#define HEAP_KEY(pri, n) (((uint64_t)pri << 32) | n)
#define HEAP_PRI(key) ((int)(key >> 32))
#define HEAP_N(key) ((int)key)
#define PARENT(i) (((i) - 1) / 2)
#define LEFT(i) (2 * (i) + 1)
#define RIGHT(i) (2 * (i) + 2)

typedef uint64_t heap_type;

struct node {
int depth;
int left, mid, right;
struct node *child[2];
};
struct node *root;

static int n;
static int m;
static int q;
static int visited[MAX_N * MAX_M];
static int length[MAX_N * MAX_M];
static int dist[LOG2_MAX_M][MAX_N][MAX_N * MAX_M];

static heap_type queue[MAX_N * MAX_M * 4];
static int num_queue;

static inline void swap_node(heap_type *a, int x, int y) {
heap_type tmp = a[x];
a[x] = a[y];
a[y] = tmp;
}

static void sift_down(heap_type *a, int i, int size) {
while (1) {
int l = LEFT(i);
int r = RIGHT(i);
int min;

if (r >= size) {
if (l >= size) {
break;
}
min = l;
} else {
if (a[r] >= a[l]) {
min = l;
} else {
min = r;
}
}

if (a[min] >= a[i]) {
break;
}

swap_node(a, i, min);

i = min;
}
}

static void sift_up(heap_type *a, int i, int size) {
while (i) {
int p = PARENT(i);
if (a[p] <= a[i]) {
break;
}

swap_node(a, p, i);

i = p;
}
}

static void pop_heap(heap_type *a, int size) {
swap_node(a, 0, size-1);
sift_down(a, 0, size-1);
}

static void push_heap(heap_type *a, int size) {
sift_up(a, size-1, size);
}

static void dijkstra(struct node *s, int i, int begin) {
int *mind = dist[s->depth][i];
for (int r = 0; r < n; r++) {
for (int c = s->left; c <= s->right; c++) {
visited[N(r,c)] = 0;
mind[N(r,c)] = INFINITY;
}
}
num_queue = 0;
mind[begin] = length[begin];
queue[num_queue++] = HEAP_KEY(mind[begin], begin);
push_heap(queue, num_queue);

while (num_queue) {
pop_heap(queue, num_queue);
int u = queue[--num_queue];

visited[u] = 1;
static const int offsets[] = {
0, -1, 0, 1,
-1, 0, 1, 0
};

for (int j = 0; j < 4; j++) {
int vr = ROW(u) + offsets[j];
int vc = COL(u) + offsets[4+j];
if (vr < 0 || vr >= n || vc < s->left || vc > s->right) {
continue;
}
int v = N(vr, vc);

if (visited[v]) {
continue;
}

int alt = mind[u] + length[v];
if (alt < mind[v]) {
mind[v] = alt;
assert(num_queue < MAX_N * MAX_M * 4);
queue[num_queue++] = HEAP_KEY(alt, v);
push_heap(queue, num_queue);
}
}
}
}

void free_node(struct node *root) {
if (!root) {
return;
}

free_node(root->child[0]);
free_node(root->child[1]);
free(root);
}

struct node *alloc_node(int depth, int left, int right) {
struct node *s = calloc(sizeof(struct node), 1);
s->depth = depth;
s->left = left;
s->right = right;
s->mid = s->left + (s->right - s->left) / 2;
for (int i = 0; i < n; i++) {
dijkstra(s, i, N(i, s->mid));
}

return s;
}

int mind_r(struct node *s, int r1, int c1, int r2, int c2) {
int min = INT_MAX;
for (int i = 0; i < n; i++) {
int *mind = dist[s->depth][i];
int d = mind[N(r1, c1)] + mind[N(r2, c2)] - length[N(i, s->mid)];
min = MIN(min, d);
}
if (c1 <= s->mid && c2 >= s->mid) {
return min;
}
else if (c2 < s->mid) {
if (!s->child[0]) {
s->child[0] = alloc_node(s->depth+1, s->left, s->mid-1);
}
int lmin = mind_r(s->child[0], r1, c1, r2, c2);
return MIN(min, lmin);
} else {
if (!s->child[1]) {
s->child[1] = alloc_node(s->depth+1, s->mid+1, s->right);
}
int rmin = mind_r(s->child[1], r1, c1, r2, c2);
return MIN(min, rmin);
}
}

int mind(int r1, int c1, int r2, int c2) {
if (!root) {
root = alloc_node(0, 0, m-1);
}

return mind_r(root, r1, c1, r2, c2);
}

int main() {
scanf("%d %d", &n, &m);

for (int i = 0; i < n * m; i++) {
scanf("%d", &length[i]);
}

int q;
scanf("%d", &q);

for (int i = 0; i < q; i++) {
int r1, c1, r2, c2;
scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
if (c1 > c2) {
int tmp = r1;
r1 = r2;
r2 = tmp;
tmp = c1;
c1 = c2;
c2 = tmp;
}

printf("%d\n", mind(r1, c1, r2, c2));
}
free_node(root);

return 0;
}
```

{"mode":"full","isActive":false}