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
Find Merge Point of Two Lists
This challenge is part of a tutorial track by MyCodeSchool Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share
View Solution →Inserting a Node Into a Sorted Doubly Linked List
Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function
View Solution →Reverse a doubly linked list
This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.
View Solution →Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →