Leetcode每日一题 —— 1391. 检查网格中是否存在有效路径

1391. 检查网格中是否存在有效路径 - 力扣（LeetCode）

1391. 检查网格中是否存在有效路径 - 给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是： * 1 表示连接左单元格和右单元格的街道。 * 2 表示连接上单元格和下单元格的街道。 * 3 表示连接左单元格和下单元格的街道。 * 4 表示连接右单元格和下单元格的街道。 * 5 表示连接左单元格和上单元格的街道。 * 6...

思路

大体上其实和昨天的思路比较相近，同样可以用并查集，扫描网格时也同样可以从上至下、从左至右扫描，对于每个格子都尝试往下或者往右走以进行合并。

和之前题不同的地方就在于，这题限制了每个格子处的行进方向。

咱的做法是建立了一个硬编码的 patterns 表来表示向右或者向下走时，某个编号的街道是否能走向另一个编号的街道。这样能防止代码写得太复杂。

代码

class Solution {
public:
    bool hasValidPath(vector<vector<int>>& grid) {
        // 这题还挺有意思，其实就是限定了每个格子处的行进方向
        // 依旧可以并查集解决
        int m=grid.size(),n=grid[0].size();
        int ufLen=m*n;
        vector<int> parents(ufLen,-1),sizes(ufLen,1);

        auto find=[&](auto&& self, int x) -> int {
            return parents[x]==-1 ? x : parents[x]=self(self,parents[x]);
        };

        auto merge=[&](int x1,int x2) -> void {
            int root1=find(find,x1),root2=find(find,x2);
            if(root1==root2){
                // 已经合并
                return;
            }
            // 小树并入大树
            if(sizes[root1]<sizes[root2]){
                swap(root1,root2);
            }
            parents[root2]=root1;
            sizes[root1]+=sizes[root2];
        };

        // 扫描网格，依旧看每个格子向下或者向右能不能走
        int drcts[][2]={
            {0,1},
            {1,0},
        };
        // patterns[i][j][k]
        // i 表示尝试行进方向（右 i=0, 下 i=1）
        // j+1 表示当前格子的街道编号
        // k+1 表示行进后的街道编号
        // 如果 patterns[i][j][k]=true 就说明能走
        bool patterns[2][6][6]={
            {
                {true,false,true,false,true,false},
                {false,false,false,false,false,false}, // 街道 2 无法往右走
                {false,false,false,false,false,false},
                {true,false,true,false,true,false},
                {false,false,false,false,false,false},
                {true,false,true,false,true,false},
            },
            {
                {false,false,false,false,false,false}, // 街道 1 无法往下走
                {false,true,false,false,true,true},
                {false,true,false,false,true,true},
                {false,true,false,false,true,true},
                {false,false,false,false,false,false},
                {false,false,false,false,false,false},
            },
        };
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<2;k++){
                    int nextI=i+drcts[k][0],nextJ=j+drcts[k][1];
                    // 没有越界的话就判断能不能往这个方向走，如果可以就合并
                    if(nextI>=m||nextJ>=n||!patterns[k][grid[i][j]-1][grid[nextI][nextJ]-1]){
                        continue;
                    }
                    merge(i*n+j,nextI*n+nextJ);
                }
            }
        }
        // 最后判断首个和最后一个是否连通
        return find(find,0) == find(find, ufLen-1);
    }
};

1 个帖子 - 1 位参与者

阅读完整话题