4 条题解

  • 0
    @ 2025-5-11 18:30:49

    如下:

    
    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());
    		}
    	}
    }
    
    

信息

ID
33
时间
1000ms
内存
256MiB
难度
3
标签
递交数
33
已通过
19
上传者