P1162 填涂颜色 java_bfs

分析

1. 此题我们可以用bfs，题意就是把被1包围的部分改为2，故我们可以把1理解为墙，不能通过1往后搜索，通过vis数组去记录哪些点未被访问，最后我们可以通过map的值是否0加上是否访问过，即可确定吐的范围；
2. 数组的周围加一个框，就是方阵的行、列有效范围是从1到n， 但我们从0,0开始搜索，可以避免遇到方阵的第一个点就是1，直接堵死了，无路可走；
3. 关于四个方向走的问题，我们可以通过一个四层for循环加上x、y的偏移量数组去简化问题；

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int n;static int[][] vis = new int[35][35];static int[][] map = new int[35][35];static int[] dx = { -1, 0, 1, 0 };static int[] dy = { 0, 1, 0, -1 };static Queue<Integer> x = new LinkedList<>();static Queue<Integer> y = new LinkedList<>();static void bfs() {// 从0,0点开始搜索vis[0][0] = 1;x.offer(0);y.offer(0);while (!x.isEmpty()) {// 队列已经有的那个点0,0开始向四个方向搜索for (int k = 0; k < 4; k++) {int xx = x.peek() + dx[k];int yy = y.peek() + dy[k];if (xx >= 0 && yy >= 0 && xx <= n + 1 && yy <= n + 1 && vis[xx][yy] == 0 && map[xx][yy] == 0) {// 不能越界且，遇到1相当于墙，不能搜索他及其后面的x.offer(xx);y.offer(yy);vis[xx][yy] = 1;}}x.poll();y.poll();}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();for (int i = 1; i <= n; i++) {// 数组外面套一圈0；for (int j = 1; j <= n; j++) {map[i][j] = sc.nextInt();}}bfs();// 最后没被遍历到的点且该点的值为0，就是被1包围住的点，即需要输出2for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (map[i][j] == 0 && vis[i][j] == 0) {System.out.print(2 + " ");} else {System.out.print(map[i][j] + " ");}}System.out.println();}}
}