由数字00组成的方阵中,有一任意形状闭合圈,闭合圈由数字11构成,围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如:6 \times 66×6的方阵(n=6n=6),涂色前和涂色后的方阵如下:
0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1
每组测试数据第一行一个整数n(1 \le n \le 30)n(1≤n≤30)
接下来nn行,由00和11组成的n \times nn×n的方阵。
方阵内只有一个闭合圈,圈内至少有一个00。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
已经填好数字22的完整方阵。
输入 #1复制
6 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1
输出 #1复制
0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1
1 \le n \le 301≤n≤30
我的思想:这道题,我认为还是蛮简单的,使用的方法是广度搜索。解题的步骤:进入环内,进行广度搜索,只要遇到不是1,就把它填涂为2。第一个1的右下角肯定是0。
这是进入这个环的关键。直接上代码吧
package com.wu.bfs; import java.util.Scanner; public class Main { static int[] dx={1,0,-1,0}; static int[] dy={0,-1,0,1}; static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt()+1; int map[][]=new int[n][n]; for (int i=1;i<n;i++){ for (int j=1;j<n;j++){ map[i][j]=sc.nextInt(); } } for (int i=1;i<n;i++){ for (int j=1;j<n;j++){ if (map[i][j]==1){ bfs(map,i+1,j+1); //终止符.找到开始坐标跳出两个循环 i=40; j=40; } } } for (int i=1;i<n;i++){ for (int j=1;j<n;j++){ System.out.print(map[i][j]+" "); } System.out.println(); } } //广度搜索 private static void bfs(int[][] map, int x, int y) { map[x][y]=2; for (int k=0;k<4;k++){ int x1=x+dx[k]; int y1=y+dy[k]; //标记 if (x1<1||y1<1||x1>n||y1>n||map[x1][y1]==1||map[x1][y1]==2){ //走不通,中断.重新选择一个方向 continue; } bfs(map,x1,y1); } } }