← 返回题目列表

AtCoder · ahc024_a

A. 拓扑图

中文机器翻译题面 查看原题

故事

高桥市市长高桥先生决定使用彩色方形瓷砖在市政厅大厅的地板上绘制高桥市地图。 高桥市分为多个区,在这张地图中,每个区应表示为一组相同颜色的相连瓷砖。 他委托承包商绘制了一份精确的地图草稿,但使用的瓷砖数量过多,超出了预算。 喜欢图表的高桥市长只对区之间的邻接关系感兴趣,认为如果忽略邻接关系以外的信息,例如每个区的形状和大小,可以用更少的图块来绘制地图。 请使用尽可能少的图块创建地图。

准确的地图

小地图正确表示邻接

问题陈述

给定一张以网格表示的高桥市地图 n\times n 方块。 让 (0,0) 是左上角正方形的坐标,并且 (i,j) 是所在正方形的坐标 i 向下平方并 从那里向右走 j 方块。 该城市由 m 病房和彩色方块 c (1\leq c\leq m) 对应于 c第病房。 的外侧 n\times n 方块对应于城市的外部并且是彩色的 0.

如果两个方块共享一条边,则它们被定义为“相邻”;如果任意两个方块可以通过相邻方块相互到达,则一组方块被定义为“相连”。 在给定的图中,对于每种颜色 c,保证颜色 c 的方块集是连通的。

你的任务是创建一个以网格表示的地图 n\times n 满足以下所有条件的正方形。

  • 对于每种颜色 c (0\leq c\leq m),颜色方块 必须连接 c 。请注意,由于外部 n\times n 方块是彩色的 0,颜色方块 0 可以通过外部方块连接。
  • 对于每对颜色 c 和 d (0\leq c<d\leq m),一组颜色方块的邻接 c 和一组颜色方块 原始地图和创建的地图中的 d 必须相同。也就是说,当且仅当存在相邻的颜色方块 c 和 d 原图中存在相邻的颜色方块 创建的地图中的 c 和 d 。请注意,由于外部 n\times n 方块是彩色的 0,边界上的方块被认为与颜色方块相邻 0.

评分

让 E 是颜色方块的总数 创建的地图中的 0 。 那么你将获得分数 E+1.

共有150个测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

输入由标准输入按以下格式给出。

n m
c_{0,0} c_{0,1} \cdots c_{0,n-1}
\vdots
c_{n-1,0} c_{n-1,1} \cdots c_{n-1,n-1}

对于所有测试用例,我们修复 n = 50 和 m = 100. c_{i,j} 是一个整数值,表示坐标处正方形的颜色 (i,j) 并满足 1\leq c_{i,j}\leq m。 对于每一个 k=1,2,\cdots,m,至少存在一个 (i,j) 与 c_{i,j}=k.

输出

让 d_{i,j} (0\leq d_{i,j}\leq m) 是坐标处正方形的颜色 创建的地图中的 (i,j) 。 然后,按以下格式输出到标准输出。

d_{0,0} d_{0,1} \cdots d_{0,n-1}
\vdots
d_{n-1,0} d_{n-1,1} \cdots d_{n-1,n-1}

如果输出地图不满足问题陈述中指定的条件,则提交将被判断为 WA.

您的程序可能会输出多个解决方案。 如果输出多个解,则仅使用最后一个进行评分。 您可以使用可视化工具的网络版本来比较多个解决方案。

显示示例

输入生成

首先,我们初始化 c_{i,j}=0 对于所有人 (i,j)。 接下来,对于每个 k=1,2,\cdots,m,我们随机选择一个正方形 c_{i,j}=0 并设置 c_{i,j}=k。 最后,我们重复以下过程,同时与 c_{i,j}=0 保留。

随机选择一个正方形 c_{i,j}=0 并随机选择其相邻的方块 (i',j')。 我们设定 c_{i,j}=c_{i',j'}.

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。