# HackerEarth Straightest path problem solution

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.

`#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 intusing 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 1002using 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("%d\n", ans);        return 0;}`