代码随想录 打卡第五十二天

卡码网 101 孤岛的总面积#includeiostream #includevector using namespace std; int inorder[4][2] {0,1, 1,0, 0,-1, -1,0}; void dfs(vectorvectorint 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; vectorvectorint mon(n,vectorint(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 沉没孤岛#includeiostream #includevector using namespace std; int main(){ int n,m; cin n m; vectorvectorint graph(n,vectorint(m,0)); vectorvectorint state(n,vectorint(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 高山流水#includeiostream #includevector using namespace std; int inorder[4][2] {0,1, 1,0, 0,-1, -1,0}; void dfs(vectorvectorint mon,vectorvectorint 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; vectorvectorint mon(n,vectorint(m,0)); vectorvectorint border1(n,vectorint(m,0)); vectorvectorint border2(n,vectorint(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 建造最大岛屿#includeiostream #includevector #includeunordered_map #includeunordered_set using namespace std; int inorder[4][2] {0,1, 1,0, 0,-1, -1,0}; void dfs(vectorvectorint graph,vectorvectorint 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; vectorvectorint graph(n,vectorint(m,0)); vectorvectorint visit(n,vectorint(m,0)); unordered_mapint,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_setint 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; }