AT_utpc2025_h.Heyawake-like Problem

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

有一个 $ (3N+1) $ 行 $ (3N+1) $ 列的方格。请你判断是否可以将每个格子涂成「黑色」或「白色」,使其满足从下述所有条件。如果存在满足条件的涂色方案,请给出一种。

  • 不同的黑色格子不能通过边相邻。
  • 对于任意一个黑色格子,从它出发,只能经过角相邻的黑色格子(允许经过 $ 0 $ 次),都可以到达位于方格外周上的某一个黑色格子。
  • 所有的白色格子需要整体连通。即对于任意两个白格,可以只经过边相邻的白格(允许经过 $ 0 $ 次),从一个格子走到另一个格子。
  • 有 $ 2 $ 行各有 $ N+1 $ 个黑格,其余每行各有 $ N $ 个黑格。
  • 有 $ 2 $ 列各有 $ N+1 $ 个黑格,其余每列各有 $ N $ 个黑格。

输入格式

输入从标准输入读取,格式如下:

$ N $

输出格式

如果不存在满足条件的涂色方案,请输出一行 No。否则,输出一种满足条件的方案。对于第 $ i $ 行第 $ j $ 列的格子,如果为白色则 $ a_{i,j} $ 为 .,如果为黑色则为 #。

Yes
$ a_{1,1} \dots a_{1,3N+1} \vdots a_{3N+1,1} \dots a_{3N+1,3N+1} $

若存在多个方案,输出任意一种均可。

输入输出样例

  • 输入#1

    1

    输出#1

    No

说明/提示

样例说明 1

如下三个输出样例均为 $ N=1 $ 的输出格式,但因不满足题面条件,均判定为不正确。

Yes
##..
#...
...#
..##
Yes
#.#.
...#
#.#.
.#..
Yes
...#
.#..
..#.
#...

第 1 个样例中,黑格通过边相邻。
第 2 个样例中,白格整体并不连通。
第 3 个样例中,不符合黑格个数的条件,且第 2 行第 2 列的黑格出发,无法通过角相邻的黑格到达外周的黑色格子。

已知 $ N=1 $ 时,不存在满足条件的涂色方案。

数据范围

  • 输入均为整数
  • $ 1 \leq N \leq 500 $

由 ChatGPT 5 翻译

输入解题思路,AI测评打分。不知道怎么写?

首页