`

Find Islands

 
阅读更多

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 连通分量的“孤岛”。-matlab开发

    ISLANDS 查找矩阵中所有 4 连通分量的“岛”。 该函数将返回三个输出参数,包括输入矩阵中最大的连接岛。 有关所有说明,请参阅详细帮助。 灵感来自最近发布的益智游戏: ...

    java-leetcode题解之Number of Islands II.java

    针对这个问题,LeetCode上的Number of Islands II题目要求通过编写算法来解决这个问题。本篇题解将详细探讨如何使用Java语言实现这一问题的解决方案。 首先,理解问题的背景至关重要。在Number of Islands II的问题...

    findIslands(input,m​ode,threshold):在向量中查找特定值的岛。-matlab开发

    在MATLAB编程环境中,`findIslands`函数是一个自定义函数,用于在向量中查找特定值的连续区域,这些区域被其他不同的值所包围,我们称之为“孤岛”。这个功能在数据分析和处理中非常有用,特别是在寻找某种特定特征...

    河北省石家庄创新国际学校八年级英语下册Unit8HaveyoureadTreasureIslandyetSectionA检测题无

    - 动词的过去分词是英语中不规则变化的一部分,例如题目中给出的`read`的过去分词是`read`,`drink`的过去分词是`drunk`,`find`的过去分词是`found`,`leave`的过去分词是`left`,`see`的过去分词是`seen`,`tell`...

    LeetCode最全代码

    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 | | ...

    C++OpenCV3源代码floodFill函数用法

    - `FLOODFILL_ISLANDS`:标记不连续区域而非连续区域。 #### 三、示例代码分析 为了更好地理解 `floodFill` 函数的使用方法,我们可以通过一个简单的示例来进行分析: ```cpp #include #include using ...

    CRUD EJB 3 Web Dynpro访问数据库

    目前,他专注于如Composition Application Framework、Visual Composer、Web Services、Web Dynpro等技术,并对如何在企业中利用NetWeaver Galaxy和Flash Islands等新特性进行研究。 #### 目录 1. **介绍** 2. **...

    Git-2.21.0-64-bit.zip

    * 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/...

Global site tag (gtag.js) - Google Analytics