998. Check if There is a Valid Path in Grid

Given an m x n grid where each cell holds a street type 1-6 (1: west-east, 2: north-south, 3: west-south, 4: east-south, 5: west-north, 6: east-north), determine whether there is a valid path from the top-left cell to the bottom-right cell, where two adjacent cells connect only if both streets point toward each other. Return true or false. The input is JSON {grid}.

Input: JSON {grid}.

Output: Boolean — true or false.

Examples

Input: {"grid":[[2,4,3],[6,5,2]]}
Output: true
Explanation: A connected street path exists.

Input: {"grid":[[1,2,1],[1,2,1]]}
Output: false
Explanation: Streets do not link end to end.

Input: {"grid":[[2]]}
Output: true
Explanation: Start equals end.

Constraints

• 1<=rows,cols<=300
• street types 1-6

Asked by