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 连通分量的“岛”。 该函数将返回三个输出参数,包括输入矩阵中最大的连接岛。 有关所有说明,请参阅详细帮助。 灵感来自最近发布的益智游戏: ...
针对这个问题,LeetCode上的Number of Islands II题目要求通过编写算法来解决这个问题。本篇题解将详细探讨如何使用Java语言实现这一问题的解决方案。 首先,理解问题的背景至关重要。在Number of Islands II的问题...
在MATLAB编程环境中,`findIslands`函数是一个自定义函数,用于在向量中查找特定值的连续区域,这些区域被其他不同的值所包围,我们称之为“孤岛”。这个功能在数据分析和处理中非常有用,特别是在寻找某种特定特征...
- 动词的过去分词是英语中不规则变化的一部分,例如题目中给出的`read`的过去分词是`read`,`drink`的过去分词是`drunk`,`find`的过去分词是`found`,`leave`的过去分词是`left`,`see`的过去分词是`seen`,`tell`...
389 | [Find the Difference](https://leetcode.com/problems/find-the-difference/) | [C++](./C++/find-the-difference.cpp) [Python](./Python/find-the-difference.py) | _O(n)_ | _O(1)_ | Easy | | ...
- `FLOODFILL_ISLANDS`:标记不连续区域而非连续区域。 #### 三、示例代码分析 为了更好地理解 `floodFill` 函数的使用方法,我们可以通过一个简单的示例来进行分析: ```cpp #include #include using ...
目前,他专注于如Composition Application Framework、Visual Composer、Web Services、Web Dynpro等技术,并对如何在企业中利用NetWeaver Galaxy和Flash Islands等新特性进行研究。 #### 目录 1. **介绍** 2. **...
* The way of specifying the path to find dynamic libraries at runtime has been simplified. The old default to pass -R/path/to/dir has been replaced with the new default to pass -Wl,-rpath,/path/to/...