CF1949J.Amanda the Amoeba

省选/NOI-

通过率:0%

AC君温馨提醒

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

题目描述

如图,r×cr\times c 的网格中有一只变形虫。每个格子有三种状态:被变形虫的身体占据(绿色),空白(白色),或存在障碍物(黑色)。

每次移动,先将身体占据的格子之一变为空白,然后再把某个与身体相邻的空白格子变为身体所占据。两个格子相邻当且仅当有公共边。移动过程中要保证身体是连通的,且不占据障碍物。

已知变形虫初始占据了哪些格子,它想移动到占据着给出的另一些格子(虚线内)的状态。求任意一种方案。

输入格式

第一行 r,c.r, c.

下面的 rr 行 cc 列,表示初始状态;接下去又有 rr 行 cc 列,表示目标状态。其中,* 表示变形虫的身体,. 表示空白,X 表示障碍。

r,c≤50r, c\leq 50

输出格式

若不存在方案,输出 NO;否则先输出一行 YES,然后一行一个整数 mm 表示移动次数。

接下来 mm 行,每行 44 个整数 x1,y1,x2,y2x_1, y_1, x_2, y_2 表示该次移动时,变空白的格子、新占据的格子。

可以证明只要有方案,就存在 m≤104m\leq 10^4 的方案。

输入输出样例

  • 输入#1

    5 8
    .******.
    **.X**..
    *******.
    **.X**..
    .******.
    
    
    .******.
    ...X****
    .*******
    ...X****
    .******.

    输出#1

    YES
    5
    3 1 3 8
    2 1 2 8
    4 1 4 8
    2 2 4 7
    4 2 2 7
  • 输入#2

    2 5
    *.X..
    **X..
    
    
    ..X**
    ..X*.

    输出#2

    NO

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

首页