【每日算法Day 70】图解算法:小学生都会的数块数问题,你会吗?

简介: 在由 1 x 1 方格组成的 N x N 网格 grid 中,每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。(请注意,反斜杠字符是转义的,因此 \ 用 "\\" 表示。)。返回区域的数目

题目链接


LeetCode 959. 由斜杠划分区域[1]

题目描述


在由 1 x 1 方格组成的 N x N 网格 grid 中,每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

(请注意,反斜杠字符是转义的,因此 \ 用 "\\" 表示。)。

返回区域的数目。

示例1

输入:[  " /",  "/ "]输出:2解释:2x2 网格如下:

image.png

示例2

输入:[  " /",  "  "]输出:1解释:2x2 网格如下:

image.png

示例3

输入:[  "\\/",  "/\\"]输出:4解释:(回想一下,因为 \ 字符是转义的,所以 "\\/" 表示 \/,而 "/\\" 表示 /\。)2x2 网格如下:

image.png

示例4

输入:[  "/\\",  "\\/"]输出:5解释:(回想一下,因为 \ 字符是转义的,所以 "/\\" 表示 /\,而 "\\/" 表示 \/。)2x2 网格如下:

image.png

示例5

输入:[  "//",  "/ "]输出:3解释:2x2 网格如下:

image.png

题解


这题如果不用写代码,直接让你数的话,那就非常简单了。但是要想实现代码,还是有点麻烦的。

最主要的麻烦点在于,如果表示出斜杠的划分?这里我提供了三种不同的方法。

方法 1


image.png

如上图所示,首先将每个格子划分成 3 x 3 的更小的网格,然后对角线上填充 1 来表示斜杠,其余地方全部填充 0 。

那么问题就转化为了求一个 3N x 3N 的网格上的 0 的连通块一共有几块,这就用普通的 dfs 搜一遍就知道了。

那么这里有个问题,为什么不能每个格子划分成 2 x 2 呢?如下图所示,这样会导致两个格子中的 0 无法只用上下左右四个方向来联通:image.png

方法 2


image.png

如上图所示,这种方法采用了并查集的思想。

首先将一个格子用 X 划分成四块,上图左半部分是各自之间的连通性,两个格子的相邻部分是一定连通的。

而右半部分是格子内部的连通性。如果有斜杠,那就将斜杠两边的两小块都连起来。如果没有斜杠,那就将四小块都连起来,而这只需要三条线就够了。

方法 3



如上图所示,这个方法还是采用了并查集的思想。这次我们不以格子为计算单元了,我们来看格点。

初始的时候,四周一圈的格点都是连通的(红色线),而内部的格点都是孤立的。这时候只有一个区域,也就是整个平面。

然后一个格子一个格子添加斜杠。首先添加绿色斜杠,也就是连接 0 和 5 格点,这时候发现这两个点不在一个连通块里,那么就没有产生区域。

然后添加蓝色斜杠,也就是连接 2 和 5 格点,这时候发现这两个点在同一个连通块里,那么就产生了一个新的区域(也就是灰色部分)。

这样遍历完所有斜杠,就能知道增加了几块新的区域了。

代码


方法 1(c++)

classSolution {
public: 
intdx[4] = {0, 0, 1, -1};   
intdy[4] = {1, -1, 0, 0};
voiddfs(intx, inty, vector<vector<int>>&grid) {    
intn=grid.size();  
for (inti=0; i<4; ++i) {      
intnx=x+dx[i], ny=y+dy[i];   
if (0<=nx&&nx<n&&0<=ny&&ny<n&&!grid[nx]
                [ny]) {     
grid[nx][ny] =1;      
dfs(nx, ny, grid);     
            }  
        }  
    }
intregionsBySlashes(vector<string>&grid) {  
intn=grid.size(); 
vector<vector<int>>new_grid(3*n, vector<int>(3*n, 0));        for (inti=0; i<n; ++i) { 
for (intj=0; j<n; ++j) {        
if (grid[i][j] =='/') {    
new_grid[3*i][3*j+2] =1;  
new_grid[3*i+1][3*j+1] =1;      
new_grid[3*i+2][3*j] =1;     
                } elseif (grid[i][j] =='\\') {    
new_grid[3*i][3*j] =1;     
new_grid[3*i+1][3*j+1] =1;  
new_grid[3*i+2][3*j+2] =1;   
                }        
            }       
        }       
intcnt=0;   
for (inti=0; i<3*n; ++i) {   
for (intj=0; j<3*n; ++j) {  
if (!new_grid[i][j]) {      
cnt++;       
new_grid[i][j] =1;    
dfs(i, j, new_grid);    
                }       
            }      
        }      
returncnt;   
    }
};

方法 2(c++)

classSolution {
public:  
vector<int>f;
intfind(intx) {  
returnx==f[x] ?x : f[x]=find(f[x]);    }
voidmerge(intu, intv) {   
intfu=find(u), fv=find(v);    
if (fu==fv) return;   
f[fv] =fu;    }
intregionsBySlashes(vector<string>&grid) {   
intn=grid.size();  
f=vector<int>(4*n*n, 0);   
for (inti=0; i<4*n*n; ++i) {      
f[i] =i;    
        }    
for (inti=0; i<n; ++i) {   
for (intj=0; j<n; ++j) {  
ints=4*(i*n+j);         
if (grid[i][j] =='/') {     
merge(s, s+3);  
merge(s+1, s+2);   
                } else {           
merge(s, s+1);     
merge(s+2, s+3);  
                }            
if (grid[i][j] ==' ') {   
merge(s, s+3);   
                }            
if (i>0) merge(s, s-4*n+2);   
if (i<n-1) merge(s+2, s+4*n);  
if (j>0) merge(s+3, s-3);    
if (j<n-1) merge(s+1, s+7);  
            }      
        }     
intcnt=0;     
for (inti=0; i<4*n*n; ++i) {     
if (find(i) ==i) cnt++;    
        }     
returncnt;   
    }
};

