卡码网 101 孤岛的总面积
![]()
#include<iostream> #include<vector> using namespace std; int inorder[4][2] = {0,1, 1,0, 0,-1, -1,0}; void dfs(vector<vector<int>>& mon,int x,int y){ if(mon[x][y] == 0) return; mon[x][y] = 0; for(int i = 0;i < 4;i++){ int next_x = x + inorder[i][0]; int next_y = y + inorder[i][1]; if(next_x < mon.size() && next_x >= 0 && next_y < mon[0].size() && next_y >= 0){ if(mon[next_x][next_y] == 1){ dfs(mon,next_x,next_y); } } } return; } int main(){ int n,m; cin >> n >> m; vector<vector<int>> mon(n,vector<int>(m,0)); for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ cin >> mon[i][j]; } } for(int i = 0;i < n;i++){ dfs(mon,i,0); dfs(mon,i,m-1); } for(int j = 0;j < m;j++){ dfs(mon,0,j); dfs(mon,n-1,j); } int count = 0; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(mon[i][j] == 1) count++; } } cout << count; return 0; }
卡码网 102 沉没孤岛
![]()
#include<iostream> #include<vector> using namespace std; int main(){ int n,m; cin >> n >> m; vector<vector<int>> graph(n,vector<int>(m,0)); vector<vector<int>> state(n,vector<int>(m,0)); for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ cin >> graph[i][j]; } } for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if((i == 0 || j == 0 || i == n-1 || j == m-1) && graph[i][j] == 1) state[i][j] = 1; } } for(int i = 0;i < n;i++){ cout << state[i][0]; for(int j = 1;j < m;j++){ cout << " " << state[i][j]; } cout << endl; } return 0; }
卡码网 103 高山流水
![]()
#include<iostream> #include<vector> using namespace std; int inorder[4][2] = {0,1, 1,0, 0,-1, -1,0}; void dfs(vector<vector<int>>& mon,vector<vector<int>>& visit,int x,int y){ if(visit[x][y] == 1) return; visit[x][y] = 1; for(int i = 0;i < 4;i++){ int next_x = x + inorder[i][0]; int next_y = y + inorder[i][1]; if(next_x < mon.size() && next_x >= 0 && next_y < mon[0].size() && next_y >= 0){ if(mon[next_x][next_y] >= mon[x][y]){ dfs(mon,visit,next_x,next_y); } } } return; } int main(){ int n,m; cin >> n >> m; vector<vector<int>> mon(n,vector<int>(m,0)); vector<vector<int>> border1(n,vector<int>(m,0)); vector<vector<int>> border2(n,vector<int>(m,0)); for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ cin >> mon[i][j]; } } for(int i = 0;i < n;i++){ dfs(mon,border1,i,0); dfs(mon,border2,i,m-1); } for(int j = 0;j < m;j++){ dfs(mon,border1,0,j); dfs(mon,border2,n-1,j); } for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(border1[i][j] == 1 && border2[i][j] == 1) { cout << i << " " << j << endl; } } } return 0; }
卡码网 104 建造最大岛屿
![]()
#include<iostream> #include<vector> #include<unordered_map> #include<unordered_set> using namespace std; int inorder[4][2] = {0,1, 1,0, 0,-1, -1,0}; void dfs(vector<vector<int>>& graph,vector<vector<int>>& visit,int x,int y,int& space,int& mark){ if(graph[x][y] == 0) return; if(visit[x][y] == 1) return; visit[x][y] = 1; graph[x][y] = mark; space++; for(int i = 0;i < 4;i++){ int next_x = x + inorder[i][0]; int next_y = y + inorder[i][1]; if(next_x < graph.size() && next_x >= 0 && next_y < graph[0].size() && next_y >= 0){ dfs(graph,visit,next_x,next_y,space,mark); } } return; } int main(){ int n,m; cin >> n >> m; vector<vector<int>> graph(n,vector<int>(m,0)); vector<vector<int>> visit(n,vector<int>(m,0)); unordered_map<int,int> sp; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ cin >> graph[i][j]; } } int mark = 1; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(graph[i][j] == 1 && visit[i][j] == 0){ int space = 0; dfs(graph,visit,i,j,space,mark); sp[mark] = space; mark++; } } } int result = 0; int water = 0; unordered_set<int> visitset; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(graph[i][j] != 0) water = 1; int state = 1; if(graph[i][j] == 0) { for(int k = 0;k < 4;k++){ int next_x = i + inorder[k][0]; int next_y = j + inorder[k][1]; if(next_x < graph.size() && next_x >= 0 && next_y < graph[0].size() && next_y >= 0){ if(graph[next_x][next_y] != 0 && visitset.find(graph[next_x][next_y]) == visitset.end()){ state += sp[graph[next_x][next_y]]; visitset.insert(graph[next_x][next_y]); } } } } visitset.clear(); if(result < state) result = state; } } if(result == 1 && water == 1) result = n * m; cout << result; return 0; }
