Straightest path | Editorial by aksingh007

The problem boils down to finding the minimum number of turns while traveling from one position to other in the given grid. 
Let turns[i][j][k] denote the minimum number of turns required to reach cell (i, j) given that you were moving in either of the four direction
i.e (RIGHT, LEFT, UP, DOWN).

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

Straightest path | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?