Given matrix MxN of 0s and 1s, return and output all groups of adjacent 1s in form of (row,col)...
1s are considered adjacent if they are adjacent horizontally or vertically.
1 1 0 1 0 1
1 1 1 1 0 1
0 0 0 0 1 1
1 0 1 0 1 0
Output:
A: (0,0)(1,0)(0,1)(1,1)(1,2)(1,3)(0,3)
B: (0,5)(1,5)(2,4)(2,5)(3,4)
C: (3,0)
D: (3,2)
Order in the output is insignificant.
#include <iostream> #include <vector> #include <functional> #include <unordered_map> using namespace std; // solution with changing the original matrix vector<vector<pair<int,int>>> findIslands(vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(); vector<vector<pair<int,int>>> res; vector<pair<int,int>> list; vector<vector<int>> dirs = {{0,1},{0,-1},{1,0},{-1,0}}; function<void(int,int)> dfs = [&](int r, int c) { list.emplace_back(r,c); mat[r][c] = 0; for(auto& dir:dirs) { int i = r+dir[0], j = c+dir[1]; if(i<0 || j<0 || i>=m || j>=n || !mat[i][j]) continue; dfs(i, j); } }; for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(mat[i][j]) { list.clear(); dfs(i, j); res.push_back(list); } } } return res; } // solution without changing the original matrix, using additional visited bool matrix vector<vector<pair<int,int>>> findIslands1(vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(); vector<vector<pair<int,int>>> res; vector<pair<int,int>> list; vector<vector<bool>> visited(m, vector<bool>(n)); vector<vector<int>> dirs = {{0,1},{0,-1},{1,0},{-1,0}}; function<void(int,int)> dfs = [&](int r, int c) { list.emplace_back(r,c); visited[r][c] = true; for(auto& dir:dirs) { int i = r+dir[0], j = c+dir[1]; if(i<0 || j<0 || i>=m || j>=n || !mat[i][j] || visited[i][j]) continue; dfs(i, j); } }; for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(mat[i][j] && !visited[i][j]) { list.clear(); dfs(i, j); res.push_back(list); } } } return res; } // solution without changing the original matrix and without additional memory space vector<unordered_map<int,vector<pair<int,int>>>> findIslands2(vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(); vector<unordered_map<int,vector<pair<int,int>>>> res; unordered_map<int,vector<pair<int,int>>> map; vector<vector<int>> dirs = {{0,1},{0,-1},{1,0},{-1,0}}; auto exists = [&](int r, int c) { for(auto& mp:res) { if(mp.count(r)) { for(auto& p:mp[r]) if(p.first <= c && p.second >= c) return true; } } return false; }; function<void(int,int)> dfs = [&](int r, int c) { if(map.count(r)) { bool inserted = false; for(auto& p:map[r]) { if(p.first <= c && p.second >= c) return; if(c+1 == p.first) { p.first = c; inserted = true; break; } else if(c-1 == p.second) { p.second = c; inserted = true; break; } } if(!inserted) map[r].push_back({c, c}); } else { map[r].push_back({c, c}); } for(auto& dir:dirs) { int i = r+dir[0], j = c+dir[1]; if(i<0 || j<0 || i>=m || j>=n || !mat[i][j]) continue; dfs(i, j); } }; for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(mat[i][j] && !exists(i,j)) { map.clear(); dfs(i, j); res.push_back(map); } } } return res; } int main() { vector<vector<int>> mat = { {1, 1, 0, 1, 0, 1}, {1, 1, 1, 1, 0, 1}, {0, 0, 0, 0, 1, 1}, {1, 0, 1, 0, 1, 0}}; auto res1 = findIslands1(mat); for(auto& list:res1) { for(auto& p:list) cout << "(" << p.first << "," << p.second << ") "; cout << endl; } auto res2 = findIslands2(mat); for(auto& map:res2) { for(auto& kv:map) for(auto& pair:kv.second) for(int i=pair.first; i<=pair.second; i++) cout << "(" << kv.first << "," << i << ") "; cout << endl; } return 0; }
相关推荐
ISLANDS 查找矩阵中所有 4 连通分量的“岛”。 该函数将返回三个输出参数,包括输入矩阵中最大的连接岛。 有关所有说明,请参阅详细帮助。 灵感来自最近发布的益智游戏: ...
新的14islands网站(2014年版)。 设置 npm install bower install 如果您没有gem install bundle软件: gem install bundle bundle install 跑步 grunt serve在开发模式下的上运行该站点以进行查看。 使用ruby...
Floating Islands - Fantasy Environment Pack.rar
unity3d 游戏场景模型 Islands unity3d 地形公路场景模型.zip模型资源unity模型资源下载unity3d 游戏场景模型 Islands unity3d 地形公路场景模型.zip模型资源unity模型资源下载unity3d 游戏场景模型 Islands unity3d...
一大批岛屿资产供您在下一Unity项目中使用!包括热带岛屿、火山岛、热带山脉、植被、乡村房屋、木板路、船只、粒子、后期FX等。 适用于原型设计、移动、LOD或风格化游戏。 模块化部分很容易在Unity网格上组装在一起...
离岛Vue客户具有Vue组件和Vuex的“孤岛游戏”的Web界面。基于Lance Halvorsen的《 》一书。 要启动Phoenix服务器: 使用mix deps.get安装依赖mix deps.get 使用npm install在assets目录中安装Node.js依赖项使用mix ...
雪山延绵不断,有层层叠叠的山峦,树木重重,白雪皑皑,有你想要,下你想载,需要的赶快下载吧
Ecotourism and sustainability in Mediterranean islands T 427 Ecotourism and Sustainability in Mediterranean Islands Dimitrios Diamantis Executive Summary Sustainable and ecotourism practices in...
在输入向量中查找特定值的孤岛。 一些预定义模式可用,例如检测零、一、NaN、notNans、大于阈值、小于阈值和等于特定值的岛。 输出是岛屿开始、停止和岛屿持续时间的索引。
Merge-Islands
NULL 博文链接:https://sap.iteye.com/blog/1703052
要安装和使用brs-islands ,请遵循。 用法 brs-islands 贡献 分叉( ) 创建功能分支( git checkout -b my-new-feature ) 提交更改( git commit -am 'Add some feature' ) 推送到分支( git push origin my...
基于基因条形码可视化技术的结核分枝杆菌致病岛泛基因组扫描及功能分析,王国庆,徐广宇,结核分枝杆菌(M.tuberculosis)是广为传播的人类致病菌之一,其致病基因可在菌株间或与其他致病微生物频繁交换。...
一旦有了Ember CLI项目,就可以安装Ember Islands。 ember install ember-islands 此插件的1.x版本已针对Ember 2.x版本进行了测试。 如果您在使用较早版本的Ember时遇到问题,请尝试使用0.5.x版的Ember Islands。 ...
要调整各个岛屿的声音,您必须对文件data/islands_specs.json进行编辑。 这是一个以数据结构格式设置的文件,因此要使其正常工作,必须正确设置格式。 该特定文件包含一个岛对象(由{´ and ´}括号分隔)的列表...
基于Prototype框架的Java脚本Ajax组件。 这些组件可以独立使用。 这些组件完全是面向对象的。 通过这些孤岛(组件)将您的JS代码减至最少。
从任何地方(美国,德国,瑞典,英国…)到您梦想中的温暖碧波,您都可以快速逃脱:只有使用Tropical Islands Wallpapers扩展程序。 无需离开办公室或家,即可前往菲律宾,希腊,塞舌尔,斐济,马尔代夫,费尔南多·...
PROCJAM 2015的岛屿样本项目 这是一个示例Unity项目,显示了使用“细胞自动机”的简单岛生成。 资产 它使用了2015 PROCJAM Art Pack。 您可以从免费获得该Art Pack。 该艺术作品已获得知识共享BY-NC许可,请在此处...
贡献 该项目欢迎您的贡献和建议。 大多数捐款要求您同意一份《捐款者许可协议》(CLA),声明您有权并实际上授予我们使用您的捐款的权利。 有关详细信息,请访问 。 当您提交拉取请求时,CLA机器人会自动确定您是否...