British_Informatics_Olympiad/2014-BIO-2.py at main · WebCoder49/British_Informatics_Olympiad · GitHub

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
# Loops
class Board:

    # Directions from tiles for each colour
    adjacent = {
        0: { # Colour 0 - red (solid)
            1: ((0, -1), (0, 1)), # Each item: Change in x, change in y
            2: ((-1, 0), (1, 0)),
            3: ((0, -1), (-1, 0)),
            4: ((0, -1), (1, 0)),
            5: ((0, 1), (1, 0)),
            6: ((0, 1), (-1, 0)),
        },
        1: {  # Colour 1 - green (dashed)
            2: ((0, -1), (0, 1)),  # Each item: Change in x, change in y
            1: ((-1, 0), (1, 0)),
            5: ((0, -1), (-1, 0)),
            6: ((0, -1), (1, 0)),
            3: ((0, 1), (1, 0)),
            4: ((0, 1), (-1, 0)),
        }
    }

    def __init__(self, grid):
        self.grid = grid # 2D array
        self.height = len(self.grid) # Number of rows
        self.width = len(self.grid[0])

    def loops(self, colour):

        self.visited = set() # Already checked tiles - reset for colour
        loop_tiles = 0

        for y in range(self.height):
            for x in range(self.width):
                if (x, y) in self.visited:
                    print("Ignored: ", x, y)
                    continue
                else:
                    # Check from x, y
                    loop_tiles += self.find_loop(x, y, colour)
                    print("Found: ", x, y, loop_tiles, self.visited)

        return loop_tiles

    def find_loop(self, x, y, colour):
        # Find length of loop
        tile_count = 1
        # First coords
        self.visited.add((x, y))
        first_x = x
        first_y = y

        current_tile = (x, y)

        next_tile = self.find_next_tile(x, y, colour, first_x, first_y) # First x and y is where going back to will cause a closed loop

        while(next_tile != None):
            self.visited.add(current_tile)
            previous_tile = current_tile
            current_tile = next_tile
            # Find next tile
            tile_count += 1
            # results = self.find_next_tile(next_tile[0], next_tile[1], colour, first_x, first_y, direction)
            next_tile = self.find_next_tile(current_tile[0], current_tile[1], colour, first_x, first_y, previous_tile)
            if(next_tile == "loop"):
                return tile_count

        return 0 # Loop not closed

    def find_next_tile(self, x, y, colour, first_x, first_y, prev_tile=None):
        tile_id = self.grid[y][x]
        possible_dirs = self.adjacent[colour][tile_id]

        if prev_tile == None or (prev_tile[0]-x, prev_tile[1]-y) in possible_dirs: # If links back to previous tile
            # Not possible if not linked to previous square
            for dir in possible_dirs:

                # x and y of destination
                dest_x = dir[0] + x
                dest_y = dir[1] + y

                if(prev_tile != None):
                    if((dest_x, dest_y) == prev_tile):
                        # Going to previous - not allowed
                        continue

                print("   To", dest_x, dest_y, "From", x, y, "Start", first_x, first_y)

                if(dest_x >= self.width or dest_x < 0 or dest_y >= self.height or dest_y < 0):
                    continue # Out of board
                elif(dest_x == first_x and dest_y == first_y):
                    # Closed loop
                    if((x-first_x, y-first_y) in self.adjacent[colour][self.grid[first_y][first_x]]):
                        # Line attaching first tile to last tile
                        return "loop" # closed loop
                    else:
                         print("NOT C", self.adjacent[colour][self.grid[first_y][first_x]], x, y)
                         continue
                elif ((dest_x, dest_y) in self.visited):
                    continue  # Going back on visited square
                else:
                    print("   Y")
                    return (dest_x, dest_y)

        return None # No possible next step found


def input_grid():
    size = int(input("Size: "))
    grid = []

    for i in range(size):
        # Convert string input to list of ints and append to grid
        grid.append(
            list(
                map(
                    lambda tile: int(tile), # Items to ints
                    input("Row {}: ".format(i))[0:size]) # To array
            )
        )

    return grid

board = Board(input_grid())
print(board.loops(0), board.loops(1))