代码随想录算法训练营第56,57天 [卡玛网98. 所有可达路径， 卡玛网99. 岛屿数量，卡玛网100. 岛屿的最大面积]

一、卡玛网98. 所有可达路径

链接: 代码随想录.
思路：邻接矩阵和邻接表两种方法
做题状态：看解析后做出来了

// 邻接矩阵
#include<iostream>
#include<vector>
using namespace std;
 
vector<vector<int>> result;
vector<int> path;
 
void dfs(vector<vector<int>> &graph,int x,int n){
    if(x == n){
        result.push_back(path);
        return;
    }
     
    for(int i = 1;i<=n;i++){
        if(graph[x][i] == 1){
            path.push_back(i);
            dfs(graph,i,n);
            path.pop_back();
        }
    }
}
 
int main(){
    int N;int M;
    int s;int t;
    cin >> N >> M;
    vector<vector<int>> graph(N+1,vector<int>(N+1,0));
    while(M--){
        cin>>s>>t;
        graph[s][t] = 1;
    }
    path.push_back(1);
    dfs(graph,1,N);
    if(result.size() == 0){
        cout << -1 <<endl;
    }
    for(vector<int> p : result){
        for(int i =0;i<p.size()-1;i++){
            cout << p[i] <<" ";
        }
        cout << p[p.size()-1]<<endl;
    }
    return 0;
}

二、卡玛网99. 岛屿数量

链接: 代码随想录.
思路：深搜广搜
做题状态：看解析后做出来了

// 深搜
#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
 
void dfs(vector<vector<int>> &graph,vector<vector<int>> &visited,int i,int j ){
    for(int k =0;k<4;k++){
        int next_x = i+dir[k][0];
        int next_y = j+dir[k][1];
        if(next_x < 0 || next_x >= graph.size() || next_y < 0 || next_y >= graph[0].size()){
            continue;
        }
        if(visited[next_x][next_y] == 0 && graph[next_x][next_y] == 1){
            visited[next_x][next_y] = 1;
            dfs(graph,visited,next_x,next_y);
        }
    }
}
 
 
int main(){
    int m;int n;
    cin >> n >> m;
    vector<vector<int>> graph(n,vector<int>(m,0));
    int x;
    int result = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin >> x;
            if(x == 1){
                graph[i][j] = 1;
            }
        }
    }
    vector<vector<int>> visited(n,vector<int>(m,0));
     
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(graph[i][j] == 1 && visited[i][j] == 0){
                visited[i][j] = 1;
                result++;
                dfs(graph,visited,i,j);
            }
        }
    }
     
    cout << result <<endl;
}

// 广搜
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
void bfs(vector<vector<int>> &graph,vector<vector<int>> &visited ,int x,int y){
    queue<pair<int,int>> que;
    que.push({x,y});
    visited[x][y] = 1;
    while(!que.empty()){
        pair<int,int> cur = que.front();
        que.pop();
        int cur_x = cur.first;
        int cur_y = cur.second;
        for(int i = 0;i<4;i++){
            int next_x = cur_x+dir[i][0];
            int next_y = cur_y+dir[i][1];
            if(next_x < 0 || next_x >= graph.size() || next_y < 0 || next_y >= graph[0].size()){
                continue;
            }
            if(graph[next_x][next_y] == 1 && visited[next_x][next_y] == 0){
                visited[next_x][next_y] = 1;
                que.push({next_x,next_y});
            }
        }
    }
}
 
int main(){
    int N;
    int M;
    cin >> N >> M;
    vector<vector<int>> graph(N,vector<int>(M,0));
    vector<vector<int>> visited(N,vector<int>(M,0));
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            cin >>graph[i][j];
        }
    }
     
    int result = 0;
     
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            if(graph[i][j] == 1 && visited[i][j] == 0){
                visited[i][j] = 1;
                result++;
                bfs(graph,visited,i,j);
            }
        }
    }
    cout << result <<endl;
}

三、卡玛网100. 岛屿的最大面积

链接: 代码随想录.
思路：深搜广搜
做题状态：看解析后做出来了

// 深搜
#include<iostream>
#include<vector>
using namespace std;
int count = 0;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
void dfs(vector<vector<int>> &graph,vector<vector<int>> &visited,int x,int y){
    for(int i = 0;i<4;i++){
        int next_x = x+dir[i][0];
        int next_y = y+dir[i][1];
        if(next_x < 0 || next_x >= graph.size() || next_y < 0 ||next_y >= graph[0].size()){
            continue;
        }
        if(graph[next_x][next_y] == 1 && visited[next_x][next_y] == 0){
            visited[next_x][next_y] = 1;
            count++;
            dfs(graph,visited,next_x,next_y);
        }
    }
}
 
int main(){
    int n;int m;
    cin >> n >> m;
    vector<vector<int>> graph(n,vector<int>(m,0)); 
    vector<vector<int>> visited(n,vector<int>(m,0)); 
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> graph[i][j];
        }
    }
    int result = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(graph[i][j] == 1 && visited[i][j] == 0){
                count = 1;
                visited[i][j] = 1;
                dfs(graph,visited,i,j);
                result = max(result,count);
            }
        }
    }
     
    cout << result <<endl;
}

// 广搜
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int count = 0;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
void bfs(vector<vector<int>> &graph,vector<vector<int>> &visited,int x,int y){
   queue<pair<int,int>> que;
   que.push({x,y});
   visited[x][y] = 1;
   count++;
   while(!que.empty()){
       pair<int,int> cur = que.front();
       que.pop();
       int cur_x = cur.first;
       int cur_y = cur.second;
       for(int i = 0;i<4;i++){
           int next_x = cur_x + dir[i][0];
           int next_y = cur_y + dir[i][1];
           if(next_x < 0 || next_x >= graph.size() || next_y<0||next_y>=graph[0].size()){
               continue;
           }
           if(graph[next_x][next_y] == 1 && visited[next_x][next_y] == 0){
                visited[next_x][next_y] = 1;
                que.push({next_x,next_y});
                count++;
           }
           
       }
   }
}
 
int main(){
    int n;int m;
    cin >> n >> m;
    vector<vector<int>> graph(n,vector<int>(m,0)); 
    vector<vector<int>> visited(n,vector<int>(m,0)); 
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> graph[i][j];
        }
    }
     
    int result = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(graph[i][j] == 1 && visited[i][j] == 0){
                count = 0;
                visited[i][j] = 1;
                bfs(graph,visited,i,j);
                result = max(result,count);
            }
        }
    }
     
    cout << result <<endl;
}