Leetcode每日一题 —— 1559. 二维网格图中探测环
- 内容介绍
- 文章标签
- 相关推荐
1559. 二维网格图中探测环 - 力扣（LeetCode）
1559. 二维网格图中探测环 - 给你一个二维字符网格数组grid，大小为m x n，你需要检查grid中是否存在 相同值 形成的环。 一个环是一条开始和结束于同一个格子的长度 大于等于 4的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值。 同时，你也不能回到上一次移动时所在的格子。比方说，环(1, 1) -> (1, 2) -> (1, 1)是不合法的，因为从 (1, 2)移动到 (1, 1)...
思路
比较典型的无向图判环题，常用的思想有 DFS / BFS / 并查集，这里咱就用并查集来做了。
先注意题目中两个条件：
- 走回头路不算环路，也就不能往回走。
- 环路径的长度要 \ge 4 才算。其实在第 1 点条件的限制下这点是必然成立的，最小的环必须要有四个格子组成。
所以这题只需要保证不走回头路，进行判环即可。
用并查集判环，要不走回头路的话，我们在扫描网格时从上至下、从左至右，对于每个格子可以只尝试合并其右方或者下方的格子，按这样的逻辑处理必然是不会有回头路滴。
如此扫描直至某个网格与其右边或者下边的网格在同一个集合中，则满足题目要求，返回 true。
代码
class Solution {
public:
bool containsCycle(vector<vector<char>>& grid) {
// 比较重要的是这种环路的长度还必须 >=4 才算
// 其实不难，可以用并查集来执行合并和判环，如果有环就看对应块中元素数量是不是 >=4
// 要构成环，最小的环必然是四个方格组成的
int m=grid.size(),n=grid[0].size();
// 初始化并查集
vector<int> parents(m*n,-1),sizes(m*n,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) -> bool {
int root1=find(find,x1),root2=find(find,x2);
if(root1==root2){
// 已经合并
return false;
}
// 否则启发式合并，小树并入大树
if(sizes[root1]<sizes[root2]){
swap(root1,root2);
}
parents[root2]=root1;
sizes[root1]+=sizes[root2];
return true;
};
// 获得集合大小
// auto getSize=[&](int x){
// return sizes[find(find,x)];
// };
// 扫描数组执行判环
int drcts[][2]={
{0,1},
{1,0},
};
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
// 为了防止走回头路，对于每个方格我们只往右或者往下合并
for(auto& d:drcts){
int newI=i+d[0],newJ=j+d[1];
if(newI>=m||newJ>=n||grid[newI][newJ]!=grid[i][j]){
// 越界或者字母不相同
continue;
}
// 尝试执行合并
if(!merge(i*n+j,newI*n+newJ)/*&&getSize(i*n+j)>=4*/){
// 如果没有执行合并，说明遇到已经在并查集里的了，有环
// 这个时候判断，如果集合中有 >=4 个元素就可以结束
// 其实在不走回头路的前提下，只要有环，必然路径长度 >=4
return true;
}
}
}
}
return false;
}
};
网友解答：
--【壹】--：
试图BFS发现情况不对，回归DFS怀抱。
class Solution {
public:
bool containsCycle(vector<vector<char>>& grid) {
int n = grid.size(),m = grid[0].size();
std::vector<std::vector<int>> st(n,std::vector<int>(m,0));
int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
bool res = false;
auto find = [&](this auto&& find, int x,int y,int v) -> bool {
st[x][y] = v;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i],ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] != grid[x][y]) {
continue;
}
if(st[nx][ny]) {
if(st[x][y] - st[nx][ny] >= 3) {
return true;
}
} else {
res |= find(nx,ny,v + 1);
}
}
return false;
};
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(!st[i][j]) {
res |= find(i,j,1);
if(res) {
break;
}
}
}
}
return res;
}
};
--【贰】--：
neighbor :: (Int, Int) -> Int -> [Int] -- m * n grid
neighbor (m, n) x =
let (r, c) = x `divMod` n
candidates = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]
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)
containsCycle :: [[Char]] -> Bool
containsCycle grid = isLeft $ runExcept (evalStateT check mempty)
where
m = length grid
n = length $ head $ fromList grid
cs = UV.fromList $ concat grid
dfs c curr parent = do
modify (IS.insert curr)
let adjs = filter (\a -> a /= parent && cs UV.! a == c) $ neighbor (m, n) curr
for_ adjs $ \adj ->
ifM (gets (IS.member adj)) (throwError ()) $ dfs c adj curr
check :: StateT IntSet (Except ()) ()
check = for_ [0 .. m * n - 1] $ \i ->
unlessM (gets (IS.member i)) $ dfs (cs UV.! i) i (-1)
直接dfs、遇到走过的点就说明有环，要记的状态太多而且需要callcc（throwError ()）就拿变形金刚摆烂了
type DSU s = UV.MVector s Int
find :: DSU s -> Int -> ST s Int
find dsu x = do
p <- UMV.unsafeRead dsu x
if x /= p
then do
r <- find dsu p
UMV.unsafeWrite dsu x r $> r
else pure p
union :: DSU s -> Int -> Int -> ST s ()
union dsu x y = do
px <- find dsu x
py <- find dsu y
when (px /= py) (UMV.unsafeWrite dsu px py)
isUnited :: DSU s -> Int -> Int -> ST s Bool
isUnited = on (liftA2 (==)) . find
containsCycle' :: [[Char]] -> Bool
containsCycle' grid = isLeft $ runST $ runExceptT do
let m = length grid
n = length $ head $ fromList grid
cs = UV.fromList $ concat grid
dsu <- lift $ UMV.generate (m * n) id
for_ [0 .. m * n - 1] $ \i -> do
let adjs = filter (\a -> a < i && cs UV.! a == cs UV.! i) $ neighbor (m, n) i
for_ adjs $ \a -> do
ifM (lift $ isUnited dsu a i) (throwError ()) (lift $ union dsu a i)
拿并查集写就比较简单了，注意连的时候固定连比自己小的来避重就行了
1559. 二维网格图中探测环 - 力扣（LeetCode）
1559. 二维网格图中探测环 - 给你一个二维字符网格数组grid，大小为m x n，你需要检查grid中是否存在 相同值 形成的环。 一个环是一条开始和结束于同一个格子的长度 大于等于 4的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值。 同时，你也不能回到上一次移动时所在的格子。比方说，环(1, 1) -> (1, 2) -> (1, 1)是不合法的，因为从 (1, 2)移动到 (1, 1)...
思路
比较典型的无向图判环题，常用的思想有 DFS / BFS / 并查集，这里咱就用并查集来做了。
先注意题目中两个条件：
- 走回头路不算环路，也就不能往回走。
- 环路径的长度要 \ge 4 才算。其实在第 1 点条件的限制下这点是必然成立的，最小的环必须要有四个格子组成。
所以这题只需要保证不走回头路，进行判环即可。
用并查集判环，要不走回头路的话，我们在扫描网格时从上至下、从左至右，对于每个格子可以只尝试合并其右方或者下方的格子，按这样的逻辑处理必然是不会有回头路滴。
如此扫描直至某个网格与其右边或者下边的网格在同一个集合中，则满足题目要求，返回 true。
代码
class Solution {
public:
bool containsCycle(vector<vector<char>>& grid) {
// 比较重要的是这种环路的长度还必须 >=4 才算
// 其实不难，可以用并查集来执行合并和判环，如果有环就看对应块中元素数量是不是 >=4
// 要构成环，最小的环必然是四个方格组成的
int m=grid.size(),n=grid[0].size();
// 初始化并查集
vector<int> parents(m*n,-1),sizes(m*n,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) -> bool {
int root1=find(find,x1),root2=find(find,x2);
if(root1==root2){
// 已经合并
return false;
}
// 否则启发式合并，小树并入大树
if(sizes[root1]<sizes[root2]){
swap(root1,root2);
}
parents[root2]=root1;
sizes[root1]+=sizes[root2];
return true;
};
// 获得集合大小
// auto getSize=[&](int x){
// return sizes[find(find,x)];
// };
// 扫描数组执行判环
int drcts[][2]={
{0,1},
{1,0},
};
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
// 为了防止走回头路，对于每个方格我们只往右或者往下合并
for(auto& d:drcts){
int newI=i+d[0],newJ=j+d[1];
if(newI>=m||newJ>=n||grid[newI][newJ]!=grid[i][j]){
// 越界或者字母不相同
continue;
}
// 尝试执行合并
if(!merge(i*n+j,newI*n+newJ)/*&&getSize(i*n+j)>=4*/){
// 如果没有执行合并，说明遇到已经在并查集里的了，有环
// 这个时候判断，如果集合中有 >=4 个元素就可以结束
// 其实在不走回头路的前提下，只要有环，必然路径长度 >=4
return true;
}
}
}
}
return false;
}
};
网友解答：
--【壹】--：
试图BFS发现情况不对，回归DFS怀抱。
class Solution {
public:
bool containsCycle(vector<vector<char>>& grid) {
int n = grid.size(),m = grid[0].size();
std::vector<std::vector<int>> st(n,std::vector<int>(m,0));
int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
bool res = false;
auto find = [&](this auto&& find, int x,int y,int v) -> bool {
st[x][y] = v;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i],ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] != grid[x][y]) {
continue;
}
if(st[nx][ny]) {
if(st[x][y] - st[nx][ny] >= 3) {
return true;
}
} else {
res |= find(nx,ny,v + 1);
}
}
return false;
};
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(!st[i][j]) {
res |= find(i,j,1);
if(res) {
break;
}
}
}
}
return res;
}
};
--【贰】--：
neighbor :: (Int, Int) -> Int -> [Int] -- m * n grid
neighbor (m, n) x =
let (r, c) = x `divMod` n
candidates = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]
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)
containsCycle :: [[Char]] -> Bool
containsCycle grid = isLeft $ runExcept (evalStateT check mempty)
where
m = length grid
n = length $ head $ fromList grid
cs = UV.fromList $ concat grid
dfs c curr parent = do
modify (IS.insert curr)
let adjs = filter (\a -> a /= parent && cs UV.! a == c) $ neighbor (m, n) curr
for_ adjs $ \adj ->
ifM (gets (IS.member adj)) (throwError ()) $ dfs c adj curr
check :: StateT IntSet (Except ()) ()
check = for_ [0 .. m * n - 1] $ \i ->
unlessM (gets (IS.member i)) $ dfs (cs UV.! i) i (-1)
直接dfs、遇到走过的点就说明有环，要记的状态太多而且需要callcc（throwError ()）就拿变形金刚摆烂了
type DSU s = UV.MVector s Int
find :: DSU s -> Int -> ST s Int
find dsu x = do
p <- UMV.unsafeRead dsu x
if x /= p
then do
r <- find dsu p
UMV.unsafeWrite dsu x r $> r
else pure p
union :: DSU s -> Int -> Int -> ST s ()
union dsu x y = do
px <- find dsu x
py <- find dsu y
when (px /= py) (UMV.unsafeWrite dsu px py)
isUnited :: DSU s -> Int -> Int -> ST s Bool
isUnited = on (liftA2 (==)) . find
containsCycle' :: [[Char]] -> Bool
containsCycle' grid = isLeft $ runST $ runExceptT do
let m = length grid
n = length $ head $ fromList grid
cs = UV.fromList $ concat grid
dsu <- lift $ UMV.generate (m * n) id
for_ [0 .. m * n - 1] $ \i -> do
let adjs = filter (\a -> a < i && cs UV.! a == cs UV.! i) $ neighbor (m, n) i
for_ adjs $ \a -> do
ifM (lift $ isUnited dsu a i) (throwError ()) (lift $ union dsu a i)
拿并查集写就比较简单了，注意连的时候固定连比自己小的来避重就行了