1391. Check if There is a Valid Path in a Grid

题目信息

题号:

1391

难度:

Medium

主题:

网格、图搜索、连通方向

原题:

LeetCode 1391

重点:

六种街道类型分别连接固定方向;相邻两格只有接口方向互相匹配时才能通行

题目重述

给定街道网格 grid,每个整数 1 到 6 表示一种固定连接方向的街道。需要从左上角出发,沿街道连接移动到右下角。

两格相邻并不自动连通:当前格朝目标方向有出口,目标格也必须朝当前方向有接口。不能旋转或修改街道。请判断是否存在合法路径。

1 <= grid.length, grid[i].length <= 300。

自建示例

相邻街道接口逐步匹配:

输入:grid = [[1,3],[6,2]]
输出:true
解释:左上角类型 1 向右连接类型 3,类型 3 再向下连接终点的类型 2。

接口方向不匹配时无法通行:

输入:grid = [[1,2]]
输出:false
解释:类型 1 向右有出口,但类型 2 只有上下接口,没有左接口。