grid_problem_using_bfs_java/using_python.py at master · mridulbarman027/grid_problem_using_bfs_java · 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
grid = [[0, 0, 0, 0, 0, 0, 0, 0],
        [0, -1, 0, 0, 0, -1, 0, 0],
        [0, 0, 0, 0, -1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, -1, 0, 0, -1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, -1, 0],
        [0, 0, -1, 0, 0, -1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, -1, 0, 0, 0],
        ]
row = len(grid)
col = len(grid[0])
start_position = [9, 3]

possible_paths = -1
queue = []


def explore_diagonal(x, y):
    if x+1 < row and y+1 < col:
        if grid[x+1][y+1] == 0:
            queue.append([x+1, y+1])
            visitNode([x+1, y+1])
    if x-1 >= 0 and y-1 >= 0:
        if grid[x-1][y-1] == 0:
            queue.append([x-1, y-1])
            visitNode([x-1, y-1])
    if x-1 >= 0 and y+1 < col:
        if grid[x-1][y+1] == 0:
            queue.append([x-1, y+1])
            visitNode([x-1, y+1])
    if x+1 < row and y-1 >= 0:
        if grid[x+1][y-1]:
            queue.append([x+1, y-1])
            visitNode([x+1, y-1])


def visitNode(pos):
    global possible_paths
    if grid[pos[0]][pos[1]] == 0:
        grid[pos[0]][pos[1]] = 1
        possible_paths += 1


queue.append(start_position)
visitNode(start_position)

while len(queue) > 0:
    node = queue.pop()
    explore_diagonal(node[0], node[1])

# print(grid)

print(possible_paths)