#P11708. 「KTSC 2020 R1」涂色

「KTSC 2020 R1」涂色

题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码:

#include<vector>

long long shortcut(int N, std::vector<long long> X, std::vector<long long> Y);
  

题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T4「 칠하기

题目描述

有一个由 N×MN \times M 个格子组成的网格。网格中的一些格子是障碍物,不能通过,其他格子是可以通过的。现在我们要按照以下规则给可以通过的格子涂色。

  1. N×MN \times M 个格子中的一个可以通过的格子开始,作为当前格子。起始的当前格子可以是任何一个可以通过的格子。
  2. 从当前格子选择一个方向(上/下/左/右),一直移动到网格的边界或遇到障碍物为止。注意,中途不能停下。
  3. 如果移动过程中是水平方向(左或右),则所有水平移动经过的格子都涂成黄色。开始移动的格子也涂成黄色。如果移动过程中是垂直方向(上或下),则所有垂直移动经过的格子都涂成蓝色。开始移动的格子也涂成蓝色。(如果移动方向上立即遇到障碍物,无法移动,则开始的格子也会被涂色。)
  4. 如果所有可以通过的格子至少被涂成一次黄色,并且至少被涂成一次蓝色,则涂色成功并结束涂色。
  5. 如果没有达到上述条件,则从停止的格子,即最后一个可以移动的格子开始,重复步骤 2-4。如果无论如何重复这些步骤,都无法使所有可以通过的格子至少被涂成一次黄色,并且至少被涂成一次蓝色,则失败。

例如,考虑以下例子。在一个 2×32 \times 3 的网格中,所有格子都是可以通过的。如果从左上角的 (0,0)(0,0) 开始,如左图和中图所示,无论如何移动,都无法使所有可以通过的格子至少被涂成一次蓝色,并且至少被涂成一次黄色。相反,如果从 (0,1)(0,1) 开始,如右图所示移动,则可以使所有可以通过的格子至少被涂成一次蓝色,并且至少被涂成一次黄色。

给定网格的大小和布局,我们需要判断是否可以使所有可以通过的格子被涂成蓝色和黄色。你需要实现以下函数来解决这个问题:

int yellowblue(int N, int M, vector<string> V);

  • 该函数只会被调用一次。
  • 参数 NNMM 表示网格的大小。
  • 参数 VV 是表示网格状态的字符串数组,长度为 NNVV 的每个字符串长度为 MM。如果网格的 (i,j)(i, j) 格子是可以通过的,则 V[i]V[i] 的第 jj 个字符为 .;如果是障碍物,则为 #
  • 如果可以使所有可以通过的格子至少被涂成一次蓝色,并且至少被涂成一次黄色,则返回 1;否则返回 0

你需要提交一份代码,该代码中实现以下函数:

int yellowblue(int N, int M, vector<string> V);

该函数应按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

输入格式

示例评测程序按以下格式读取输入:

  • 11 行:NMN\,MNN:网格的行数,MM:网格的列数)
  • 2+i(0iN1)2+i (0 \leq i \leq N-1) 行:由 .# 组成的长度为 MM 的字符串。如果字符串的第 jj 个字符为 .,则表示网格的 (i,j1)(i, j-1) 格子是可以通过的;如果为 #,则表示是障碍物。

输出格式

示例评测程序将输出你的代码中 yellowblue() 函数返回的值。

1 1
.

1
2 3
...
...

1

3 3
...
..#
.##

1
3 3
.##
#..
#..

0

提示

对于所有输入数据,满足:

  • 1N,M1,0001 \leq N, M \leq 1,000
  • 整个网格中至少有一个可以通过的格子。

详细子任务附加限制及分值如下表所示。

Subtask 分值 约束
11 3030 N,M50N, M \leq 50
22 7070 无附加限制