4 条题解
-
0
蒟蒻的题解，本题主要思路就是：遍历一遍地图，每次遇到了1就dfs把与他相邻的1以及它本身全都搞成0，同时计数器+1 ，这样遍历完一遍岛屿数量也就出来了！！
//package TemplateQuestion; import javax.annotation.processing.SupportedSourceVersion; import java.io.*; public class Main{ //岛屿的数量 ，看到题目就知道是tmd DFS了。。. static int n; static int [][]arr; static int count; static StreamTokenizer st; static PrintWriter pw; static int []mx={-1,1,0,0}; static int []my={0,0,-1,1}; static void dfs(int a,int b) { arr[a][b]=0; for(int i=0;i<4;i++) { int tx=a+mx[i]; int ty=b+my[i]; if(tx<1||tx>n||ty<1||ty>n||arr[tx][ty]==0) { continue; } dfs(tx,ty); } } public static void main(String[] args) throws IOException { st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); pw=new PrintWriter(System.out); count=0; st.nextToken(); n= (int) st.nval; arr=new int[n+1][n+1]; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { st.nextToken(); arr[i][j]= (int) st.nval; } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(arr[i][j]==1) { count++; dfs(i,j); } } } System.out.println(count); } } -
0
如下：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int ans = 0, n; static int[][] map; static int[] dx = { -1, 1, 0, 0 }; static int[] dy = { 0, 0, -1, 1 }; public static void main(String[] args) { solve(); out.flush(); } static void solve() { n = in.nextInt(); map = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { map[i][j] = in.nextInt(); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (map[i][j] == 1) { ans++; bfs(i, j); } } } out.print(ans); } /** * 第一个版本的BFS * @param x * @param y */ static void bfs(int x, int y) { Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[] { x, y }); map[x][y] = 0; while (!queue.isEmpty()) { int[] cur = queue.poll(); int curx = cur[0]; int cury = cur[1]; for (int i = 0; i < dx.length; i++) { int newx = curx + dx[i]; int newy = cury + dy[i]; if (!check(newx, newy) || map[newx][newy] != 1) { continue; } queue.offer(new int[] { newx, newy }); map[newx][newy] = 0; } } } /** * 另一个版本BFS * @param x * @param y */ static void bfs1(int x, int y) { Queue<Pair> queue = new LinkedList<>(); queue.offer(new Pair(x, y)); map[x][y] = 0; while (!queue.isEmpty()) { Pair curPair = queue.poll(); int curx = curPair.x; int cury = curPair.y; for (int i = 0; i < dx.length; i++) { int newx = curx + dx[i]; int newy = cury + dy[i]; if (!check(newx, newy) || map[newx][newy] != 1) { continue; } queue.offer(new Pair(newx, newy)); map[newx][newy] = 0; } } } static class Pair { int x; int y; public Pair(int x, int y) { super(); this.x = x; this.y = y; } } /** * DFS版本 * @param x * @param y */ static void dfs(int x, int y) { for (int i = 0; i < dx.length; i++) { int newx = x + dx[i]; int newy = y + dy[i]; if (!check(newx, newy)) { continue; } if (map[newx][newy] != 1) { continue; } map[newx][newy] = 0; dfs(newx, newy); } } private static boolean check(int newx, int newy) { if (newx >= n || newy >= n || newx < 0 || newy < 0) { return false; } return true; } static FastReader in = new FastReader(); static PrintWriter out = new PrintWriter(System.out); static class FastReader { static BufferedReader br; static StringTokenizer st; FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } double nextDouble() { return Double.parseDouble(next()); } Long nextLong() { return Long.parseLong(next()); } } }-
时崎狂三 @ 2025-5-25 12:25:16
牛，思路好全面
-
-
0
岛屿的个数
这题用dfs染色法的思想，可以很快解决，简单来说，就是每次进入dfs时，都把周围的陆地都染色，这样保证了每次进入的都是一个新岛屿 代码如下：
#include<bits/stdc++.h> using namespace std; const int N=505; int n,mp[N][N],ans; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; bool check(int x,int y){ return (x>=1&&x<=n&&y>=1&&y<=n&&mp[x][y]==1); } void dfs(int x,int y){ mp[x][y]=2; for(int i=0;i<4;i++){ int cur_x=x+dx[i],cur_y=y+dy[i]; if(check(cur_x,cur_y)){ dfs(cur_x,cur_y); } } } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>mp[i][j]; } } //dfs染色法 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(mp[i][j]==1){ dfs(i,j); ans++; } } } cout<<ans; return 0; }学会了可以试试岛屿个数这道题，也可以用染色法的思想解决～
-
0
JAVA ac代码:
package abcd; import java.util.*; import java.util.StringTokenizer; import java.io.*; public class Main { static int n; static int[][] a;//矩阵 static int ans=0;//答案 static int[] dx= {0,0,-1,1}; static int[] dy= {1,-1,0,0}; public static void main(String[] args) { n=in.nextInt(); a=new int[n][n]; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { a[i][j]=in.nextInt(); } } //遍历图 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { //当这个点是陆地 if(a[i][j]==1) { ans++;//岛屿数+1 bfs(i,j);//将相连的陆地全部设置为0 } } } out.println(ans); out.close(); } private static void bfs(int i, int j) { Queue<int[]> q=new LinkedList<>(); q.add(new int[]{i,j});//将当前点入队 //遍历直到周围都是0 while(!q.isEmpty()) { //获得当前相连陆地点的坐标 int[] temp=q.poll(); int x=temp[0]; int y=temp[1]; //枚举这个坐标上下左右四个点 for(int k=0;k<4;k++) { int x1=x+dx[k]; int y1=y+dy[k]; //越界分析和是海洋 if(x1<0||y1<0||x1>=n||y1>=n||a[x1][y1]==0)continue; q.add(new int[] {x1,y1}); a[x1][y1]=0;//设置为海洋，不再遍历 } } } static FastReader in=new FastReader(); static PrintWriter out=new PrintWriter(System.out); static class FastReader{ static BufferedReader br; static StringTokenizer st; FastReader(){ br=new BufferedReader(new InputStreamReader(System.in)); } String next() { String str=""; while(st==null||!st.hasMoreElements()) { try { str=br.readLine(); }catch(IOException e) { throw new RuntimeException(e); } st=new StringTokenizer(str); } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } double nextDouble() { return Double.parseDouble(next()); } long nextLong() { return Long.parseLong(next()); } } }
- 1