Hexagonal Grid
Problem Statement :
You are given a hexagonal grid consisting of two rows, each row consisting of n cells. The cells of the first row are labelled a1,a2,...,an and the cells of the second row are labelled b1,b2,...,bn. For example, for n=6: Grid Shape (Note that the b is connected with a(i+1).) Your task is to tile this grid with 2*1 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 t, the number of test cases. The first line of each test case contains a single integer n denoting the length of the grid. The second line contains a binary string of length n. The ith character describes whether cell ai is blackened. The third line contains a binary string of length n. The ith character describes whether cell bi is blackened. A 0 corresponds to an empty cell and a 1 corresponds to blackened cell. Constraints 1 <= t <= 100 1 <= n <= 10 Output Format For each test case, print YES if there exists at least one way to tile the grid, and NO otherwise.
Solution :
Solution in C :
In C++ :
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
char s[2][13];
int n;
bool can(char s[2][13],int x,int y) {
//printf("x = %d y = %d\n%s\n%s\n",x,y,s[0],s[1]);
if (y >= n) {
return can(s, x + 1, 0);
}
if (x > 1) {
return true;
}
if (s[x][y] == '1') {
return can(s, x, y + 1);
}
if ((y + 1 < n) && (s[x][y + 1] == '0')) {
s[x][y] = s[x][y + 1] = '1';
if (can(s, x, y + 1)) {
return true;
}
s[x][y] = s[x][y + 1] = '0';
}
if (x == 0) {
if (s[1][y] == '0') {
s[0][y] = s[1][y] = '1';
if (can(s, x , y + 1)) {
return true;
}
s[0][y] = s[1][y] = '0';
}
if ((y) && (s[1][y - 1] == '0')) {
s[0][y] = s[1][y - 1] = '1';
if (can(s, x, y + 1)) {
return true;
}
s[0][y] = s[1][y - 1] = '0';
}
}
return false;
}
int main() {
int z;
for (scanf("%d",&z);z;--z) {
scanf("%d%s%s",&n,s[0],s[1]);
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += s[0][i] - '1';
sum += s[1][i] - '1';
}
puts((((sum & 1) == 0) && can(s, 0, 0))?"YES":"NO");
}
return 0;
}
In Java :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class Solution {
BufferedReader reader;
StringTokenizer tokenizer;
PrintWriter out;
public void solve() throws IOException {
int T = nextInt();
for (int t = 0; t < T; t++) {
int N = nextInt();
boolean[][] map = new boolean[2][N];
String line1 = reader.readLine();
String line2 = reader.readLine();
for (int i = 0; i < N; i++) {
map[0][i] = line1.charAt(i) == '1';
map[1][i] = line2.charAt(i) == '1';
}
if (pack(map)) {
out.println("YES");
} else {
out.println("NO");
}
}
}
public boolean pack(boolean[][] map) {
boolean done = true;
for (int i = 0; i < map[0].length; i++) {
if (!map[0][i] || !map[1][i]) {
done = false;
break;
}
}
if (done) return true;
for (int i = 0; i < map[0].length; i++) {
if (!map[0][i]) {
if (!map[1][i]) {
map[0][i] = true;
map[1][i] = true;
done = done || pack(map);
map[0][i] = false;
map[1][i] = false;
}
if (i < map[0].length - 1 && !map[0][i+1]) {
map[0][i] = true;
map[0][i+1] = true;
done = done || pack(map);
map[0][i] = false;
map[0][i+1] = false;
}
break;
}
if (!map[1][i]) {
if (i < map[0].length - 1 && !map[0][i+1]) {
map[1][i] = true;
map[0][i+1] = true;
done = done || pack(map);
map[1][i] = false;
map[0][i+1] = false;
}
if (i < map[0].length - 1 && !map[1][i+1]) {
map[1][i] = true;
map[1][i+1] = true;
done = done || pack(map);
map[1][i] = false;
map[1][i+1] = false;
}
break;
}
}
return done;
}
/**
* @param args
*/
public static void main(String[] args) {
new Solution().run();
}
public void run() {
try {
reader = new BufferedReader(new InputStreamReader(System.in));
tokenizer = null;
out = new PrintWriter(System.out);
solve();
reader.close();
out.close();
} catch (Exception e) {
e.printStackTrace();
System.exit(1);
}
}
int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
String nextToken() throws IOException {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
}
In C :
#include <stdio.h>
#include <stdlib.h>
int dp1[4][2]={{0,3},{2,0},{1,2},{0,0}};
int count[4]={2,1,2,1};
int dp2[4][10],table[10];
void solve(int mask,int row);
int main(){
int T,N,i,j;
char str1[11],str2[11];
scanf("%d",&T);
while(T--){
scanf("%d%s%s",&N,str1,str2);
for(i=0;i<N;i++){
table[i]=0;
if(str1[i]-'0')
table[i]+=1;
if(str2[i]-'0')
table[i]+=2;
}
for(i=0;i<4;i++)
for(j=0;j<N;j++)
dp2[i][j]=-1;
solve(table[N-1],N-1);
if(dp2[table[N-1]][N-1])
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
void solve(int mask,int row){
int i;
if(row==0){
if(mask==0 || mask==3)
dp2[mask][row]=1;
else
dp2[mask][row]=0;
return;
}
if(row==1){
for(i=0;i<count[mask];i++){
if(dp1[mask][i]&table[row-1])
continue;
if((dp1[mask][i]|table[row-1])==3 || (dp1[mask][i]|table[row-1])==0)
{
dp2[mask][row]=1;
return;
}
}
dp2[mask][row]=0;
return;
}
for(i=0;i<count[mask];i++){
if(dp1[mask][i]&table[row-1])
continue;
if(dp2[dp1[mask][i]|table[row-1]][row-1]==-1)
solve(dp1[mask][i]|table[row-1],row-1);
if(dp2[dp1[mask][i]|table[row-1]][row-1]){
dp2[mask][row]=1;
return;
}
}
dp2[mask][row]=0;
return;
}
In Python3 :
def nextIndex(index):
return [index[0]+index[1], (index[1]+1)%2]
def onBoard(index, board):
return index[0] < len(board[0])
for t in range(int(input())):
n = int(input())
line1 = input()
line2 = input()
board = [line1,line2]
index = [0, 0]
sol = "YES"
while(index[0]<n):
if board[index[1]][index[0]] == "1":
index = nextIndex(index)
continue
index1 = nextIndex(index)
if not onBoard(index1, board):
#print("line 19 index",index1)
sol = "NO"
break
if board[index1[1]][index1[0]] == "0":
#board[index1[1]][index1[0]] = "1"
#board[index[1]][index[0]] = "1"
index = nextIndex(index1)
continue
index2 = nextIndex(index1)
if not onBoard(index2, board):
#print("line 29 index",index2)
sol = "NO"
break
if board[index2[1]][index2[0]] == "0":
#board[index2[1]][index2[0]] = "1"
#board[index[1]][index[0]] = "1"
index = nextIndex(index2)
continue
sol = "NO"
#print("line 37",index, index1, index2)
break
print(sol)
View More Similar Problems
Pair Sums
Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v
View Solution →Lazy White Falcon
White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi
View Solution →Ticket to Ride
Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o
View Solution →Heavy Light White Falcon
Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim
View Solution →Number Game on a Tree
Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy
View Solution →Heavy Light 2 White Falcon
White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr
View Solution →