java实现第九届蓝桥杯整理玩具

整理玩具

小明有一套玩具，一共包含NxM个部件。这些部件摆放在一个包含NxM个小格子的玩具盒中，每个小格子中恰好摆放一个部件。

每一个部件上标记有一个0~9的整数，有可能有多个部件标记相同的整数。

小明对玩具的摆放有特殊的要求：标记相同整数的部件必须摆在一起，组成一个矩形形状。

如以下摆放是满足要求的：

00022

00033

44444

12244

12244

12233

01234

56789

以下摆放不满足要求：

11122

11122

33311

111111

122221

122221

111111

11122

11113

33333

给出一种摆放方式，请你判断是否符合小明的要求。

输入

输入包含多组数据。

第一行包含一个整数T，代表数据组数。 (1 <= T <= 10)

以下包含T组数据。

每组数据第一行包含两个整数N和M。 (1 <= N, M <= 10)

以下包含N行M列的矩阵，代表摆放方式。

输出

对于每组数据，输出YES或者NO代表是否符合小明的要求。

【样例输入】

3

3 5

00022

00033

44444

3 5

11122

11122

33311

2 5

01234

56789

【样例输出】

YES

NO

YES

资源约定：

峰值内存消耗（含虚拟机） < 256M

CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

不要使用package语句。不要使用jdk1.7及以上版本的特性。

主类的名字必须是：Main，否则按无效代码处理。

PS：

分析

一开始想着用连通性做，发现挺麻烦的，后来主要思考矩形这个条件限制，想到了一个非常巧妙的做法。

既然是矩形，那就必然有固定的长和宽，那么我们为每一种玩具设置矩形的边界值，用maxX、maxY、minX、minY来确定矩形的范围。先假设所有的玩具都是符合在一个矩形中这个条件。读取数据不断更新更新矩形的边界，最后比较每种矩形是否有重叠的部分，如果有，说明存在不在一个矩形内的玩具，则是NO。

注：矩形重叠的充分必要条件是：横轴上矩形A的右边界值大于等于矩形B的左边界值且矩形A的左边界值小于等于矩形B的右边界值，同时竖轴上矩形A的上边界值大于等于矩形B的下边界值且矩形A的下边界值小于等于矩形B的上边界值。

import java.util.Scanner;;

class Fanwei {

	int minX;

	int maxX;

	int minY;

	int maxY;

	Fanwei() {

		minX = minY = maxX = maxY = -10;

	}

}

public class Main {

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		Scanner in = new Scanner(System.in);

		int T = in.nextInt();

		for (int i = 0; i < T; i++)

		{

			boolean res = true;

			Fanwei[] fanwei = new Fanwei[10];

			for (int j = 0; j < 10; j++)

				fanwei[j] = new Fanwei();

			int N = in.nextInt();

			int M = in.nextInt();

			in.nextLine();

			int[][] gezi = new int[N][M];

			for (int j = 0; j < N; j++)

			{

				char[] str = in.nextLine().toCharArray();

				for (int k = 0; k < M; k++)

				{

					gezi[j][k] = str[k]-48;

				}

			}

			for (int j = 0; j < N; j++)

			{

				for (int k = 0; k < M; k++)

				{

					int tmp = gezi[j][k];

					if (fanwei[tmp].minX == -10 || fanwei[tmp].minX > j)

						fanwei[tmp].minX = j;

					if (fanwei[tmp].maxX == -10 || fanwei[tmp].maxX < j)

						fanwei[tmp].maxX = j;

					if (fanwei[tmp].minY == -10 || fanwei[tmp].minY > k)

						fanwei[tmp].minY = k;

					if (fanwei[tmp].maxY == -10 || fanwei[tmp].maxY < k)

						fanwei[tmp].maxY = k;

				}

			}

			OUT:

			for (int j = 0; j < 9; j++)

			{

				if (fanwei[j].minX == -10)

					continue;

				for (int k = j+1; k < 10; k++)

				{

					if (fanwei[k].minX == -10)

						continue;

					if (fanwei[j].maxX >= fanwei[k].minX && fanwei[j].minX <= fanwei[k].maxX)

					{

						if (fanwei[j].maxY >= fanwei[k].minY && fanwei[j].minY <= fanwei[k].maxY)

						{

							res = false;

							break OUT;

						}

					}

				}

			}

			if (res)

				System.out.println("YES");

			else

				System.out.println("NO");

		}

	}

}

巴特西

java实现第九届蓝桥杯整理玩具

输入

输出

最新文章

热门文章