Pipes CodeForces - 1234C（dfs）-白红宇

Pipes CodeForces - 1234C（dfs）

阅读量：4135 次

发布时间：2019-05-25

本文共 4125 字，大约阅读时间需要 13 分钟。

You are given a system of pipes. It consists of two rows, each row consists of nn pipes. The top left pipe has the coordinates (1,1)(1,1) and the bottom right — (2,n)(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 9090 degrees clockwise or counterclockwise arbitrary (possibly, zero) number of times (so the types 11 and 22 can become each other and types 3,4,5,63,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)(1,0) (to the left of the top left pipe), move to the pipe at (1,1)(1,1), flow somehow by connected pipes to the pipe at (2,n)(2,n) and flow right to (2,n+1)(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)(1,2) 9090 degrees clockwise, the pipe at (2,3)(2,3) 9090 degrees, the pipe at (1,6)(1,6) 9090 degrees, the pipe at (1,7)(1,7) 180180 degrees and the pipe at (2,7)(2,7) 180180 degrees. Then the flow of water can reach (2,n+1)(2,n+1) from (1,0)(1,0).

You have to answer qq independent queries.

Input

The first line of the input contains one integer qq (1≤q≤1041≤q≤104) — the number of queries. Then qq queries follow.

Each query consists of exactly three lines. The first line of the query contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — 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 nn digits from 11 to 66 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 nn over all queries does not exceed 2⋅1052⋅105.

Output

For the ii-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)(2,n+1) from (1,0)(1,0), and “NO” otherwise.

Example

Input

2323216

1615124

536

345

Output

YES

Note

The first query from the example is described in the problem statement.

题意：总共有六种水管，可以旋转，拼接。问能否可以使水流从(1,1)流到(2,n)。

思路：1-2是一类，3-6是另一类。直接dfs求就可以了，注意细节。

代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=2e5+100;char s[5][maxx];int n;inline void dfs(int x,int y,int &flag){
   	if(flag) return ;	if(x>2||x<1||y<1||y>n) return ;	if(x==2&&y==n&&(s[x][y]=='1'||s[x][y]=='6'))//到达了(2,n)后也不能判断是否能流出去，必须是可以流到(2,n+1)才行。	{
   		flag=1;		return ;	}	if(s[x][y]=='1') 	{
   		if(y+1>n) return ;		char c=s[x][y+1];		if(c=='2'||c=='1') s[x][y+1]='1';		else if(x==1) s[x][y+1]='4';		else if(x==2) s[x][y+1]='5';//当前是1的时候，需要分情况讨论第一行，第二行的情况。		dfs(x,y+1,flag);		s[x][y+1]=c;	}	else if(s[x][y]=='2') return ;//2的时候直接不行	else if(s[x][y]=='3') //3以后就直接根据情况讨论。	{
   		if(y+1>n) return ;		char c=s[x][y+1];		if(c=='2'||c=='1') s[x][y+1]='1';		else s[x][y+1]='4';		dfs(x,y+1,flag);		s[x][y+1]=c;	}	else if(s[x][y]=='4')	{
   		if(x+1>2) return ;		char c=s[x+1][y];		if(c=='1'||c=='2') return ;		else s[x+1][y]='6';		dfs(x+1,y,flag);		s[x+1][y]=c;	}	else if(s[x][y]=='5')	{
   		if(x-1<1) return ;		char c=s[x-1][y];		if(c=='1'||c=='2') return ;		else s[x-1][y]='3';		dfs(x-1,y,flag);		s[x-1][y]=c;	}	else if(s[x][y]=='6') 	{
   		if(y+1>n) return ;		char c=s[x][y+1];		if(c=='1'||c=='2') s[x][y+1]='1';		else s[x][y+1]='5';		dfs(x,y+1,flag);		s[x][y+1]=c;	}}int main(){
   	int t;	scanf("%d",&t);	while(t--)	{
   		scanf("%d",&n);		for(int i=1;i<=2;i++) scanf("%s",s[i]+1);		int flag=0;		if(s[1][1]=='2'||s[1][1]=='1') s[1][1]='1';//一开始必须能流进(1,1)。		else s[1][1]='4';		dfs(1,1,flag);		if(flag) puts("YES");		else puts("NO");	}	return 0;}

努力加油a啊，(^o)/~

转载地址：http://hytvi.baihongyu.com/

你可能感兴趣的文章