1

I'm trying to make a code that checks if there is a path in a maze from the first coordinate to the last represented by a matrix. I'm also trying to use queues. Here is the code I have so far:

from queue import Queue
maze=open(input())
matrix=maze.readlines()
matrix=[i.strip() for i in matrix]
matrix=[i.split() for i in matrix]
q=Queue()
row=0
column=0
q.put(row,column)
while not q.empty():
     row,col=q.get()
     if matrix[row][col+1]=="0" and col+1<len(matrix[0]):
         q.put(row,col+1)
         matrix[row][col+1]="2"
    if matrix[row+1][col]=="0" and row+1<len(matrix):
         q.put(row+1,col)
         matrix[row+1][col]="3"
    if matrix[row][col-1]=="0" and col-1>len(matrix[0]):
         q.put(row,col-1)
         matrix[x][x-1]="4"
    if matrix[row-1][col]=="0" and row-1<len(matrix):
         q.put(row-1,col)
         matrix[row-1][col]="5"

What can I add to the end in order to get an output of "Yes" (if there is a path) and "No" if there isn't one?

Here is a sample of the text file containing a matrix.

0 0 0 0 1 0 0 0
0 1 1 0 1 0 1 0
0 1 0 0 1 0 1 0
0 0 0 1 0 0 1 0
0 1 0 1 0 1 1 0
0 0 1 1 0 1 0 0
1 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0

I tried adding this at the end. I run my code and it says "'int' object is not iterable" 

if matrix[7][7]=="2" "3" "4" or "5":
   print "yes"
else:
   print "no"
Fat Cat
  • 63
  • 1
  • 8
  • 1
    `matrix[x[0]][x[1]+1]=="2"` makes a comparison & throws away the result. Is that supposed to be `matrix[x[0]][x[1]+1] = "2"`? – PM 2Ring Nov 07 '17 at 08:36
  • It would make it a _lot_ easier to analyze your code if you showed some typical maze data. In order to make a [mcve] you could hard-code the matrix as a list in your code. – PM 2Ring Nov 07 '17 at 08:39
  • Also, all of those `x[0]` and `x[1]` make the code hard to read. It'd be a lot easier on the eyes if you split the coordinates into a pair of variables like `row, col = q.get()`. – PM 2Ring Nov 07 '17 at 08:41
  • Noted! I edited my code, thanks! I'm not sure if I did the last suggestion right. Hopefully, it's easier to read now. – Fat Cat Nov 07 '17 at 09:00
  • `row` and `col` are plain integers, so you should have stuff like `if matrix[row][col+1]=="0"` – PM 2Ring Nov 07 '17 at 09:03
  • Oh, I see. Thank you! – Fat Cat Nov 07 '17 at 09:09
  • BTW `if matrix[7][7]=="2" "3" "4" or "5":` is equivalent to `if (matrix[7][7]=="234") or "5":`, which is not what you want. Please see the links at https://sopython.com/canon/22/why-doesn-t-if-x-a-or-b-or-c-do-what-i-expect/ – PM 2Ring Nov 07 '17 at 12:34

1 Answers1

1

There are a couple of problems with your code.

Firstly, you need to put (row, col) tuples into the queue.

Secondly, you need to change the order of the logic in your `if tests. First test that the new row or column index is inside the matrix, and then test if that location contains "0".

Once the whole matrix is mapped, you just need to test if the last location in the matrix is equal to "0".

Here's a repaired version of your code.

from queue import Queue

def show(matrix):
    for line in matrix:
        print(*line)
    print()

maze = '''\
0 0 0 0 1 0 0 0
0 1 1 0 1 0 1 0
0 1 0 0 1 0 1 0
0 0 0 1 0 0 1 0
0 1 0 1 0 1 1 0
0 0 1 1 0 1 0 0
1 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0
'''

matrix = maze.splitlines()
matrix = [i.strip() for i in matrix]
matrix = [i.split() for i in matrix]
numrows, numcols = len(matrix), len(matrix[0])

show(matrix)

# Explore the maze
q = Queue()
row = col = 0
q.put((row, col))
while not q.empty():
    row, col = q.get()

    if col+1 < numcols and matrix[row][col+1] == "0":
         q.put((row, col+1))
         matrix[row][col+1] = "2"
    if row+1 < numrows and matrix[row+1][col] == "0":
         q.put((row+1, col))
         matrix[row+1][col] = "3"
    if 0 <= col-1 and matrix[row][col-1] == "0":
         q.put((row, col-1))
         matrix[row][col-1] = "4"
    if 0 <= row-1 and matrix[row-1][col] == "0":
         q.put((row-1, col))
         matrix[row-1][col] = "5"

show(matrix)
row, col = numrows - 1, numcols - 1
current = matrix[row][col]
if current == "0":
    print('No path exists')
else:
    print('Success!')

output

0 0 0 0 1 0 0 0
0 1 1 0 1 0 1 0
0 1 0 0 1 0 1 0
0 0 0 1 0 0 1 0
0 1 0 1 0 1 1 0
0 0 1 1 0 1 0 0
1 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0

4 2 2 2 1 5 2 2
3 1 1 3 1 5 1 3
3 1 4 3 1 5 1 3
3 2 2 1 5 2 1 3
3 1 3 1 5 1 1 3
3 2 1 1 5 1 4 3
1 3 2 2 2 1 1 3
4 3 1 1 1 1 4 3

Success!

Now see if you can print the path through the maze.
Hint: start at matrix[numrows-1][numcols-1] and work backwards.

BTW, you should probably use a collections.deque for this task instead of a queue.Queue, which is normally used when your program uses threading.

PM 2Ring
  • 54,345
  • 6
  • 82
  • 182