Pipes
题面翻译
给定一些特定形状的水管。有一个网格，它包含两行，每行包含$n$条水管。左上角的水管的坐标为$(1,1)$，而右下角的水管的坐标为$(2,n)$。
有六种水管：两种是直的，四种是弯曲的。形状如图所示。
你可以任意地旋转水管（每次$90$˚）。那么$1,2$号水管，$3,4,5,6$号水管就可以相互转换了。
你想要令水流通过这些水管从$(1,0)$(水流会从$(1,0)$流到左上角的水管)，流到$(1,1)$，再顺着连接着的水管到$(2,n)$并向右流到$(2,n+1)$。
当水管相邻并且当它们的末端均被连接，我们就称这些水管是连通的。
下面是连通水管的一些例子。
下面，我们将用一些例子说明这个问题。
它的解决方法如下图所示。
水流已经用蓝色的线标注了。要达到这个答案，我们要顺时针旋转$(1,2)$上的水管，$(2,3)$上的水管，$(1,6)$上的水管$90$度，$(1,7)$及$(2,7)$上的水管$180$度。那么水流就可以从$(1,0)$到达$(2,n+1)$。
你需要回答$q$次独立的询问。
题目描述
You are given a system of pipes. It consists of two rows, each row consists of $ n $ pipes. The top left pipe has the coordinates $ (1, 1) $ and the bottom right — $ (2, n) $ .
There are six types of pipes: two types of straight pipes and four types of curved pipes. Here are the examples of all six types:
Types of pipes You can turn each of the given pipes $ 90 $ degrees clockwise or counterclockwise arbitrary (possibly, zero) number of times (so the types $ 1 $ and $ 2 $ can become each other and types $ 3, 4, 5, 6 $ can become each other).
You want to turn some pipes in a way that the water flow can start at $ (1, 0) $ (to the left of the top left pipe), move to the pipe at $ (1, 1) $ , flow somehow by connected pipes to the pipe at $ (2, n) $ and flow right to $ (2, n + 1) $ .
Pipes are connected if they are adjacent in the system and their ends are connected. Here are examples of connected pipes:
Examples of connected pipes Let's describe the problem using some example:
The first example input And its solution is below:
The first example answer As you can see, the water flow is the poorly drawn blue line. To obtain the answer, we need to turn the pipe at $ (1, 2) $ $ 90 $ degrees clockwise, the pipe at $ (2, 3) $ $ 90 $ degrees, the pipe at $ (1, 6) $ $ 90 $ degrees, the pipe at $ (1, 7) $ $ 180 $ degrees and the pipe at $ (2, 7) $ $ 180 $ degrees. Then the flow of water can reach $ (2, n + 1) $ from $ (1, 0) $ .
You have to answer $ q $ independent queries.
输入格式
The first line of the input contains one integer $ q $ ( $ 1 \le q \le 10^4 $ ) — the number of queries. Then $ q $ queries follow.
Each query consists of exactly three lines. The first line of the query contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of pipes in each row. The next two lines contain a description of the first and the second rows correspondingly. Each row description consists of $ n $ digits from $ 1 $ to $ 6 $ without any whitespaces between them, each digit corresponds to the type of pipe in the corresponding cell. See the problem statement to understand which digits correspond to which types of pipes.
It is guaranteed that the sum of $ n $ over all queries does not exceed $ 2 \cdot 10^5 $ .
输出格式
For the $ i $ -th query print the answer for it — "YES" (without quotes) if it is possible to turn some pipes in a way that the water flow can reach $ (2, n + 1) $ from $ (1, 0) $ , and "NO" otherwise.
样例 #1
样例输入 #1
6
7
2323216
1615124
1
3
4
2
13
24
2
12
34
3
536
345
2
46
54样例输出 #1
YES
YES
YES
NO
YES
NO提示
The first query from the example is described in the problem statement.
这题炒鸡水啊
首先题目也告诉我们了，$1$ 和 $2$ ; $3$, $4$, $5$ 和 $6$ 分别可以相互转化，那么其实一共只有两种管子
于是一共就只需要建立一个函数模拟水流的走向
#include <string.h>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
// 1上 2左 3下(三种状态用于记录水流的来源)
int n;
char a[2][200100]; //用于存储字符串
inline void solve(int x, int y, int from) { //模拟水流
if (x == 1 && y == n) { //如果到达终点则返回
printf("YES\n");
return;
}
if (x > 1 || x < 0 || y >= n) { //如果出界则不可能到达终点
printf("NO\n");
return;
}
if (a[x][y] <= '2') {
if (from == 1 || from == 3) {
//如果管子为直管但是水流从上下流入，那么只可能从上下流出，不符合条件
printf("NO\n");
return;
} else {
solve(x, y + 1, 2); //直管只能从左流向右
}
}
if (a[x][y] > '2') {
if (from == 1) {
solve(x, y + 1, 2); //从上下流入则向右继续流
}
if (from == 2) {
solve(x == 0 ? 1 : 0, y, x == 0 ? 1 : 3); //从左流入则向上下流
}
if (from == 3) {
solve(x, y + 1, 2); //从上下流入则向右继续流
}
}
return;
}
int main() {
int q;
scanf("
while (q--) {
scanf("
scanf("
scanf("
solve(0, 0, 2);
}
return 0;
}
Comments NOTHING