代码随想录算法训练营day51

1.岛屿数量（深搜）

1.1 题目

https://kamacoder.com/problempage.php?pid=1171

1.2 题解

#include <iostream>
#include <vector>
#include <queue>
#include <list>
using namespace std;

/*邻接矩阵写法*/

//四个方向
int direct[4][2] = { 0, 1, 1, 0, -1, 0, 0, -1 };


void dfs(const vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y)
{
	//确定终止条件
	if (visited[x][y] == true || grid[x][y] == 0)return;
	//当前节点标记访问过
	visited[x][y] = true;
	//开始遍历四个方向
	for (int i = 0; i < 4; i++)
	{
		int nextx = x + direct[i][0];
		int nexty = y + direct[i][1];
		//如果越界了，结束本次循环
		if (nextx < 0 || nextx >= grid[1].size() || nexty < 0 || nexty >= grid[0].size())continue;
		dfs(grid, visited, nextx, nexty);
	}
}

int main()
{
	//矩阵行数
	int n;
	//矩阵列数
	int m;
	cin >> n >> m;

	//构造矩阵
	vector<vector<int>> grid(n,vector<int>(m,0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> grid[i][j];
		}
	}
	//是否遍历的标志列表
	vector<vector<bool>> visited(n, vector<bool>(m, false));
	//开始遍历
	int result = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (!visited[i][j] && grid[i][j] == 1) 
			{
				result++;
				dfs(grid, visited, i, j);
			}
		}
	}
	cout << result << endl;

}

2.岛屿数量（广搜）

2.1题目

https://kamacoder.com/problempage.php?pid=1171

2.2 题解

#include <iostream>
#include <vector>
#include <queue>
#include <list>
using namespace std;


int dir[4][2] = { 0,1,1,0,-1,0,0,-1 };

void bfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y)
{
	queue<pair<int, int>> que;
	que.push({ x,y });
	//加入队列立即标记
	visited[x][y] = true;
	while (!que.empty())
	{
		pair<int, int> cur = que.front();
		que.pop();
		int curx = cur.first;
		int cury = cur.second;
		for (int i = 0; i < 4; i++)
		{
			int nextx = curx + dir[i][0];
			int nexty = cury + dir[i][1];
			if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
			if (!visited[nextx][nexty] && grid[nextx][nexty] == 1)
			{
				que.push({ nextx,nexty });
				visited[nextx][nexty] = true;
			}
		}
	}
}
int main()
{
	int n;
	int m;
	cin >> n >> m;
	vector<vector<int>> grid(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> grid[i][j];
		}
	}
	vector<vector<bool>> visited(n, vector<bool>(m, false));

	int result = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (!visited[i][j] && grid[i][j] == 1) 
			{
				result++;
				bfs(grid, visited, i, j);
			}
		}
	}
	cout << result << endl;
}

3.岛屿的最大面积

3.1 题目

https://kamacoder.com/problempage.php?pid=1172

3.2 题解

#include <iostream>
#include <vector>
#include <queue>
#include <list>
using namespace std;


int dir[4][2] = { 0,1,1,0,-1,0,0,-1 };


void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int& result)
{

	//判断终止条件
	if (visited[x][y] || grid[x][y] == 0)return;
	visited[x][y] = true;
	result++;
	for (int i = 0; i < 4; i++)
	{
		int curx = x + dir[i][0];
		int cury = y + dir[i][1];
		//越界结束本次循环
		if (curx < 0 || curx >= grid.size() || cury < 0 || cury >= grid[1].size())continue;
		dfs(grid, visited, curx, cury, result);
	}
}
int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> grid(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> grid[i][j];
		}
	}
	vector<vector<bool>> visited(n, vector<bool>(m, false));
	int result = 0;
	int temp = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (!visited[i][j] && grid[i][j] == 1) 
			{
				dfs(grid, visited, i, j, temp);
				result = max(result, temp);
				temp = 0;
			}
		}
	}
	cout << result << endl;
}