盘锦网站制作公司,广州网站建设新锐,南京 app开发公司,合肥建设云个人服务平台题目描述 题目分析
仔细分析这道题以后虽然觉得可能要转化为图之类的#xff0c;但是完全没有具体的想法#xff0c;因为每个格子都有三种情况#xff0c;这三种情况的不同的组合又会产生不同的结果。 发现找不到编码转化为图以后#xff0c;我分析了一下不同数量方块之间…题目描述 题目分析
仔细分析这道题以后虽然觉得可能要转化为图之类的但是完全没有具体的想法因为每个格子都有三种情况这三种情况的不同的组合又会产生不同的结果。 发现找不到编码转化为图以后我分析了一下不同数量方块之间的联系试图找到像递归一样的关系。发现也没有找到关键是边长小的方块四周会有边但是将其放到大方块中并没有这些边而且他们的边界还会组合。 在没有思路之后我看了一下题解发现题解最巧妙的地方在于将每一个单元块再次划分为四个小块从而将原先三种情况统一了起来每种情况是这四个小块的不同组合方式。然后块与块之间同样通过小块进行拼接。然后再使用并差集得到联通块的个数。
总结
分解以后使用并查集得到联通分量的个数这个是非常简单的但是关键在于分解这步自己没有想到。以后遇到问题不应该仅仅思考问题的拼接、分类讨论、递归而且也应该考虑一下所谓的分类情况能否再进行分解从而将各种分类统一起来。
AC代码
class UnionSet {
public:int n;int setCount;vectorint father;vectorint size;UnionSet(int _n):n(_n),setCount(_n),father(_n),size(_n, 1) {iota(father.begin(), father.end(), 0);}int root(int x) {//路径压缩return x father[x] ? x : father[x] root(father[x]);}bool unite(int x, int y) {x root(x);y root(y);if (x y) {return false;}if (size[x] size[y]) {//按秩合并swap(x, y);}father[y] x;size[x] size[y];--setCount;return true;}
};
class Solution {
public:int regionsBySlashes(vectorstring grid) {int n grid.size();UnionSet us(4 * n * n);for (int i 0; i n; i) {int idx 0; //用于指向对应的字符for (int j 0; j n; j, idx) {int base (i * n j) * 4; //哈希值switch (grid[i][idx]) {case ://空格将四个块全部合并us.unite(base 0, base 1);us.unite(base 0, base 2);us.unite(base 0, base 3);break;case /://斜杠us.unite(base 0, base 3);us.unite(base 1, base 2);break;case \\://反斜杠us.unite(base 0, base 1);us.unite(base 2, base 3);//idx; //因为反斜杠有两个break;}//完成和右边块和下边块的拼接if (j 1 n) {//右边块存在int baser base 4;us.unite(base 1, baser 3);}if (i 1 n) {//下边块存在int baseb 4 * ((i 1) * n j);us.unite(base 2, baseb 0);}}}//最后联通块的个数return us.setCount;}
};官方题解是用Java写的这里就不再贴出。刚开始看到题目中说反斜杠是两个我还想着要对反斜杠特殊处理代码中的idx变量结果真的只是编码输出的问题。。。
