代码随想录算法训练营第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;
}