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);
}
};
网友解答：
--【壹】--：
type Street = Int
neighbor :: (Int, Int) -> Int -> Street -> [Int]
neighbor (m, n) x street =
let (r, c) = x `divMod` n
candidates = case street of
1 -> [(r, c + 1), (r, c - 1)] -- LR
2 -> [(r + 1, c), (r - 1, c)] -- UD
3 -> [(r, c - 1), (r + 1, c)] -- LD
4 -> [(r, c + 1), (r + 1, c)] -- RD
5 -> [(r, c - 1), (r - 1, c)] -- LU
6 -> [(r, c + 1), (r - 1, c)] -- RU
_ -> []
in mapMaybe (toIdx (m, n)) candidates
toIdx :: (Int, Int) -> (Int, Int) -> Maybe Int
toIdx (m, n) (r, c) =
guard (0 <= r && r < m && 0 <= c && c < n) $> (r * n + c)
hasValidPath :: [[Street]] -> Bool
hasValidPath grid = isLeft $ runExcept (evalStateT (dfs 0) mempty)
where
m = length grid
n = length $ head $ fromList grid
terminal = m * n - 1
neighbors = V.map (uncurry $ neighbor (m, n)) $ V.fromList $ zip [0 ..] $ concat grid
adjs = V.generate (m * n) $ \i -> filter (\a -> i `elem` (neighbors V.! a)) (neighbors V.! i)
dfs curr =
when (curr == terminal) (throwError ())
*> modify' (IS.insert curr)
*> for_ (adjs V.! curr) (unlessM <$> (gets . IS.member) <*> dfs)
先算有向图，过滤出无向子图再dfs，如果原地改状态疑似会把向量搞进老年代反而让性能下降
--【贰】--：
from typing import List
class Solution:
def hasValidPath(self, grid: List[List[int]]) -> bool:
d = {
1: ((0, -1), (0, 1)),
2: ((-1, 0), (1, 0)),
3: ((0, -1), (1, 0)),
4: ((0, 1), (1, 0)),
5: ((0, -1), (-1, 0)),
6: ((0, 1), (-1, 0)),
}
m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
def dfs(i, j):
if i == m - 1 and j == n - 1:
return True
vis[i][j] = True
for di, dj in d[grid[i][j]]:
ii, jj = i + di, j + dj
if 0 <= ii < m and 0 <= jj < n and not vis[ii][jj]:
if (-di, -dj) in d[grid[ii][jj]]:
if dfs(ii, jj):
return True
return False
return dfs(0, 0)
--【叁】--：
存下每个点的俩方向，直接从起点做一个bfs。
给负值表示走过，省点空间同时也能保持记忆。
bfs到下一个点时，确保不越界且没走过的同时，下一个点再探下一个点，确保能回得来才行。
稍后研究其他语言怎么写这坨O.o
class Solution {
public:
bool hasValidPath(vector<vector<int>>& grid) {
int m = grid.size(),n = grid[0].size();
std::vector<std::vector<int>> dx = {{0,0},{-1,1},{0,1},{0,1},{-1,0},{-1,0}};
std::vector<std::vector<int>> dy = {{-1,1},{0,0},{-1,0},{1,0},{0,-1},{0,1}};
grid[0][0] = -grid[0][0];
queue<pair<int,int>> q;
q.push(std::make_pair(0,0));
while(!q.empty()) {
auto p = q.front();
q.pop();
int x = p.first,y = p.second;
int id = -grid[x][y] - 1;
for(int i = 0; i < 2; i++) {
int nx = x + dx[id][i], ny = y + dy[id][i];
if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {
int nid = grid[nx][ny] - 1;
for(int j = 0; j < 2; j++) {
int nnx = nx + dx[nid][j], nny = ny + dy[nid][j];
if(nnx == x && nny == y) {
grid[nx][ny] = -grid[nx][ny];
q.push(std::make_pair(nx,ny));
break;
}
}
}
}
}
return (grid[m - 1][n - 1] < 0);
}
};
python 的id貌似不能乱用; deque 直接当queue用;没大括号,我return缩进错了整了5分钟才发现.
class Solution:
def hasValidPath(self, grid: List[List[int]]) -> bool:
m,n = len(grid),len(grid[0])
dx = [[0,0],[-1,1],[0,1],[0,1],[-1,0],[-1,0]]
dy = [[-1,1],[0,0],[-1,0],[1,0],[0,-1],[0,1]]
q = deque()
grid[0][0] = -grid[0][0]
q.append([0,0])
while q:
val = q.popleft()
x,y = val[0], val[1]
vid = -grid[x][y] - 1
for i in range(2):
nx, ny = x + dx[vid][i], y + dy[vid][i]
if nx >= 0 and ny >= 0 and nx < m and ny < n and grid[nx][ny] > 0:
nvid = grid[nx][ny] - 1
for j in range(2):
nnx, nny = nx + dx[nvid][j], ny + dy[nvid][j]
if nnx == x and nny == y:
grid[nx][ny] = -grid[nx][ny]
q.append([nx,ny])
break
return (grid[m - 1][n - 1] < 0)
不能直接用len(q)当条件; 切片当queue; go这个初化是真别扭;append用法和python区分;
func hasValidPath(grid [][]int) bool {
m, n := len(grid), len(grid[0])
dx := [][]int{{0,0},{-1,1},{0,1},{0,1},{-1,0},{-1,0}}
dy := [][]int{{-1,1},{0,0},{-1,0},{1,0},{0,-1},{0,1}}
q := [][2]int{{0,0}}
grid[0][0] = -grid[0][0]
for len(q) > 0 {
x, y := q[0][0], q[0][1]
q = q[1:]
id := -grid[x][y] - 1
for i := 0; i < 2; i++ {
nx, ny := x + dx[id][i], y + dy[id][i]
if nx >= 0 && ny >= 0 && nx < m && ny < n && grid[nx][ny] > 0 {
nid := grid[nx][ny] - 1
for j := 0; j < 2; j++ {
nnx, nny := nx + dx[nid][j], ny + dy[nid][j]
if nnx == x && nny == y {
q = append(q,[2]int{nx,ny})
grid[nx][ny] = -grid[nx][ny]
break
}
}
}
}
}
return (grid[m - 1][n - 1] < 0)
}
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);
}
};
网友解答：
--【壹】--：
type Street = Int
neighbor :: (Int, Int) -> Int -> Street -> [Int]
neighbor (m, n) x street =
let (r, c) = x `divMod` n
candidates = case street of
1 -> [(r, c + 1), (r, c - 1)] -- LR
2 -> [(r + 1, c), (r - 1, c)] -- UD
3 -> [(r, c - 1), (r + 1, c)] -- LD
4 -> [(r, c + 1), (r + 1, c)] -- RD
5 -> [(r, c - 1), (r - 1, c)] -- LU
6 -> [(r, c + 1), (r - 1, c)] -- RU
_ -> []
in mapMaybe (toIdx (m, n)) candidates
toIdx :: (Int, Int) -> (Int, Int) -> Maybe Int
toIdx (m, n) (r, c) =
guard (0 <= r && r < m && 0 <= c && c < n) $> (r * n + c)
hasValidPath :: [[Street]] -> Bool
hasValidPath grid = isLeft $ runExcept (evalStateT (dfs 0) mempty)
where
m = length grid
n = length $ head $ fromList grid
terminal = m * n - 1
neighbors = V.map (uncurry $ neighbor (m, n)) $ V.fromList $ zip [0 ..] $ concat grid
adjs = V.generate (m * n) $ \i -> filter (\a -> i `elem` (neighbors V.! a)) (neighbors V.! i)
dfs curr =
when (curr == terminal) (throwError ())
*> modify' (IS.insert curr)
*> for_ (adjs V.! curr) (unlessM <$> (gets . IS.member) <*> dfs)
先算有向图，过滤出无向子图再dfs，如果原地改状态疑似会把向量搞进老年代反而让性能下降
--【贰】--：
from typing import List
class Solution:
def hasValidPath(self, grid: List[List[int]]) -> bool:
d = {
1: ((0, -1), (0, 1)),
2: ((-1, 0), (1, 0)),
3: ((0, -1), (1, 0)),
4: ((0, 1), (1, 0)),
5: ((0, -1), (-1, 0)),
6: ((0, 1), (-1, 0)),
}
m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
def dfs(i, j):
if i == m - 1 and j == n - 1:
return True
vis[i][j] = True
for di, dj in d[grid[i][j]]:
ii, jj = i + di, j + dj
if 0 <= ii < m and 0 <= jj < n and not vis[ii][jj]:
if (-di, -dj) in d[grid[ii][jj]]:
if dfs(ii, jj):
return True
return False
return dfs(0, 0)
--【叁】--：
存下每个点的俩方向，直接从起点做一个bfs。
给负值表示走过，省点空间同时也能保持记忆。
bfs到下一个点时，确保不越界且没走过的同时，下一个点再探下一个点，确保能回得来才行。
稍后研究其他语言怎么写这坨O.o
class Solution {
public:
bool hasValidPath(vector<vector<int>>& grid) {
int m = grid.size(),n = grid[0].size();
std::vector<std::vector<int>> dx = {{0,0},{-1,1},{0,1},{0,1},{-1,0},{-1,0}};
std::vector<std::vector<int>> dy = {{-1,1},{0,0},{-1,0},{1,0},{0,-1},{0,1}};
grid[0][0] = -grid[0][0];
queue<pair<int,int>> q;
q.push(std::make_pair(0,0));
while(!q.empty()) {
auto p = q.front();
q.pop();
int x = p.first,y = p.second;
int id = -grid[x][y] - 1;
for(int i = 0; i < 2; i++) {
int nx = x + dx[id][i], ny = y + dy[id][i];
if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {
int nid = grid[nx][ny] - 1;
for(int j = 0; j < 2; j++) {
int nnx = nx + dx[nid][j], nny = ny + dy[nid][j];
if(nnx == x && nny == y) {
grid[nx][ny] = -grid[nx][ny];
q.push(std::make_pair(nx,ny));
break;
}
}
}
}
}
return (grid[m - 1][n - 1] < 0);
}
};
python 的id貌似不能乱用; deque 直接当queue用;没大括号,我return缩进错了整了5分钟才发现.
class Solution:
def hasValidPath(self, grid: List[List[int]]) -> bool:
m,n = len(grid),len(grid[0])
dx = [[0,0],[-1,1],[0,1],[0,1],[-1,0],[-1,0]]
dy = [[-1,1],[0,0],[-1,0],[1,0],[0,-1],[0,1]]
q = deque()
grid[0][0] = -grid[0][0]
q.append([0,0])
while q:
val = q.popleft()
x,y = val[0], val[1]
vid = -grid[x][y] - 1
for i in range(2):
nx, ny = x + dx[vid][i], y + dy[vid][i]
if nx >= 0 and ny >= 0 and nx < m and ny < n and grid[nx][ny] > 0:
nvid = grid[nx][ny] - 1
for j in range(2):
nnx, nny = nx + dx[nvid][j], ny + dy[nvid][j]
if nnx == x and nny == y:
grid[nx][ny] = -grid[nx][ny]
q.append([nx,ny])
break
return (grid[m - 1][n - 1] < 0)
不能直接用len(q)当条件; 切片当queue; go这个初化是真别扭;append用法和python区分;
func hasValidPath(grid [][]int) bool {
m, n := len(grid), len(grid[0])
dx := [][]int{{0,0},{-1,1},{0,1},{0,1},{-1,0},{-1,0}}
dy := [][]int{{-1,1},{0,0},{-1,0},{1,0},{0,-1},{0,1}}
q := [][2]int{{0,0}}
grid[0][0] = -grid[0][0]
for len(q) > 0 {
x, y := q[0][0], q[0][1]
q = q[1:]
id := -grid[x][y] - 1
for i := 0; i < 2; i++ {
nx, ny := x + dx[id][i], y + dy[id][i]
if nx >= 0 && ny >= 0 && nx < m && ny < n && grid[nx][ny] > 0 {
nid := grid[nx][ny] - 1
for j := 0; j < 2; j++ {
nnx, nny := nx + dx[nid][j], ny + dy[nid][j]
if nnx == x && nny == y {
q = append(q,[2]int{nx,ny})
grid[nx][ny] = -grid[nx][ny]
break
}
}
}
}
}
return (grid[m - 1][n - 1] < 0)
}