day51 图论part3

卡码网 101. 孤岛的总面积

可以从行和列的遍历开始，从边缘向中间遍历 。

importjava.util.*;classMain{staticintres=0;staticintcount=0;staticbooleanflag=false;publicstaticvoiddfs(int[][]graph,boolean[][]visited,intx,inty){if(visited[x][y]||graph[x][y]==0){return;}if(x==0||y==0||x==graph.length-1||y==graph[0].length-1){flag=true;}count++;visited[x][y]=true;int[][]dir={{1,0},{0,1},{-1,0},{0,-1}};for(inti=0;i<4;i++){intnextx=x+dir[i][0];intnexty=y+dir[i][1];if(nextx<0||nexty<0||nextx>=graph.length||nexty>=graph[0].length){continue;}dfs(graph,visited,nextx,nexty);}}publicstaticvoidmain(String[]agrs){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[][]graph=newint[n][m];for(inti=0;i<n;i++){for(intj=0;j<m;j++){graph[i][j]=sc.nextInt();}}boolean[][]visited=newboolean[n][m];for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(!visited[i][j]&&graph[i][j]==1){dfs(graph,visited,i,j);}if(flag==false){res+=count;}count=0;flag=false;}}System.out.println(res);}}

卡码网 102. 沉没孤岛

importjava.util.*;publicclassMain{publicstaticvoiddfs(int[][]graph,intx,inty){if(graph[x][y]==0||graph[x][y]==2){return;}graph[x][y]=2;int[][]dir={{1,0},{0,1},{-1,0},{0,-1}};for(inti=0;i<4;i++){intnextx=x+dir[i][0];intnexty=y+dir[i][1];if(nextx<0||nexty<0||nextx>=graph.length||nexty>=graph[0].length){continue;}dfs(graph,nextx,nexty);}}publicstaticvoidmain(String[]agrs){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[][]graph=newint[n][m];for(inti=0;i<n;i++){for(intj=0;j<m;j++){graph[i][j]=sc.nextInt();}}for(inti=0;i<n;i++){if(graph[i][0]==1){dfs(graph,i,0);}if(graph[i][m-1]==1){dfs(graph,i,m-1);}}for(intj=0;j<m;j++){if(graph[0][j]==1){dfs(graph,0,j);}if(graph[n-1][j]==1){dfs(graph,n-1,j);}}for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(graph[i][j]==2){graph[i][j]=1;}elseif(graph[i][j]==1){graph[i][j]=0;}}}for(inti=0;i<n;i++){for(intj=0;j<m;j++){System.out.print(graph[i][j]+" ");}System.out.println();}}}

卡码网 103. 高山流水

从边界开始遍历，逆向思维。

importjava.util.*;publicclassMain{publicstaticvoiddfs(int[][]graph,boolean[][]visited,intx,inty){if(visited[x][y]){return;}visited[x][y]=true;int[][]dir={{1,0},{0,1},{-1,0},{0,-1}};for(inti=0;i<4;i++){intnextx=x+dir[i][0];intnexty=y+dir[i][1];if(nextx<0||nexty<0||nextx>=graph.length||nexty>=graph[0].length){continue;}if(graph[x][y]<=graph[nextx][nexty]){dfs(graph,visited,nextx,nexty);}}}publicstaticvoidmain(String[]agrs){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[][]graph=newint[n][m];for(inti=0;i<n;i++){for(intj=0;j<m;j++){graph[i][j]=sc.nextInt();}}boolean[][]firstborder=newboolean[n][m];boolean[][]secondborder=newboolean[n][m];for(inti=0;i<n;i++){dfs(graph,firstborder,i,0);dfs(graph,secondborder,i,m-1);}for(intj=0;j<m;j++){dfs(graph,firstborder,0,j);dfs(graph,secondborder,n-1,j);}for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(firstborder[i][j]==true&&secondborder[i][j]==true){System.out.print(i+" "+j);System.out.println();}}}}}

卡码网 104. 建造最大岛屿

先计算出所有岛屿的面积，用map存储，之后再把0的位置设置为1看周围面积变化。

importjava.util.*;publicclassMain{staticintmark=2;staticintcount=0;staticint[][]dir={{1,0},{0,1},{-1,0},{0,-1}};publicstaticvoiddfs(int[][]graph,boolean[][]visited,intx,inty,intmark){if(visited[x][y]){return;}visited[x][y]=true;graph[x][y]=mark;count++;for(inti=0;i<4;i++){intnextx=x+dir[i][0];intnexty=y+dir[i][1];if(nextx<0||nexty<0||nextx>=graph.length||nexty>=graph[0].length){continue;}if(graph[nextx][nexty]==1){dfs(graph,visited,nextx,nexty,mark);}}}publicstaticvoidmain(String[]agrs){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[][]graph=newint[n][m];HashMap<Integer,Integer>mapsize=newHashMap<>();HashSet<Integer>setsize=newHashSet<>();for(inti=0;i<n;i++){for(intj=0;j<m;j++){graph[i][j]=sc.nextInt();}}intmaxIsland=0;boolean[][]visited=newboolean[n][m];for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(!visited[i][j]&&graph[i][j]==1){count=0;dfs(graph,visited,i,j,mark);mapsize.put(mark,count);mark++;}maxIsland=Math.max(maxIsland,count);}}intres=maxIsland;for(inti=0;i<n;i++){for(intj=0;j<m;j++){intsize=1;if(graph[i][j]==0){setsize.clear();for(intk=0;k<4;k++){intneari=i+dir[k][0];intnearj=j+dir[k][1];if(neari<0||nearj<0||neari>=graph.length||nearj>=graph[0].length){continue;}Integercur_key=graph[neari][nearj];if(mapsize.containsKey(cur_key)&&!setsize.contains(cur_key)){size+=mapsize.get(cur_key);setsize.add(cur_key);}}res=Math.max(res,size);}}}System.out.println(res);}}