4 条题解
-
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()); } } }
信息
- ID
- 33
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 33
- 已通过
- 19
- 上传者