代码随想录60期day54

岛屿dfs

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

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

void dfs(const vector<vector<int>>&grid,vector<vecotr<bool>>&visited,int x,int y){
	for(int i = 0 ; i < 4; i++){
		int newtx = x + dir[i][0];
		int newty = y + dir[i][0];

		if(newtx < 0 || newtx > grid.size() || newty < 0 || newty >= grid[0].size()) continue;
		if(!visited[newtx][newty] && grid[newtx][newty] == 1){

			visited[newtx][newty] = true;
			dfs(grid,visited,newtx,newty);
		}

	}
}

int main(){
	int n,m;
	cin>>n>>m;
	vector<vector<int>>grid(n,vector<int>(m,n));
	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){
				visited[i][j] = true;
				result++;
				dfs(grid,visited,i,j);
			}
		}
	}
	cout<<result<<endl;
}

岛屿bfs

#include<iostream>
#include<vector>
#include<queue>
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 newtx = curx + dir[i][0];
			int newty = cury + dir[i][1];
			if(newtx < 0 || newtx >= grid.size() || newty < 0 || newty >= grid[0].size()){
				que.push({newtx,newty});
				visited[newtx][newty] = true;
			}
		}
	}
}

int main(){
	int n,m;
	cin>>n>>m;
	vector<vecotr<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;
}

100. 岛屿的最大面积

dfs

#include<iostream>
#include<vector>
using namespace std;
int count;
int dir[4][2] = {0,1,1,0,-1,0,0,-1};

void dfs(vector<vector<int>>&grid,vector<vector<bool>>&visited,int x,int y){
	for(int i = 0;i<4;i++){
		int newtx = x + dir[i][0];
		int newty = y + dir[i][1];
		if(newtx < 0 || newtx >=grid.size() || newty < 0 || newty >= grid[0].size()) continue;
		if(!visited[newtx][newty] && grid[newtx][newty] == 1){
			visited[newtx][newty] = true;
			count++;
			dfs(grid,visited,newtx,newty)
		}
	}
}

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;
	for(int i =0;i<n;i++){
		for(int j = 0;j<m;j++){
			if(!visited[i][j]&&grid[i][j] == 1){
				count++;
				visited[i] = true;
				dfs(grid,visited,i,j);
				result = max(result,count);
			}
		}
	}
	cout<<result<<endl;
}

bfs

class Solution {
private:
    int count;
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
    void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
        queue<int> que;
        que.push(x);
        que.push(y);
        visited[x][y] = true; // 加入队列就意味节点是陆地可到达的点
        count++;
        while(!que.empty()) {
            int xx = que.front();que.pop();
            int yy = que.front();que.pop();
            for (int i = 0 ;i < 4; i++) {
                int nextx = xx + dir[i][0];
                int nexty = yy + dir[i][1];
                if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界
                if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 节点没有被访问过且是陆地
                    visited[nextx][nexty] = true;
                    count++;
                    que.push(nextx);
                    que.push(nexty);
                }
            }
        }
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(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) {
                    count = 0;
                    bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                    result = max(result, count);
                }
            }
        }
        return result;
    }
};