P1162_填涂颜色(JAVA语言)(速看！全洛谷最暴力解法！QAQ)

思路：看了看数据n<=30,于是我们可以暴力求解（主要是BFS学的不咋地~2333）。枚举每个0的位置，看上下左右四个方向上是否都有1。都有1的话说明被1包围，即在闭合圈的内部，开个数组标记一下，最后判断是否被标记输出即可。另外，我们可以手动给数组增加两个宽度，这样就不需要特判边界了~

题目描述

由数字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

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		Scanner in=new Scanner(System.in);

		int n=in.nextInt();

		int a[][]=new int[n+2][n+2];//手动增加边界

		boolean b[][]=new boolean[n+2][n+2];//标记数组

		for(int i=1;i<=n;i++)//读入不解释

			for(int j=1;j<=n;j++)

				a[i][j]=in.nextInt();

		for(int i=1;i<=n;i++)

		{

			for(int j=1;j<=n;j++)

			{

				if(a[i][j]==0)

				{

					if(isCircle(a,i,j,n))//如果在该点在闭合圈内部，做标记

					{

						b[i][j]=true;

					}

				}

			}

		}

		for(int i=1;i<=n;i++){

			for(int j=1;j<=n;j++)

			{

				if(b[i][j])System.out.print("2 ");//如果被标记，输出2

				else System.out.print(a[i][j]+" ");//否则，按原数输出

			}

		System.out.println();

		}

	}

	private static boolean isCircle(int[][] a, int i, int j, int k) {

		// TODO Auto-generated method stub

		boolean fl=false,fr=false,fu=false,fd=false;//四个方向上是否有1的标记

		for(int c=0;c<j;c++){//左边

			if(a[i][c]==1){

				fl=true;

				break;

			}

		}

		for(int c=j+1;c<=k;c++){//右边

			if(a[i][c]==1){

				fr=true;

				break;

			}

		}

		for(int c=0;c<i;c++){//上边

			if(a[c][j]==1){

				fu=true;

				break;

			}

		}

		for(int c=i+1;c<=k;c++){//下边

			if(a[c][j]==1){

				fd=true;

				break;

			}

		}

		if(fl&&fr&&fu&&fd)return true;

		else return false;

	}

}

巴特西

P1162_填涂颜色(JAVA语言)(速看！全洛谷最暴力解法！QAQ)

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章