Cerinta completa

You are given a hexagonal grid consisting of two rows, each row consisting of cells. The cells of the first row are labelled and the cells of the second row are labelled .

For example, for :

Grid Shape

(Note that the is connected with .)

Your task is to tile this grid with tiles that look like the following:

Orientations

As you can see above, there are three possible orientations in which a tile can be placed.

Your goal is to tile the whole grid such that every cell is covered by a tile, and no two tiles occupy the same cell. To add to the woes, certain cells of the hexagonal grid are blackened. No tile must occupy a blackened cell.

Is it possible to tile the grid?

Here’s an example. Suppose we want to tile this grid:

Example Blank

Then we can do the tiling as follows:

Example Tiled

Input Format

The first line contains a single integer , the number of test cases.

The first line of each test case contains a single integer denoting the length of the grid.
The second line contains a binary string of length . The character describes whether cell is blackened.
The third line contains a binary string of length . The character describes whether cell is blackened.
A 0 corresponds to an empty cell and a 1 corresponds to blackened cell.

Constraints

Output Format

For each test case, print YES if there exists at least one way to tile the grid, and NO otherwise.

Sample Input 0

6
6
010000
000010
2
00
00
2
00
10
2
00
01
2
00
11
2
10
00

Sample Output 0

YES
YES
NO
NO
YES
NO

Explanation 0

The first test case in the sample input describes the example given in the problem statement above.
For the second test case, there are two ways to fill it: either place two diagonal tiles side-by-side or place two horizontal tiles.

Limbajul de programare folosit: cpp14

Cod:

/*******************************************************
* Copyright (C) 2015 Haotian Wu
*
* This file is the solution to the question:
* https://www.hackerrank.com/challenges/hexagonal-grid
*
* Redistribution and use in source and binary forms are permitted.
*******************************************************/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <map>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Dynamic Programming. We can use dp[i][j] = k to denote the case that ...
// first row has i cells, and second line has j cells, is feasible (k=1) or not (k=0).
// When we encounter a black cell, we ignore it. For example, if row2[j] is black, dp[i][j] = dp[i][j-1].
int dp[11][11];
char row1[12],row2[12];
int getdp(int i, int j)
{
    if (i == 0 && j == 0)
        return 1;
    if ((i == 0 && j < 0) || (j == 0 && i < 0))
        return 0;
    if (dp[i][j] != -1)
        return dp[i][j];
    if (i > 0 && row1[i] == '1')
        return getdp(i-1,j);
    if (j > 0 && row2[j] == '1')
        return getdp(i,j-1);
    if (i < j)
    {
        if (j > 1 && row2[j-1] == '0') 
            dp[i][j] = getdp(i, j-2);
        else
            dp[i][j] = 0;
    }
    else if (i == j || i == j+1)
    {
        dp[i][j] = getdp(i-1, j-1);
    }
    else
    {
        if (i > 1 && row1[i-1] == '0')
            dp[i][j] = getdp(i-2, j);
        else
            dp[i][j] = 0;
    }
    return dp[i][j];
}
int main() {
    int tt;
    scanf("%d",&tt);
    while (tt--)
    {
        int n;
        memset(dp,-1,sizeof(dp));
        scanf("%d %s %s",&n,row1+1,row2+1);
        printf("%s\n", getdp(n, n)? "YES":"NO");
    }
}

Scor obtinut: 1.0

Submission ID: 464612792

Link challenge: https://www.hackerrank.com/challenges/hexagonal-grid/problem

Hexagonal Grid