day51 图论part3

文章目录卡码网 101. 孤岛的总面积卡码网 102. 沉没孤岛卡码网 103. 高山流水卡码网 104. 建造最大岛屿卡码网 101. 孤岛的总面积可以从行和列的遍历开始从边缘向中间遍历 。importjava.util.*;classMain{staticintres0;staticintcount0;staticbooleanflagfalse;publicstaticvoiddfs(int[][]graph,boolean[][]visited,intx,inty){if(visited[x][y]||graph[x][y]0){return;}if(x0||y0||xgraph.length-1||ygraph[0].length-1){flagtrue;}count;visited[x][y]true;int[][]dir{{1,0},{0,1},{-1,0},{0,-1}};for(inti0;i4;i){intnextxxdir[i][0];intnextyydir[i][1];if(nextx0||nexty0||nextxgraph.length||nextygraph[0].length){continue;}dfs(graph,visited,nextx,nexty);}}publicstaticvoidmain(String[]agrs){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();int[][]graphnewint[n][m];for(inti0;in;i){for(intj0;jm;j){graph[i][j]sc.nextInt();}}boolean[][]visitednewboolean[n][m];for(inti0;in;i){for(intj0;jm;j){if(!visited[i][j]graph[i][j]1){dfs(graph,visited,i,j);}if(flagfalse){rescount;}count0;flagfalse;}}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(inti0;i4;i){intnextxxdir[i][0];intnextyydir[i][1];if(nextx0||nexty0||nextxgraph.length||nextygraph[0].length){continue;}dfs(graph,nextx,nexty);}}publicstaticvoidmain(String[]agrs){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();int[][]graphnewint[n][m];for(inti0;in;i){for(intj0;jm;j){graph[i][j]sc.nextInt();}}for(inti0;in;i){if(graph[i][0]1){dfs(graph,i,0);}if(graph[i][m-1]1){dfs(graph,i,m-1);}}for(intj0;jm;j){if(graph[0][j]1){dfs(graph,0,j);}if(graph[n-1][j]1){dfs(graph,n-1,j);}}for(inti0;in;i){for(intj0;jm;j){if(graph[i][j]2){graph[i][j]1;}elseif(graph[i][j]1){graph[i][j]0;}}}for(inti0;in;i){for(intj0;jm;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(inti0;i4;i){intnextxxdir[i][0];intnextyydir[i][1];if(nextx0||nexty0||nextxgraph.length||nextygraph[0].length){continue;}if(graph[x][y]graph[nextx][nexty]){dfs(graph,visited,nextx,nexty);}}}publicstaticvoidmain(String[]agrs){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();int[][]graphnewint[n][m];for(inti0;in;i){for(intj0;jm;j){graph[i][j]sc.nextInt();}}boolean[][]firstbordernewboolean[n][m];boolean[][]secondbordernewboolean[n][m];for(inti0;in;i){dfs(graph,firstborder,i,0);dfs(graph,secondborder,i,m-1);}for(intj0;jm;j){dfs(graph,firstborder,0,j);dfs(graph,secondborder,n-1,j);}for(inti0;in;i){for(intj0;jm;j){if(firstborder[i][j]truesecondborder[i][j]true){System.out.print(i j);System.out.println();}}}}}卡码网 104. 建造最大岛屿先计算出所有岛屿的面积用map存储之后再把0的位置设置为1看周围面积变化。importjava.util.*;publicclassMain{staticintmark2;staticintcount0;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(inti0;i4;i){intnextxxdir[i][0];intnextyydir[i][1];if(nextx0||nexty0||nextxgraph.length||nextygraph[0].length){continue;}if(graph[nextx][nexty]1){dfs(graph,visited,nextx,nexty,mark);}}}publicstaticvoidmain(String[]agrs){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();int[][]graphnewint[n][m];HashMapInteger,IntegermapsizenewHashMap();HashSetIntegersetsizenewHashSet();for(inti0;in;i){for(intj0;jm;j){graph[i][j]sc.nextInt();}}intmaxIsland0;boolean[][]visitednewboolean[n][m];for(inti0;in;i){for(intj0;jm;j){if(!visited[i][j]graph[i][j]1){count0;dfs(graph,visited,i,j,mark);mapsize.put(mark,count);mark;}maxIslandMath.max(maxIsland,count);}}intresmaxIsland;for(inti0;in;i){for(intj0;jm;j){intsize1;if(graph[i][j]0){setsize.clear();for(intk0;k4;k){intneariidir[k][0];intnearjjdir[k][1];if(neari0||nearj0||nearigraph.length||nearjgraph[0].length){continue;}Integercur_keygraph[neari][nearj];if(mapsize.containsKey(cur_key)!setsize.contains(cur_key)){sizemapsize.get(cur_key);setsize.add(cur_key);}}resMath.max(res,size);}}}System.out.println(res);}}