Task is to make bfs through matrix, where u cant touch -1 or 0 values
i already have this going through matrix without touching -1 or 0 values but i can not realize, how can i make it go from left to right, because right now its going through all matrix.So the main problem is that visited list is just lis of all nodes except -1 and 0 at the end, when it must be a list in which we have path from left to right side of matrix without touching any 0 and -1.Also there`s path list, btw, for now, it means nothing, but we can store that path in it instead of visited list as i said before.
matrix from file -
0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0 1 1
matrix = np.loadtxt('input.txt', dtype=int)
def BFS():
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
if i >0:
if j>0:
matrix[i-1][j-1] = -1
if j+1<(len(matrix[i])):
matrix[i-1][j+1] = -1
matrix[i-1][j] = -1
if j>0:
matrix[i][j-1] = -1
if i+1<(len(matrix)):
matrix[i+1][j-1] = -1
if i + 1 < (len(matrix)):
matrix[i + 1][j] = -1
if i+1<(len(matrix)) and j+1<(len(matrix[i])):
matrix[i+1][j+1] = -1
if j + 1 < (len(matrix[i])):
matrix[i][j + 1] = -1
visited = []
queue = []
path = []
for i in range(len(matrix)):
if matrix[i][0] == 1:
visited.append([i, 0])
for i in range(len(matrix)):
if matrix[i][0] == 1:
queue.append([i, 0])
while queue:
m = queue.pop(0)
if m[1]+1 < len(matrix[0]) and matrix[m[0]][m[1]+1] == 1:
"""
right
"""
if [m[0], m[1]+1] not in visited:
visited.append([m[0], m[1]+1])
queue.append([m[0], m[1]+1])
path.append([[m[0], m[1]], [m[0], m[1]+1]])
"""
up
"""
elif m[0] - 1 > -1 and matrix[m[0] - 1][m[1]] == 1:
if [m[0] - 1, m[1]] not in visited:
visited.append([m[0] - 1, m[1]])
queue.append([m[0] - 1, m[1]])
path.append([[m[0], m[1]], [m[0] - 1, m[1]]])
"""
down
"""
elif m[0] + 1 < len(matrix) and matrix[m[0] + 1][m[1]] == 1:
if [m[0] + 1, m[1]] not in visited:
visited.append([m[0] + 1, m[1]])
queue.append([m[0] + 1, m[1]])
path.append([[m[0], m[1]], [m[0] + 1, m[1]]])
"""
left
"""
elif m[1] - 1 > -1 and matrix[m[0]][m[1] - 1] == 1:
if [m[0], m[1] - 1] not in visited:
visited.append([m[0], m[1] - 1])
queue.append([m[0], m[1] - 1])
path.append([[m[0], m[1]], [m[0], m[1]-1]])
print(matrix)
print(visited)
print (f"matrix: \n{matrix}")
print ("/////////////")
BFS()