forked from algorhythms/HackerRankAlgorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Hexagonal Grid.py
66 lines (57 loc) · 2.06 KB
/
Hexagonal Grid.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# -*- coding: utf-8 -*-
"""
You are given a hexagonal grid of size 2xN. Your task is to construct the grid with 2x1 dominoes. The dominoes can be
arranged in any of the three orientations shown below. To add to the woes, certain cells of the hexogonal grid are
blackened i.e., no domino can occupy that cell. Can you construct such a hexagonal grid?
"""
__author__ = 'Danyang'
class Solution(object):
def __init__(self):
self.delta = [(0, 1), (1, 0), (1, -1)] # dominoes delta, coordinate: x downward, y rightward,
# need consistent directions
def solve(self, cipher):
"""
recursive solution, brute force, starting from top left
:param cipher: the cipher
"""
ret = self.rec(cipher)
if ret:
return "YES"
else:
return "NO"
def rec(self, grid):
changed = False
m = len(grid)
n = len(grid[0])
for i in xrange(m):
for j in xrange(n):
if not changed: # control the start from top, left
if grid[i][j] == 0:
changed = True
grid[i][j] = 1
for d in self.delta:
i2 = i + d[0]
j2 = j + d[1]
if 0 <= i2 < m and 0 <= j2 < n and grid[i2][j2] == 0:
grid[i2][j2] = 1
if self.rec(grid):
return True
grid[i2][j2] = 0
grid[i][j] = 0
if not changed:
return True
if __name__ == "__main__":
import sys
f = open("1.in", "r")
# f = sys.stdin
solution = Solution()
testcases = int(f.readline().strip())
for t in xrange(testcases):
# construct cipher
int(f.readline().strip())
cipher = []
for _ in xrange(2):
cipher.append(map(int, list(f.readline().strip())))
# solve
s = "%s\n" % (solution.solve(cipher))
print s,