#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「 칠하기」
题目描述
有一个由 个格子组成的网格。网格中的一些格子是障碍物,不能通过,其他格子是可以通过的。现在我们要按照以下规则给可以通过的格子涂色。
- 从 个格子中的一个可以通过的格子开始,作为当前格子。起始的当前格子可以是任何一个可以通过的格子。
- 从当前格子选择一个方向(上/下/左/右),一直移动到网格的边界或遇到障碍物为止。注意,中途不能停下。
- 如果移动过程中是水平方向(左或右),则所有水平移动经过的格子都涂成黄色。开始移动的格子也涂成黄色。如果移动过程中是垂直方向(上或下),则所有垂直移动经过的格子都涂成蓝色。开始移动的格子也涂成蓝色。(如果移动方向上立即遇到障碍物,无法移动,则开始的格子也会被涂色。)
- 如果所有可以通过的格子至少被涂成一次黄色,并且至少被涂成一次蓝色,则涂色成功并结束涂色。
- 如果没有达到上述条件,则从停止的格子,即最后一个可以移动的格子开始,重复步骤 2-4。如果无论如何重复这些步骤,都无法使所有可以通过的格子至少被涂成一次黄色,并且至少被涂成一次蓝色,则失败。
例如,考虑以下例子。在一个 的网格中,所有格子都是可以通过的。如果从左上角的 开始,如左图和中图所示,无论如何移动,都无法使所有可以通过的格子至少被涂成一次蓝色,并且至少被涂成一次黄色。相反,如果从 开始,如右图所示移动,则可以使所有可以通过的格子至少被涂成一次蓝色,并且至少被涂成一次黄色。
给定网格的大小和布局,我们需要判断是否可以使所有可以通过的格子被涂成蓝色和黄色。你需要实现以下函数来解决这个问题:
int yellowblue(int N, int M, vector<string> V);
- 该函数只会被调用一次。
- 参数 和 表示网格的大小。
- 参数 是表示网格状态的字符串数组,长度为 。 的每个字符串长度为 。如果网格的 格子是可以通过的,则 的第 个字符为
.
;如果是障碍物,则为#
。 - 如果可以使所有可以通过的格子至少被涂成一次蓝色,并且至少被涂成一次黄色,则返回
1
;否则返回0
。
你需要提交一份代码,该代码中实现以下函数:
int yellowblue(int N, int M, vector<string> V);
该函数应按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。
输入格式
示例评测程序按以下格式读取输入:
- 第 行:(:网格的行数,:网格的列数)
- 第 行:由
.
和#
组成的长度为 的字符串。如果字符串的第 个字符为.
,则表示网格的 格子是可以通过的;如果为#
,则表示是障碍物。
输出格式
示例评测程序将输出你的代码中 yellowblue()
函数返回的值。
1 1
.
1
2 3
...
...
1
3 3
...
..#
.##
1
3 3
.##
#..
#..
0
提示
对于所有输入数据,满足:
- 整个网格中至少有一个可以通过的格子。
详细子任务附加限制及分值如下表所示。
Subtask | 分值 | 约束 |
---|---|---|
无附加限制 |