# BFS (ppc 400)
###ENG[PL](#pl-version)
In the task we get a database [file](maze.db) with maze definition.We dumped the data to [txt](data.txt) to simplify usage.Each node stores a single byte of data.We guess that the point is to find the path through the maze.We used simple BFS search for that:
```pythonimport codecsimport collections
def print_matrix(matrix):    for i in range(50):        print(" ".join(matrix[i]))
def add_unvisited_node(to_process, visited, x, y, backtrace, prev):    if (x, y) not in visited:        visited.add((x, y))        backtrace[(x, y)] = prev        to_process.append((x, y))
def main():    visited = {(0, 0)}    to_process = [(0, 0)]    graph = collections.defaultdict(dict)    backtrace = {}    with codecs.open("data.txt") as input_file:        for line in input_file:            # eg. 1|0|0|gate|1            data = line[:-2].split("|")            node_id = int(data[0])            x = int(data[1])            y = int(data[2])            wall_type = data[3]            payload = data[4]            graph[x][y] = (node_id, wall_type, payload)
    while len(to_process) > 0:        xy = to_process.pop(0)        x = xy[0]        y = xy[1]        if x in graph and y in graph[x]:            node = graph[x][y]            if node[0] == 2500:                break            if node[1] == "gate":                add_unvisited_node(to_process, visited, x - 1, y, backtrace, xy)                add_unvisited_node(to_process, visited, x, y - 1, backtrace, xy)                add_unvisited_node(to_process, visited, x, y + 1, backtrace, xy)                add_unvisited_node(to_process, visited, x + 1, y, backtrace, xy)    print(backtrace)    current = (49, 49)    data = []    matrix = [['   ' for i in range(50)] for j in range(50)]    i = 0    while current != (0, 0):        x = current[0]        y = current[1]        matrix[x][y] = "%3d" % i        i += 1        data.append(graph[x][y][2])        current = backtrace[(x, y)]    data.reverse()    print_matrix(matrix)    result = "".join(data)    print(result)
main()
```
Which prints out the maze solution and the bytes picked up on the way:
```54C82F36487A9157315AADFDDED1BB83ECD98E49EADAFEB03DB563A94E0851478C408CFD6B0BB42B030F61A82E655B7FCA0E1FA68DF676758DC60FBFD1016F0EB8E7A2B5170A157497EF711E4009653BC9B20726C98B6561EFBE316AC2AB2DCBE56494F05B44ED3EB62DA4109BEEC2537266FEDE44ACB12A17CA8C8A5BA9E1A4D24ACAD900FFBD228AC187B9024BEDC941D137EA3A92F9F8506740CD8C62DBEDB9990F3E0259434D9FCF070FEC9E60C5697BABA83A4E59EB4C3F0E7AFD44B1B8D9D93933962B27237560B5F8F7D19904D790842FA596FBB52B2A3F7EE15B7F589D28A6F20F747615E7ED135E17AFE8FE073B6606F5C893D40CB78B635AA5FE4E0EE10C572D5E7AECEAF743953D05F78BBC10A9BB3D53B0011AE5F269C806E5F9E6026C954A0CDF9C797953360602B96FC06324C3160701505C24597F6F7C77D5B76CBE25CD2B706A41DA324A1B79CFC4BA8B11F800593514D27754```
As far as I remember this was the flag.
###PL version
W zadaniu dostajemy [plik](maze.db) z definicją labiryntu.Zrzuciliśmy dane do [txt](data.txt) żeby ułatwić sobie pracę.Każdy węzeł uzyskanego grafu przechowuje jeden bajt danych.Domyślaliśmy się, ze zadaniem jest znaleźć drogę w labiryncie.Użyliśmy do tego BFSa:
```pythonimport codecsimport collections
def print_matrix(matrix):    for i in range(50):        print(" ".join(matrix[i]))
def add_unvisited_node(to_process, visited, x, y, backtrace, prev):    if (x, y) not in visited:        visited.add((x, y))        backtrace[(x, y)] = prev        to_process.append((x, y))
def main():    visited = {(0, 0)}    to_process = [(0, 0)]    graph = collections.defaultdict(dict)    backtrace = {}    with codecs.open("data.txt") as input_file:        for line in input_file:            # eg. 1|0|0|gate|1            data = line[:-2].split("|")            node_id = int(data[0])            x = int(data[1])            y = int(data[2])            wall_type = data[3]            payload = data[4]            graph[x][y] = (node_id, wall_type, payload)
    while len(to_process) > 0:        xy = to_process.pop(0)        x = xy[0]        y = xy[1]        if x in graph and y in graph[x]:            node = graph[x][y]            if node[0] == 2500:                break            if node[1] == "gate":                add_unvisited_node(to_process, visited, x - 1, y, backtrace, xy)                add_unvisited_node(to_process, visited, x, y - 1, backtrace, xy)                add_unvisited_node(to_process, visited, x, y + 1, backtrace, xy)                add_unvisited_node(to_process, visited, x + 1, y, backtrace, xy)    print(backtrace)    current = (49, 49)    data = []    matrix = [['   ' for i in range(50)] for j in range(50)]    i = 0    while current != (0, 0):        x = current[0]        y = current[1]        matrix[x][y] = "%3d" % i        i += 1        data.append(graph[x][y][2])        current = backtrace[(x, y)]    data.reverse()    print_matrix(matrix)    result = "".join(data)    print(result)
main()
```
Co wypisuje na koniec rozwiązanie labiryntu oraz dane zebrane po drodze:
```54C82F36487A9157315AADFDDED1BB83ECD98E49EADAFEB03DB563A94E0851478C408CFD6B0BB42B030F61A82E655B7FCA0E1FA68DF676758DC60FBFD1016F0EB8E7A2B5170A157497EF711E4009653BC9B20726C98B6561EFBE316AC2AB2DCBE56494F05B44ED3EB62DA4109BEEC2537266FEDE44ACB12A17CA8C8A5BA9E1A4D24ACAD900FFBD228AC187B9024BEDC941D137EA3A92F9F8506740CD8C62DBEDB9990F3E0259434D9FCF070FEC9E60C5697BABA83A4E59EB4C3F0E7AFD44B1B8D9D93933962B27237560B5F8F7D19904D790842FA596FBB52B2A3F7EE15B7F589D28A6F20F747615E7ED135E17AFE8FE073B6606F5C893D40CB78B635AA5FE4E0EE10C572D5E7AECEAF743953D05F78BBC10A9BB3D53B0011AE5F269C806E5F9E6026C954A0CDF9C797953360602B96FC06324C3160701505C24597F6F7C77D5B76CBE25CD2B706A41DA324A1B79CFC4BA8B11F800593514D27754```
O ile dobrze pamiętam to była flaga.