Check if There is a Valid Path in a Grid

Given a m x n grid. Each cell of the grid represents a street. The street of grid[i][j] can be:

• 1 which means a street connecting the left cell and the right cell.
• 2 which means a street connecting the upper cell and the lower cell.
• 3 which means a street connecting the left cell and the lower cell.
• 4 which means a street connecting the right cell and the lower cell.
• 5 which means a street connecting the left cell and the upper cell.
• 6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path that starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Approach:

C++

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

map<int, vector<pair<int, int>>> ways;
int rows, cols;
vector<bool> vis;

bool check(int x, int y, int nx, int ny, int value)
{
    vector<pair<int,int>> w=ways[value];
    for(int i=0;i<w.size();i++)
      {
          if(nx+w[i].first==x&&ny+w[i].second==y)
            {
                return true;
            }
      }
 
    return false;
}
bool dfs(int x, int y, vector<vector<int>> &grid)
{
    if (x == rows - 1 && y == cols - 1)
        return true;
    int value = grid[x][y];
    vector<pair<int,int>> w=ways[value];

    for(int i=0;i<w.size();i++)
    { 
  
        int nx = w[i].first + x, ny = w[i].second + y;
        if (nx >= 0 && ny >= 0 && nx < rows && ny < cols 
    && !vis[nx * cols + ny] && check(x, y, nx, ny, grid[nx][ny]))
        {
            vis[nx * cols + ny] = true;
            if (dfs(nx, ny, grid))
                return true;
        }
    }
    return false;
}

bool hasValidPath(vector<vector<int>> &grid)
{
    rows = grid.size();
    if (rows == 0)
        return true;
    cols = grid[0].size();
    ways[1] = {{0, -1}, {0, 1}};
    ways[2] = {{-1, 0}, {1, 0}};
    ways[3] = {{0, -1}, {1, 0}};
    ways[4] = {{1, 0}, {0, 1}};
    ways[5] = {{0, -1}, {-1, 0}};
    ways[6] = {{-1, 0}, {0, 1}};
    vis.resize(rows * cols + 1);
    return dfs(0, 0, grid);
}

int main()
{
    vector<vector<int>> grid = {{2, 4, 3}, {6, 5, 2}};

    if (hasValidPath(grid))
        cout << "true";
    else
        cout << "false";

    return 0;
}