AT_arc031_2.[ARC031B] 埋め立て

普及+/提高

通过率:0%

AC君温馨提醒

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

题目描述

很久很久以前,某地曾有一个岛国。这个岛国由一些岛屿组成。现在,这个岛国决定填海造陆,但还没有决定填海造陆的位置。政府希望填海造陆工程能够将所有岛屿连接起来,成为一个岛屿。

给出 1010 格 ×10×10 格的该国地图,请判断:能否仅将一格海洋变成陆地,使该国所有岛屿连接成一个岛屿。另外,地图中表示陆地的格子上下左右互相连接的区域称为一个岛屿。

输入格式

输入按以下形式:

A1,1 A1,2 … A1,10A_{1,1} \space A_{1,2} \space \dots \space A_{1,10}

A2,1 A2,2 … A2,10A_{2,1} \space A_{2,2} \space \dots \space A_{2,10}

::

A10,1 A10,2 … A10,10A_{10,1} \space A_{10,2} \space \dots \space A_{10,10}

  • 岛国的地图一定为 1010 行。
  • 每行一定由 1010 个字符组成,每个字符为 'o'(表示陆地)或 'x'(表示海洋)
  • 保证至少有一格为陆地。
  • 保证至少有一格为海洋。

输出格式

如果能将 11 个格子的海洋变成陆地使得整个岛国只含一个岛屿,则输出'YES',否则输出'NO'。输出结尾请换行。
(如果本来就只有一个岛,也输出'YES')

样例1解释

将红色方框处的格子变成陆地,就能将两个岛屿合并为一个。

输入输出样例

  • 输入#1

    xxxxxxxxxx
    xoooooooxx
    xxoooooxxx
    xxxoooxxxx
    xxxxoxxxxx
    xxxxxxxxxx
    xxxxoxxxxx
    xxxoooxxxx
    xxoooooxxx
    xxxxxxxxxx

    输出#1

    YES
  • 输入#2

    xxxxxxxxxx
    xoooooooxx
    xxoooooxxx
    xxxoooxxxx
    xxxxxxxxxx
    xxxxxxxxxx
    xxxxxxxxxx
    xxxoooxxxx
    xxoooooxxx
    xxxxxxxxxx

    输出#2

    NO
  • 输入#3

    xxxxoxxxxx
    xxxxoxxxxx
    xxxxoxxxxx
    xxxxoxxxxx
    ooooxooooo
    xxxxoxxxxx
    xxxxoxxxxx
    xxxxoxxxxx
    xxxxoxxxxx
    xxxxoxxxxx

    输出#3

    YES

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

首页