[LeetCode]Number of Islands

典型的Backtracking的题目，dfs的做法就行，时间复杂度O(m * n)，常数空间，因为我们在输入数组上修改。

	class Solution {
	public:
	int numIslands(vector<vector<char>>& grid) {
	int m = grid.size(), n = m? grid[0].size(): 0, res = 0;
	for(int i = 0; i < m; ++i)
	{
	for(int j = 0; j < n; ++j)
	{
	if(grid[i][j] == '1')
	{
	backtrack(grid, i, j);
	++res;
	}
	}
	}
	return res;
	}
	private:
	void backtrack(vector<vector<char>>& grid, int i, int j)
	{
	int m = grid.size(), n = grid[0].size();
	vector<pair<int, int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	char c = grid[i][j];
	grid[i][j] = '0';
	for(auto& dir : dirs)
	{
	int x = i + dir.first, y = j + dir.second;
	if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1')
	backtrack(grid, x, y);
	}
	}
	};

view raw Number of Islands.cpp hosted with ❤ by GitHub

当然连通性的题目用Union Find大多数情况也是可以的。Number of Islands II就是一个很好的例子。