检查网格中是否存在有效路径 图解题解

从左上角能不能顺着街道走到右下角

给一个 m 行 n 列的网格 grid，每格写着 1 到 6 的编号，每个编号是一段只朝两个固定方向开口的街道：1 连左右，2 连上下，3 连左下，4 连右下，5 连左上，6 连右上。人从左上角 (0,0) 出发，只能顺着开口走，街道不能旋转，问能不能走到右下角 (m-1,n-1)，能就返回 true、不能返回 false。

照着街道模拟走路，麻烦在哪

想直接照着走一遍：从起点沿开口挪到邻居，再接着挪，撞墙就退回来换方向。麻烦在于判断这两格到底连不连——不是挨着就能过，得当前格朝邻居有开口、邻居也朝回来有开口，两边都敞着才算一条能过的缝。

只问起点终点连不连，用并查集

题目只问起点和右下角连不连得上，并不要求把路线画出来。「谁和谁归到一块」用并查集来管——把连通的格子并成一堆，往后查两个格子在不在同一堆几乎一步到位。把每格看成一个点，扫一遍相邻格，互相敞口就并到一起，最后看左上角和右下角在不在同一堆。

六个编号各朝哪两边，怎么两两对接

连边的规矩只有一条：相邻两格，各自朝对方的方向都有开口。先把编号按开口方向理一遍：朝左开的是 1、3、5，朝右开的是 1、4、6，朝上开的是 2、5、6，朝下开的是 2、3、4，同一个编号会落进两组，因为它本就朝两个方向开。扫到某格只看它开口的两个方向：朝右开就查右邻居在不在朝左开那组，在就并起来；朝下开就查下邻居在不在朝上开那组。左邻、上邻不必自己查——并查集连通是双向的，它们轮到自己时会朝右、朝下回查，每格只管右、下两向，不漏也不重。每格最多两次对接，一趟扫完能连的缝都并好。

拿题面这组网格把格子并成几堆

拿题面 grid=[[2,4,3],[6,5,2]] 走一遍，格子按（行，列）记。(0,0) 是 2、上下开，上面出界，下邻 (1,0) 是 6、朝上开，接上。(0,1) 是 4、右下开：右邻 (0,2) 是 3、朝左开，下邻 (1,1) 是 5、朝上开，都并上，(0,1) (0,2) (1,1) 成一堆。(0,2) 朝下的 (1,2) 是 2、朝上开，收进这堆。再看 (1,0)，它朝右的 (1,1) 朝左开，一并，(0,0) (1,0) 就和这一大堆接上，六格归一堆。最后查 (0,0) 和 (1,2) 同一堆，返回 true，起点确实通到了终点。

跑多快，单格和走不通各返回什么

外层双重循环扫 m 乘 n 个格子，每格最多两次合并，带路径压缩的查根摊还几乎是常数，时间 O(m·n·α)——α 随规模增长极慢、可当常数看；再加一个父数组记归属，空间 O(m·n)。

网格只剩一格时，左上角就是右下角，天然同堆，直接返回 true，这种起点即终点别漏判。题面例二 grid=[[1,2,1],[1,2,1]] 是另一头：起点 (0,0) 是 1、只朝左右开，左边出界，右邻 (0,1) 是 2、只朝上下开、并不朝左回敞口，(0,0) 一条能并的缝都找不到，孤零零留在那堆，终点接不进来，返回 false。这也点出最爱犯的错：当前格朝邻居开就放行、不管邻居朝没朝回来，走不通的相邻格会被误当连通。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        p = list(range(m * n))

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        def left(i, j):
            if j > 0 and grid[i][j - 1] in (1, 4, 6):
                p[find(i * n + j)] = find(i * n + j - 1)

        def right(i, j):
            if j < n - 1 and grid[i][j + 1] in (1, 3, 5):
                p[find(i * n + j)] = find(i * n + j + 1)

        def up(i, j):
            if i > 0 and grid[i - 1][j] in (2, 3, 4):
                p[find(i * n + j)] = find((i - 1) * n + j)

        def down(i, j):
            if i < m - 1 and grid[i + 1][j] in (2, 5, 6):
                p[find(i * n + j)] = find((i + 1) * n + j)

        for i in range(m):
            for j in range(n):
                e = grid[i][j]
                if e == 1:
                    left(i, j)
                    right(i, j)
                elif e == 2:
                    up(i, j)
                    down(i, j)
                elif e == 3:
                    left(i, j)
                    down(i, j)
                elif e == 4:
                    right(i, j)
                    down(i, j)
                elif e == 5:
                    left(i, j)
                    up(i, j)
                else:
                    right(i, j)
                    up(i, j)
        return find(0) == find(m * n - 1)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> p;

    bool hasValidPath(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        p.resize(m * n);
        for (int i = 0; i < p.size(); ++i) p[i] = i;
        auto left = [&](int i, int j) {
            if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
                p[find(i * n + j)] = find(i * n + j - 1);
            }
        };
        auto right = [&](int i, int j) {
            if (j < n - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
                p[find(i * n + j)] = find(i * n + j + 1);
            }
        };
        auto up = [&](int i, int j) {
            if (i > 0 && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
                p[find(i * n + j)] = find((i - 1) * n + j);
            }
        };
        auto down = [&](int i, int j) {
            if (i < m - 1 && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
                p[find(i * n + j)] = find((i + 1) * n + j);
            }
        };
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int e = grid[i][j];
                if (e == 1) {
                    left(i, j);
                    right(i, j);
                } else if (e == 2) {
                    up(i, j);
                    down(i, j);
                } else if (e == 3) {
                    left(i, j);
                    down(i, j);
                } else if (e == 4) {
                    right(i, j);
                    down(i, j);
                } else if (e == 5) {
                    left(i, j);
                    up(i, j);
                } else {
                    right(i, j);
                    up(i, j);
                }
            }
        }
        return find(0) == find(m * n - 1);
    }

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
};

Java

import java.util.*;
class Solution {
    private int[] p;
    private int[][] grid;
    private int m;
    private int n;

    public boolean hasValidPath(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        p = new int[m * n];
        for (int i = 0; i < p.length; ++i) {
            p[i] = i;
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int e = grid[i][j];
                if (e == 1) {
                    left(i, j);
                    right(i, j);
                } else if (e == 2) {
                    up(i, j);
                    down(i, j);
                } else if (e == 3) {
                    left(i, j);
                    down(i, j);
                } else if (e == 4) {
                    right(i, j);
                    down(i, j);
                } else if (e == 5) {
                    left(i, j);
                    up(i, j);
                } else {
                    right(i, j);
                    up(i, j);
                }
            }
        }
        return find(0) == find(m * n - 1);
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    private void left(int i, int j) {
        if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
            p[find(i * n + j)] = find(i * n + j - 1);
        }
    }

    private void right(int i, int j) {
        if (j < n - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
            p[find(i * n + j)] = find(i * n + j + 1);
        }
    }

    private void up(int i, int j) {
        if (i > 0 && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
            p[find(i * n + j)] = find((i - 1) * n + j);
        }
    }

    private void down(int i, int j) {
        if (i < m - 1 && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
            p[find(i * n + j)] = find((i + 1) * n + j);
        }
    }
}