P11708 「KTSC 2020 R1」涂色

**请使用 C++17 或 C++20 提交本题** 你需要在程序开头加入如下代码： ```cpp #include long long shortcut(int N, std::vector X, std::vector Y); ``` 题目译自 [2020년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2020/) T4「 [칠하기](https://assets.ioikorea.kr/ioitst/2020/1/paint/paint_statement.pdf)」

有一个由 $N \times M$ 个格子组成的网格。网格中的一些格子是障碍物，不能通过，其他格子是可以通过的。现在我们要按照以下规则给可以通过的格子涂色。 1. 从 $N \times M$ 个格子中的一个可以通过的格子开始，作为当前格子。起始的当前格子可以是任何一个可以通过的格子。 2. 从当前格子选择一个方向（上/下/左/右），一直移动到网格的边界或遇到障碍物为止。注意，中途不能停下。 3. 如果移动过程中是水平方向（左或右），则所有水平移动经过的格子都涂成黄色。开始移动的格子也涂成黄色。如果移动过程中是垂直方向（上或下），则所有垂直移动经过的格子都涂成蓝色。开始移动的格子也涂成蓝色。（如果移动方向上立即遇到障碍物，无法移动，则开始的格子也会被涂色。） 4. 如果所有可以通过的格子至少被涂成一次黄色，并且至少被涂成一次蓝色，则涂色成功并结束涂色。 5. 如果没有达到上述条件，则从停止的格子，即最后一个可以移动的格子开始，重复步骤 2-4。如果无论如何重复这些步骤，都无法使所有可以通过的格子至少被涂成一次黄色，并且至少被涂成一次蓝色，则失败。 例如，考虑以下例子。在一个 $2 \times 3$ 的网格中，所有格子都是可以通过的。如果从左上角的 $(0,0)$ 开始，如左图和中图所示，无论如何移动，都无法使所有可以通过的格子至少被涂成一次蓝色，并且至少被涂成一次黄色。相反，如果从 $(0,1)$ 开始，如右图所示移动，则可以使所有可以通过的格子至少被涂成一次蓝色，并且至少被涂成一次黄色。  给定网格的大小和布局，我们需要判断是否可以使所有可以通过的格子被涂成蓝色和黄色。你需要实现以下函数来解决这个问题： `int yellowblue(int N, int M, vector V);` - 该函数只会被调用一次。 - 参数 $N$ 和 $M$ 表示网格的大小。 - 参数 $V$ 是表示网格状态的字符串数组，长度为 $N$。$V$ 的每个字符串长度为 $M$。如果网格的 $(i, j)$ 格子是可以通过的，则 $V[i]$ 的第 $j$ 个字符为 `.`；如果是障碍物，则为 `#`。 - 如果可以使所有可以通过的格子至少被涂成一次蓝色，并且至少被涂成一次黄色，则返回 `1`；否则返回 `0`。 你需要提交一份代码，该代码中实现以下函数： `int yellowblue(int N, int M, vector V);` 该函数应按照上述描述工作。当然，你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N\,M$（$N$：网格的行数，$M$：网格的列数） - 第 $2+i (0 \leq i \leq N-1)$ 行：由 `.` 和 `#` 组成的长度为 $M$ 的字符串。如果字符串的第 $j$ 个字符为 `.`，则表示网格的 $(i, j-1)$ 格子是可以通过的；如果为 `#`，则表示是障碍物。

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

对于所有输入数据，满足： - $1 \leq N, M \leq 1,000$ - 整个网格中至少有一个可以通过的格子。 详细子任务附加限制及分值如下表所示。 | Subtask | 分值 | 约束 | | :----------: | :----------: | :----------: | |$1$|$30$|$N, M \leq 50$| |$2$|$70$|无附加限制|