• Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
Friday, January 27, 2023
  • Login
Zeroplusfour
No Result
View All Result
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
No Result
View All Result
Zeroplusfour
No Result
View All Result
Home Code Solutions Hackerrank Algorithms

Find the Path – HackerRank Solution

Find the Path - HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

bhautik bhalala by bhautik bhalala
May 26, 2022
Reading Time: 1 min read
0
15 Days to learn SQL Hard SQL(Advanced)-Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution alt text

Spread the love

Table of Contents

  • Find the Path  – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
  • Solutions of Algorithms Data Structures Hard HackerRank:
    • Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
  • C++ Find the Path HackerRank Solution
  • Java Find the Path HackerRank Solution
  • Python 3 Find the Path HackerRank Solution
  • Python 2 Find the Path HackerRank Solution
  • C Find the Path  HackerRank Solution
    • Leave a comment below
      • Related posts:

Find the Path  – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

Solutions of Algorithms Data Structures Hard HackerRank:

Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts

C++ Find the Path HackerRank Solution


Copy Code Copied Use a different Browser

#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;
		}
		// cout << r << " " << c << endl;
		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;
	// cout << l << " " << r << " " << mid << endl;
	for (int i = 0; i < N; ++i) {
		SPs[i][mid] = make_pair(l, dijk(i, mid, l, r));
		// cout << i << endl;
		// for (auto& v : SPs[i][mid].second) {
		// 	for (int d : v) {
		// 		cout << d << " ";
		// 	}
		// 	cout << endl;
		// }
	}
	vector<int> Qls, Qrs;
	for (int i : Qis) {
		// cout << ": ";
		// for (int q : Qs[i]) {
		// 	cout << q << " ";
		// }
		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 {
			// cout << " *";
			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];
					// if ((Qs[i][0] == j && Qs[i][1] == mid) || (Qs[i][2] == j && Qs[i][3] == mid))
					// 	d -= G[j][mid];
					ans[i] = min(ans[i], d);
				}
			}
		}
		// cout << endl;
	}
	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;
}

Java Find the Path HackerRank Solution


Copy Code Copied Use a different Browser

 

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



Python 3 Find the Path HackerRank Solution


Copy Code Copied Use a different Browser

#!/bin/python3

import sys
from collections import deque
from math import inf
from heapq import heappush, heappop

def shortestPath (matrix, query, numRows, numCols):  # Breadth First Search
    start = (query[0],query[1])
    goal = (query[2],query[3])
    pathWeight = matrix[start]
    pathQueue = []
    heappush(pathQueue, [pathWeight, start[0], start[1]])
    seen = {start:pathWeight}
    minWeight = inf
    while pathQueue:
        pathCell = heappop(pathQueue)
        row, col = (pathCell[1], pathCell[2])
        pathWeight = pathCell[0]
        if (row, col) == goal:
            if pathWeight < minWeight:
                minWeight = pathWeight
            continue
        if pathWeight >= minWeight:
            continue        
        for newRow, newCol in ((row+1,col), (row-1,col), (row,col+1), (row,col-1)):
            if 0 <= newRow < numRows and 0 <= newCol < numCols:
                newPathWeight = pathWeight + matrix [(newRow,newCol)]
                if (newRow,newCol) in seen:
                    if seen[(newRow, newCol)] <= newPathWeight:
                        continue
                heappush(pathQueue, [newPathWeight, newRow, newCol])
                seen[(newRow, newCol)] = newPathWeight
    return minWeight

if __name__ == "__main__":
    m, n = input().strip().split(' ')
    m, n = [int(m), int(n)]
    matrix = {}
    for matrixRow in range(m):
        matrixRowList = [int(weight) for weight in input().strip().split(' ')]
        for matrixCol in range(n):
            matrix[(matrixRow,matrixCol)] = matrixRowList[matrixCol]
    q = int(input().strip())
    for queries in range(q):
        query = [int(query_temp) for query_temp in input().strip().split(' ')]
        print(shortestPath(matrix, query, m, n))



Python 2 Find the Path HackerRank Solution


Copy Code Copied Use a different Browser

# 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 Find the Path  HackerRank Solution


Copy Code Copied Use a different Browser

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

    // sift up until parent is less than node
    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];

  // reset state
  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;

  // seed queue
  mind[begin] = length[begin];
  queue[num_queue++] = HEAP_KEY(mind[begin], begin);
  push_heap(queue, num_queue);

  while (num_queue) {
    // pop node with shortest path
    pop_heap(queue, num_queue);
    int u = queue[--num_queue];

    visited[u] = 1;

    // visit adjacent children
    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];

      // ignore out of bounds children
      if (vr < 0 || vr >= n || vc < s->left || vc > s->right) {
        continue;
      }

      // ignore children which have already been visited
      int v = N(vr, vc);

      if (visited[v]) {
        continue;
      }

      int alt = mind[u] + length[v];
      if (alt < mind[v]) {
        mind[v] = alt;

        // push new element to queue
        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;

  // compute dijkstra for all all rows along the middle line
  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 the query crossed the middle, this is absolutely the shortest path
  if (c1 <= s->mid && c2 >= s->mid) {
    return min;
  }
  // else, there may be a shorter path in one of the children
  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);

    // keep begin to the left of end
    if (c1 > c2) {
      int tmp = r1;
      r1 = r2;
      r2 = tmp;
      tmp = c1;
        c1 = c2;
      c2 = tmp;
    }

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

  // cleanup
  free_node(root);

  return 0;
}

 

Leave a comment below

 

Related posts:

15 Days to learn SQL Hard SQL(Advanced)-SolutionSimilar Pair – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionCounting Sort 1 – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionRecursive Digit Sum – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionLego Blocks – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionCoprime Paths – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMatrix – HackerRank Solution
Tags: Cc++14Find the Pathfull solutionGoHackerRank Solutionjavajava 15java 7java 8java8javascriptpypy 3Python 2python 3
ShareTweetPin
bhautik bhalala

bhautik bhalala

Related Posts

Leetcode All Problems Solutions
Code Solutions

Exclusive Time of Functions – LeetCode Solution

by admin
October 5, 2022
0
29

Exclusive Time of Functions - LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions...

Read more
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
32
Leetcode All Problems Solutions

Course Schedule III – LeetCode Solution

October 5, 2022
25
Leetcode All Problems Solutions

Maximum Product of Three Numbers – LeetCode Solution

September 11, 2022
52
Leetcode All Problems Solutions

Task Scheduler – LeetCode Solution

September 11, 2022
119
Leetcode All Problems Solutions

Valid Triangle Number – LeetCode Solution

September 11, 2022
28
Next Post
15 Days to learn SQL Hard SQL(Advanced)-Solution

Savita And Friends - HackerRank Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution

Liars - HackerRank Solution

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

You may also like

15 Days to learn SQL Hard SQL(Advanced)-SolutionSimilar Pair – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionCounting Sort 1 – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionRecursive Digit Sum – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionLego Blocks – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionCoprime Paths – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionMatrix – HackerRank Solution

Categories

  • Algorithms
  • Anime
  • Biography
  • Business
  • Code Solutions
  • Cosmos
  • Countdowns
  • Culture
  • Economy
  • Education
  • Entertainment
  • Finance
  • Games
  • Hackerrank
  • Health
  • How to
  • Investment
  • LeetCode
  • Lifestyle
  • LINUX SHELL
  • Manga
  • News
  • Opinion
  • Politics
  • Sports
  • SQL
  • Tech
  • Travel
  • Uncategorized
  • Updates
  • World
  • DMCA
  • Home
  • My account
  • Privacy Policy
  • Top Posts

Recent Blogs

Leetcode All Problems Solutions

Exclusive Time of Functions – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
My Hero Academia Chapter 365 Raw Scan
Anime

My Hero Academia Chapter 365 Raw Scan BNHA Spoilers: Bakugo Still Alive?

August 30, 2022
117
Free Fire MAX OB34 update APK release date and time in India server
Games

Free Fire MAX OB34 APK update release date and time in India server

May 25, 2022
9
Leetcode All Problems Solutions
Code Solutions

Super Ugly Number – LeetCode Solution

September 6, 2022
43
Leetcode All Problems Solutions
Code Solutions

Spiral Matrix – LeetCode Solution

September 3, 2022
224

© 2022 ZeroPlusFour - Latest News & Blog.

No Result
View All Result
  • Home
  • Category
    • Business
    • Culture
    • Economy
    • Lifestyle
    • Health
    • Travel
    • Opinion
    • Politics
    • Tech
  • Landing Page
  • Support Forum
  • Contact Us

© 2022 ZeroPlusFour - Latest News & Blog.

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept All”, you consent to the use of ALL the cookies. However, you may visit "Cookie Settings" to provide a controlled consent.
Cookie SettingsAccept All
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT
Are you sure want to unlock this post?
Unlock left : 0
Are you sure want to cancel subscription?