Shortest Path Length - Ascending Order

 Shortest Path Length - Ascending Order 

PROBLEM STATEMENT :

The program must accept an integer matrix of size R*C as the input. The matrix contains at least two consecutive non-zero digits starting from 1. The remaining elements in the matrix are 0s. The program must print the length of the shortest path that starts at 1 and goes over all the other non-zero digits in ascending order. Only horizontal and vertical movements are allowed. 

Boundary Condition(s): 

2 <= R, C <= 50 

Input Format: 

The first line contains R and C separated by a space. 

The next R lines, each contains C integer values separated by a space. 

Output Format: 

The first line contains the length of the shortest path. 

Example Input/Output 1: 
Input: () 
6 6 
0 0 4 0 0 0 
0 0 0 0 1 0 
0 0 0 2 0 0 
0 0 0 0 0 3 
0 0 0 0 0 0 
0 0 0 0 0 0 
Output: 
11 

Explanation: 

The minimum distance between 1 and 2 is 2. 

The minimum distance between 2 and 3 is 3. 

The minimum distance between 3 and 4 is 6. 

The length of the shortest path from 1 to 4 is 11 (2 + 3 + 6). 

Example Input/Output 2: 
Input: () 
8 5 
0 0 0 0 0 
0 0 0 6 0 
0 1 0 0 0 
0 2 0 7 0 
3 0 0 0 0 
0 0 0 4 0 
0 0 0 0 5 
0 0 0 0 0 
Output: 
17

---

SOLUTION :

C (Programming Language)

      
#include<stdio.h>
#include<stdlib.h>

int main()
{
    int r,c;
    scanf("%d %d",&r,&c);
    int a[r][c],hashi[3000]={-1},hashj[3000]={-1},ma=0,ans=0;
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]!=0)
            {
                int x=a[i][j]-1;
                hashi[x]=i;
                hashj[x]=j;
                if(a[i][j]>ma)
                {
                    ma=a[i][j];
                }
            }
        }
    }
    
    for(int i=0;i<ma-1;i++)
    {
        ans+=abs(hashi[i]-hashi[i+1])+abs(hashj[i]-hashj[i+1]);
    }
    printf("%d",ans);
}
 

C++ (CPP)

       
#include <bits/stdc++.h>
 
using namespace std;

int main(int argc, char** argv)
{
int mat[50][50];
int r,c;
cin>>r>>c;
map<int,pair<int,int>> pos;
for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
        cin>>mat[i][j];
        if(mat[i][j]!=0)
        pos[mat[i][j]] = {i,j};
    }
}

int sum =0;
for(int i=0;i<pos.size()-1;i++){
    pair<int,int> fPair = pos[i+1];
    pair<int,int> sPair= pos[i+2];
    
    int c = std::abs(fPair.second - sPair.second );
    int r = std::abs(fPair.first - sPair.first);
    sum+= (c+r);
}

cout<<sum;
}
 

JAVA

       
import java.util.*;
public class Hello {

    public static void main(String[] args) {
		//Your Code Here
		Scanner scan=new Scanner(System.in);
		int r=scan.nextInt();
		int c=scan.nextInt();
		int max=1;
		HashMap<Integer,ArrayList<Integer>> hm=new HashMap<>();
		for(int i=0;i<r;i++)
		{
		    for(int j=0;j<c;j++)
		    {
		        int t=scan.nextInt();
		        if(t!=0)
		        {
		            ArrayList<Integer> ar=new ArrayList<>();
		            ar.add(i);
		            ar.add(j);
		            hm.put(t,ar);
		            max=Math.max(t,max);
		        }
		    }
		}
		int ans=0;
		for(int i=1;i<max;i++)
		{
		    ArrayList<Integer> ar1=hm.get(i);
		    ArrayList<Integer> ar2=hm.get(i+1);
		    for(int j=0;j<2;j++)
		    ans+=Math.max(ar1.get(j),ar2.get(j))-Math.min(ar1.get(j),ar2.get(j));
		}
		System.out.print(ans);
	}
}
 

PYTHON

       
r,c=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(r)]
d=dict();s=0
for i in range(r):
    for j in range(c):
        if l[i][j]!=0:
            d[l[i][j]]=[i,j]
for i in range(2,len(d)+1):
    shortestDistance=abs(d[i][0]-d[i-1][0])+abs(d[i][1]-d[i-1][1])
    s+=shortestDistance
print(s)
 

Never Stop Learning !!