方法 3(c++)

classSolution {
public:
vector<int>f;
intfind(intx) {  
returnx==f[x] ?x : f[x]=find(f[x]);    }
intmerge(intu, intv) {   
intfu=find(u), fv=find(v);    
if (fu==fv) return0;
f[fv] =fu;    
return1; 
    }
intregionsBySlashes(vector<string>&grid) {  
intn=grid.size(); 
f=vector<int>((n+1)*(n+1), 0);
for (inti=0; i< (n+1)*(n+1); ++i) {   
f[i] =i;    
        }    
for (inti=0; i<n; ++i) {     
merge(i, i+1); 
merge(n*(n+1)+i, n*(n+1)+i+1);  
merge(i*(n+1), (i+1)*(n+1));    
merge(i*(n+1)+n, (i+1)*(n+1)+n);   
        }     
intcnt=1;  
for (inti=0; i<n; ++i) {  
for (intj=0; j<n; ++j) {    
if (grid[i][j] ==' ') continue;  
intu, v;          
if (grid[i][j] =='/') {    
u=i*(n+1)+j+1;    
v= (i+1)*(n+1)+j;  
                } else {          
u=i*(n+1)+j;     
v= (i+1)*(n+1)+j+1;  
                }              
if (!merge(u, v)) cnt++; 
            }      
        }       
returncnt;  
    }
};

参考资料

[1]

LeetCode 959. 由斜杠划分区域: https://leetcode-cn.com/problems/regions-cut-by-slashes/

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~

相关文章
|
1月前
|
算法 前端开发 JavaScript
< 每日算法:一文带你认识 “ 双指针算法 ” >
`双指针`并非指的是一种具体的公式或者范式。而是一种运算思路,用于节省逻辑运算时间的`逻辑思路`!双指针算法通常用于`优化时间复杂度`!
< 每日算法:一文带你认识 “ 双指针算法 ” >
|
算法 C++ Python
【每日算法Day 85】图解算法:一行代码解决约瑟夫环的变体
【每日算法Day 85】图解算法:一行代码解决约瑟夫环的变体
|
算法 C++
【每日算法Day 70】图解算法:小学生都会的数块数问题,你会吗?
【每日算法Day 70】图解算法:小学生都会的数块数问题,你会吗?
|
机器学习/深度学习 自然语言处理 算法
|
机器学习/深度学习 算法 Java
【每日算法】使用「双向 BFS」解决搜索空间爆炸问题(附启发式搜索 AStar 算法) |Python 主题月
【每日算法】使用「双向 BFS」解决搜索空间爆炸问题(附启发式搜索 AStar 算法) |Python 主题月
|
算法 Java 索引
【每日算法】复制带随机指针的链表:「哈希表」&「原地算法」|Python 主题月
【每日算法】复制带随机指针的链表:「哈希表」&「原地算法」|Python 主题月
|
3天前
|
算法 JavaScript 决策智能
基于禁忌搜索算法的TSP路径规划matlab仿真
**摘要:** 使用禁忌搜索算法解决旅行商问题(TSP),在MATLAB2022a中实现路径规划,显示优化曲线与路线图。TSP寻找最短城市访问路径,算法通过避免局部最优,利用禁忌列表不断调整顺序。关键步骤包括初始路径选择、邻域搜索、解评估、选择及禁忌列表更新。过程示意图展示搜索效果。
|
3天前
|
机器学习/深度学习 算法
基于BP神经网络和小波变换特征提取的烟草香型分类算法matlab仿真,分为浓香型,清香型和中间香型
```markdown 探索烟草香型分类:使用Matlab2022a中的BP神经网络结合小波变换。小波分析揭示香气成分的局部特征,降低维度,PCA等用于特征选择。BP网络随后处理这些特征,以区分浓香、清香和中间香型。 ```
|
4天前
|
机器学习/深度学习 算法
m基于PSO-GRU粒子群优化长门控循环单元网络的电力负荷数据预测算法matlab仿真
摘要: 在MATLAB 2022a中,对比了电力负荷预测算法优化前后的效果。优化前为&quot;Ttttttt111222&quot;,优化后为&quot;Tttttttt333444&quot;,明显改进体现为&quot;Tttttttttt5555&quot;。该算法结合了粒子群优化(PSO)和长门控循环单元(GRU)网络,利用PSO优化GRU的超参数,提升预测准确性和稳定性。PSO模仿鸟群行为寻找最优解,而GRU通过更新门和重置门处理长期依赖问题。核心MATLAB程序展示了训练和预测过程,包括使用&#39;adam&#39;优化器和超参数调整,最终评估并保存预测结果。
13 0
|
5天前
|
算法 安全
基于龙格库塔算法的SIR病毒扩散预测matlab仿真
该程序使用龙格库塔算法实现SIR模型预测病毒扩散,输出易感、感染和康复人群曲线。在MATLAB2022a中运行显示预测结果。核心代码设置时间区间、参数,并定义微分方程组,通过Runge-Kutta方法求解。SIR模型描述三类人群动态变化,常微分方程组刻画相互转化。模型用于预测疫情趋势,支持公共卫生决策,但也存在局限性,如忽略空间结构和人口异质性。

热门文章

最新文章