HackerEarth Straightest path problem solution

YASH PAL,
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