Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Straightest path problem solution

YASH PAL, 31 July 2024
In this HackerEarth Straightest path problem solution You are playing a game on a grid of size N X M. The game has the following rules:
  • The grid contains cells that the player can move to. These are denoted by a period (.)
  • The grid contains cells that the player cannot move to. These are denoted by an asterisk (*)
  • The player starts on the cell marked with a V.
  • The player has to reach the cell marked with an H.
Write a program to find the path which has the minimum number of changes in direction. Print the number of times that the player needs to turn on the path
HackerEarth Straightest path problem solution

HackerEarth Straightest path problem solution.

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<bitset>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fio ios_base::sync_with_stdio(false)
#define mod 1000000007
#define mod1 mod
#define mod2 100000009
#define li long long int
#define ll int
#define readi(x) scanf("%d",&x)
#define reads(x) scanf("%s", x)
#define readl(x) scanf("%I64d",&x)
#define rep(i,n) for(i=0;i<n;i++)
#define revp(i,n) for(i=(n-1);i>=0;i--)
#define myrep1(i,a,b) for(i=a;i<=b;i++)
#define myrep2(i,a,b) for(i=b;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define MAXN 100000000000100
#define MINN -10000000000000
#define pii pair<ll,ll>
#define pic pair<int,char>
#define N 2000010
#define lgn 20
#define ddouble long double
#define minus minu
#define INTMAX 10000000
// #define si short int
using namespace std;
using namespace __gnu_pbds;
typedef priority_queue<pair<ll,pii> , vector<pair<ll , pii> > > max_pq;
typedef priority_queue<pair < ll , pair < pii , ll > > , vector<pair < ll , pair < pii , ll > > > ,greater<pair < ll , pair < pii , ll > > > > min_pq;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> OST;

min_pq pq;

ll dist[2000][2000][4];

char c[2000][2000];

ll n , m;

int main()
{
ios::sync_with_stdio(false);

// freopen("hackerearthinput.txt","r",stdin);
// freopen("hackerearthoutput.txt","w",stdout);

cin >> n >> m;

ll si, sj, ti, tj;

for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
cin >> c[i][j];
if ( c[i][j]=='V')
{
si=i;
sj=j;
}
if ( c[i][j]=='H')
{
ti=i;
tj=j;
}
for (ll k=0;k<4;k++)
dist[i][j][k] = INT_MAX;
}
}

// 0 up
// 1 right
// 2 down
// 3 left

if ( si -1 >=1 && c[si-1][sj]!='*')
{
pq.push ( mp( 0, mp( mp( si-1,sj ),0)));
}
if ( sj +1 <=m && c[si][sj+1]!='*')
{
pq.push ( mp( 0, mp( mp( si,sj + 1 ),1)));
}
if ( si +1 <=n && c[si+1][sj]!='*')
{
pq.push ( mp( 0, mp( mp( si+1,sj ),2)));
}
if ( sj -1 >=1 && c[si][sj-1]!='*')
{
pq.push ( mp( 0, mp( mp( si,sj - 1),3)));
}

while ( ! pq.empty())
{
ll x = pq.top().sec.fi.fi;
ll y = pq.top().sec.fi.sec;
ll d = pq.top().fi;
ll dir = pq.top().sec.sec;
pq.pop();

if ( dist [x][y][dir] >d)
{
dist[x][y][dir]=d;
if ( x -1 >=1 && c[x-1][y]!='*')
{
ll s = 0;
pq.push ( mp( d +( dir !=s ) , mp( mp( x-1,y ),s)));
}
if ( y +1 <=m && c[x][y+1]!='*')
{
ll s =1;
pq.push ( mp(d +( dir !=s ) , mp( mp( x,y + 1 ),1)));
}
if ( x +1 <=n && c[x+1][y]!='*')
{
ll s =2;
pq.push ( mp( d +( dir !=s ), mp( mp( x+1,y ),2)));
}
if ( y -1 >=1 && c[x][y-1]!='*')
{
ll s = 3;
pq.push ( mp( d +( dir !=s ), mp( mp( x,y - 1),3)));
}

}

}


if ( dist[ti][tj][0]==INT_MAX && dist[ti][tj][1]==INT_MAX && dist[ti][tj][2]==INT_MAX && dist[ti][tj][3]==INT_MAX )
{
cout<<"-1";
}
else
{
cout<<min(dist[ti][tj][0],min(dist[ti][tj][1],min ( dist[ti][tj][2], dist[ti][tj][3]) ) ) ;
}

}

Second solution

#include <bits/stdc++.h>
#define MAX 1002

using namespace std;

char s[MAX][MAX];
int n, m;

int dx[] = {1, 0,-1, 0};
int dy[] = {0, 1, 0, -1};
int dis[MAX][MAX][4];

bool valid(int x, int y)
{
if ( x < 0 || y < 0 || x >= n || y >= m ) return false;
if ( s[x][y] == '*' ) return false;
return true;

}

struct node {
int x, y, dir;
node() { }
node(int x, int y, int dir) {
this->x = x, this->y = y, this->dir = dir;
}
};

int main()
{
int sx, sy, ex, ey, cnt1 = 0, cnt2 = 0;

scanf("%d%d", &n, &m);
assert(n >= 1 && n <= 1000);
assert(m >= 1 && m <= 1000);

for ( int i = 0; i < n; i++ ) {
scanf("%s", s[i]);
for ( int j = 0; j < m; j++ ) {
assert(s[i][j] == 'V' || s[i][j] == '*' || s[i][j] == 'H' || s[i][j] == '.');
for ( int k = 0; k < 4; k++ ) dis[i][j][k] = -1;
if ( s[i][j] == 'V' ) {
sx = i, sy = j;
cnt1++;
}
else if ( s[i][j] == 'H' ) {
ex = i, ey = j;
cnt2++;
}
}
}

assert(cnt1 == 1 && cnt2 == 1);

queue <node> q;

for ( int k = 0; k < 4; k++ ) {
dis[sx][sy][k] = 0;
q.push(node(sx, sy, k));
}

while ( !q.empty() ) {
node f = q.front();
q.pop();
for ( int k = 0; k < 4; k++ ) {
int new_x = f.x + dx[k];
int new_y = f.y + dy[k];
if ( valid(new_x, new_y) ) {
if ( dis[new_x][new_y][k] == -1 || dis[new_x][new_y][k] > dis[f.x][f.y][f.dir] + (f.dir != k) ) {
dis[new_x][new_y][k] = dis[f.x][f.y][f.dir] + (f.dir != k);
q.push(node(new_x, new_y, k));
}
}
}
}

int ans = -1;


for ( int k = 0; k < 4; k++ ) {
if ( dis[ex][ey][k] == -1 ) continue;
if ( ans == -1 || ans > dis[ex][ey][k] ) ans = dis[ex][ey][k];
}

printf("%dn", ans);

return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes