Is It a Snake


Problem Statement :


One day I was visiting a temple in which snakes were worshiped. I happened to find a golden plate of dimension 2 * n in it. It had 2 rows of n cells each, and so the total number of cells is 2 * n. Each cell of the plate was either white or black, denoted by '.' and '#' respectively. Legend says that a snake was lying on this plate for many years and prayed. So, the cells that were covered by its body have turned black, the rest of the cells were white. Its entire body was supposedly on this plate. Also, you know that a snake likes to make itself comfortable, so none of its parts will be intersecting with its other parts.

Usually, I am skeptical of such legends. So, I want to check for myself whether the legend could potentially be true or not. For example, consider the golden plate given below:


##
##

Now, the legend could be true. A snake can be on it, and one possible configuration is as follows. The head of the snake is at (1, 1), then the next portion at (1, 2), then at (2, 2) and then the finally the tail at (2, 1). Notice that the parts of the snake can be adjacent only if the corresponding cells have a common side.

##.#..
.###..

There can be a snake on the plate above.


##.##
.#.#.
The legend is surely false if the plate is as above. These are not marks of a single snake. There could be more than one possible snakes here. But not a single snake.

Given the description of the plate, figure out if the legend could be true, or if it is definitely false.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains an integer n.

The next two lines each contain n characters denoting the rows of the plate.

Output

For each test case, output a single line containing "yes" or "no" (without quotes) corresponding to the answer of the problem.

Constraints
1 ≤ T ≤ 500
1 ≤ n ≤ 500
There will be at least one cell containing the character '#'

Example

Input
6
2
##
..
2
##
.#
2
#.
.#
7
#.###..
#######
6
##.#..
.###..
5
##.##
.#.#.

Output
yes
yes
no
no
yes
no



Solution :


                            Solution in C :

#include <stdio.h>
#define BLACK 0
#define WHITE 1
int main()
{
    int cases,n,i,j,start,end,prev,next;
    char c;
    scanf("%d",&cases);
    label:
    while(cases--)
    {
        scanf("%d\n",&n);
        int a[2][n];
        for(i=0;i<2;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf(" %c",&c);
                a[i][j]=(c=='.')?WHITE:BLACK;
            }
        }
        for(i=0;1;i++)
            if(a[0][i]==BLACK || a[1][i]==BLACK)
            {
                start=i;
                break;
            }
        for(i=n-1;1;i--)
            if(a[0][i]==BLACK || a[1][i]==BLACK)
            {
                end=i;
                break;
            }
        for(i=start;i<=end;i++)
            if((a[0][i] == WHITE) && a[1][i]==WHITE)  
            {                                           
                printf("no\n");
                goto label;
            }
        for(i=start+1;i<=end;i++)      
        {                              
            if( (a[0][i]==BLACK && a[1][i-1]==BLACK) &&    (a[0][i-1]==WHITE && a[1][i]==WHITE)    )
            {
                printf("no\n");
                goto label;
            }
            if( (a[0][i]==WHITE && a[1][i-1]==WHITE) &&    (a[0][i-1]==BLACK && a[1][i]==BLACK)    )
            {
                printf("no\n");
                goto label;
            }
        }
        for(i=start;i<=end;i++)
        {
            if((a[0][i] == a[1][i]) && a[1][i]==BLACK)
            {
                if(start==i)
                {
                    while(a[0][i]==BLACK && a[1][i]==BLACK)
                        i++;
                }
                else
				{
                int rectlength=0;
                prev=(a[0][i-1]==BLACK)?0:1;
                while((a[0][i] == a[1][i]) && a[1][i]==BLACK)
                {
                    if(i==end)
                    {
                        printf("yes\n");
                        goto label;
                    }
                    rectlength++;
                    i++;
                }
                if(rectlength%2==0 )
                {  
                    if(a[prev][i]==WHITE)
                    {
                        printf("no\n");
                        goto label;
                    }
                }
                else
                {
                    if(a[prev][i]==BLACK)
                    {
                        printf("no\n");
                        goto label;
                    }
                }
                }
            }
        }
        printf("yes\n");
    }
}
                        

                        Solution in C++ :

#include <bits/stdc++.h>

#define I_O ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

//~~~~~~~~~~~~ Sort Form Of Long~~~~~~~~~~~//
#define ll long long int
#define lls int64_t
#define ld long double
#define db double
#define ull unsigned long long int

//~~~~~~~~~~~~~~Pair~~~~~~~~~~~~~~~~~~//
#define pii pair<int, int>
#define pll pair<lls, lls>
#define pdd pair<db,db>
#define psi pair<string,int>
#define vi vector<int>
#define vl vector<lls>
#define vd vector<db>
#define vs vector<string>
#define vb vector<bool>
#define vpi vector<pii>
#define vpl vector<pll>
#define vpd vector<pdd>
#define vpsi vector<psi>
#define vvi vector<vector<int>>

//~~~~~~~~~~~~~~Vector~~~~~~~~~~~~~~~~~//
#define pb push_back
#define pf push_front
#define MP make_pair
#define in insert
#define ff first
#define ss second
#define al(v) v.begin(),v.end()
#define alr(v) v.rbegin(), v.rend()
#define srt(v) sort(al(v))
#define srtr(v) sort(al(v), greater<int>());
#define len(x) ((int)(x).size())
#define rev(v) reverse(al(v))
#define btcnt(n) __builtin_popcount(n)
#define acl(v, n) accumulate(al(v), n)
#define eb emplace_back
#define Lrt(s, c) rotate(s.begin(), s.begin() + c, s.end())
#define Rrt(s, c) rotate(s.begin(), s.begin() + s.size() - c, s.end())
#define lb(v, kk) lower_bound(al(v), kk) - v.begin()
#define ub(v, kk) upper_bound(al(v), kk) - v.begin()
#define tpu(str) transform(al(str), str.begin(), ::toupper)
#define tpl(str) transform(al(str), str.begin(), ::tolower)
#define cignr cin.ignore(numeric_limits<streamsize>::max(), '\n');
#define mxv(v) *max_element(al(v))
#define mnv(v) *min_element(al(v))

const int MOD = 1e9 + 7;
const lls INF = 2e18;
const int mxn = 2e9 + 9;
const int mxd = 2e5 + 5;
const int mxa = 2e6 + 5;

//~~~~~~~~~~~~~~~~~~Function~~~~~~~~~~~~~~~~~~~~//
lls gcd(lls a, lls b){ if(b == 0LL) return a; return gcd(b, a % b); }
lls lcm(lls a, lls b){ return (a / gcd(a, b) * b); }
lls maxll(lls x, lls y){ return x > y ? x : y; }
lls minll(lls x, lls y){ return x < y ? x : y; }

//~~~~~~~~~~~~~~~Loops and Short~~~~~~~~~~~~~~~~//

#define PI acos(-1)
#define Cn continue
#define Br break
#define off return 0
#define N '\n'
#define fopen freopen("input.txt", "r", stdin);
#define rep(i, n) for(lls i = 0; (lls)i < n; i++)
#define repn(i, a, b) for(lls i = (lls)(a); i < (lls)(b); i++)
#define repr(i, a, b) for(lls i = (lls)(a) - 1; i >= (lls)(b); i--)
#define test_case() int T; cin >> T; while(T--)

using namespace std;

// ===================================~~~~~~ SOLUTION STARTS HERE ~~~~~~=================================== //

//int a, b, c, d, e, res = 0, ans = 0, prod = 1, n, m, cnt = 0, k, l, r, s, t, x, y, f, i, j, p;

char a[2][501];
bool vis[2][502];

bool dfs(int k, int n, int j) {
   bool ans = true;
   memset(vis, 0, sizeof(vis));

   for (int i = j; i < n; i++) {
      if (a[k][i] == '#') {
         vis[k][i] = 1;
         if (k == 0) {
            if (a[k + 1][i] == '#') {
               vis[++k][i] = true;
            }
         } else {
            if (a[k - 1][i] == '#') {
               vis[--k][i] = true;
            }
         }
      } else break;
   }

   for (int i = 0; i < n; i++) {
      if (a[0][i] == '#' and !vis[0][i]) {
         ans = false; break;
      }

      if (a[1][i] == '#' and !vis[1][i]) {
         ans = false; break;
      }
   }

   return ans;
}

void Run_Case() 
{
   int n, b, f, g;
   cin >> n;
   rep (i, n) cin >> a[0][i];
   rep (i, n) cin >> a[1][i];

   int cnt = 0;

   for (int i = 0; i < n; i++) {
      if (a[0][i] == '#' or a[1][i] == '#') {
         b = i; break;
      }
   }

   f = dfs(0, n, b);
   g = dfs(1, n, b);

   if ((f + g) != 0) cout << "yes\n";
   else cout << "no\n";
}

int main()
{
   I_O
   test_case()
   {
      Run_Case();
   }

   off;
}
                    

                        Solution in Java :

import java.io.*;
import java.util.*;

class ISSNAKE {
    public static void main (String[] args)  throws IOException  {
        Scanner sc= new Scanner(System.in);
         while (sc.hasNextLine())
            {
             
        int t = Integer.parseInt( sc.nextLine() );
        testcase:
        for ( int z = 0; z < t; z++ ) {
            int n = Integer.parseInt( sc.nextLine() );
            char[][] snake = new char[2][n];
            snake[0] = sc.nextLine().toCharArray();
            snake[1] = sc.nextLine().toCharArray();
            boolean[] s1 = new boolean[n];
            boolean[] s2 = new boolean[n];
            int start = 0;
            while ( snake[0][start] == '.' && snake[1][start] == '.' )
                start++;
            s1[start] = snake[0][start] == '#';
            s2[start] = snake[1][start] == '#';
            boolean ended = false;
            for ( int i = start + 1; i < n; i++ ) {
                if ( snake[0][i] == '#' && snake[1][i] == '#' ) {
                    s1[i] = s2[i - 1];
                    s2[i] = s1[i - 1];
                }
                else if ( snake[0][i] == '#' ) {
                    s1[i] = s1[i - 1];
                }
                else if ( snake[1][i] == '#' ) {
                    s2[i] = s2[i - 1];
                }
                if ( ! s1[i] && ! s2[i] )
                    ended = true;
                if ( ended && ( snake[0][i] == '#' || snake[1][i] == '#' ) ) {
                    System.out.println( "no" );
                    continue testcase;
                }
            }
        
            System.out.println( "yes" );
          }
        }
    }
}
                    

                        Solution in Python : 
                            
def strtolist(a:str):
    b = []
    for i in range(0, n):
        b.append(a[i])
    return b

def mainthing():
    p = -1
    l = 0
    for i in range(0, n * 2):
        if p == -1:
            if l1[i] == '#':
                p = i
                l = 1
                l1[p] = 0
            elif l2[i] == '#':
                p = i
                l = 2
                l2[p] = 0
        else:
            if l == 1:
                if l2[p] == '#':
                    l = 2
                    l2[p] = 0
                elif p != n - 1 and l1[p + 1] == '#':
                    p += 1
                    l1[p] = 0
                else:
                    break
            elif l == 2:
                if l1[p] == '#':
                    l = 1
                    l1[p] = 0
                elif p != n - 1 and l2[p + 1] == '#':
                    p += 1
                    l2[p] = 0
                else:
                    break

t = int(input())

for j in range(0, t):
    n = int(input())
    a = str(input())
    l1 = strtolist(a)
    l1b = strtolist(a)
    a = str(input())
    l2 = strtolist(a)
    l2b = strtolist(a)
    
    mainthing()

    # This part checks if there are any black tiles left.
    r = False
    for i in range(0, n):
        if l1[i] == '#' or l2[i] == '#':
            r = True
            break

    l1 = l2b
    l2 = l1b
    
    mainthing()

    # This part checks if there are any black tiles left.
    r2 = False
    for i in range(0, n):
        if l1[i] == '#' or l2[i] == '#':
            r2 = True
            break
    
    if not r or not r2:
        print('yes')
    else:
        print('no')
                    

View More Similar Problems

QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element

View Solution →

Jesse and Cookies

Jesse loves cookies. He wants the sweetness of all his cookies to be greater than value K. To do this, Jesse repeatedly mixes two cookies with the least sweetness. He creates a special combined cookie with: sweetness Least sweet cookie 2nd least sweet cookie). He repeats this procedure until all the cookies in his collection have a sweetness > = K. You are given Jesse's cookies. Print t

View Solution →

Find the Running Median

The median of a set of integers is the midpoint value of the data set for which an equal number of integers are less than and greater than the value. To find the median, you must first sort your set of integers in non-decreasing order, then: If your set contains an odd number of elements, the median is the middle element of the sorted sample. In the sorted set { 1, 2, 3 } , 2 is the median.

View Solution →

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →

Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →