题目背景

请使用 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 \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<string> V);

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

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

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

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

输入格式

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

• 第 $1$ 行：$N\,M$（$N$：网格的行数，$M$：网格的列数）
• 第 $2+i (0 \leq i \leq N-1)$ 行：由 . 和 # 组成的长度为 $M$ 的字符串。如果字符串的第 $j$ 个字符为 .，则表示网格的 $(i, j-1)$ 格子是可以通过的；如果为 #，则表示是障碍物。

输出格式

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

1 1
.

1

2 3
...
...

1

3 3
...
..#
.##

1

3 3
.##
#..
#..

0

提示

对于所有输入数据，满足：

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

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

Subtask	分值	约束
$1$	$30$	$N, M \leq 50$
$2$	$70$	无附加限制