CODEWITHSUNDEEP
pythoncalgorithmmatrix
Nick
Nick

Reputation: 10499

How to find cell neighbors in a matrix

I have a matrix (5x5) of boolean values:

matrix = [[False for x in range(5)] for x in range(5)]
matrix[0][3] = True
matrix[2][2] = True

F F F T F
F X F F F
F F T F F
F F F F F
F F F F F

Given an index, I need to find the closer cell which value is True. Where closer means: the cell that can be reached with the lower number of moves, that is the sum between the rows difference and the columns difference must be minimal. So, for example:

row, column = find(row=1, column=1)
# row = 2
# column = 2

What kind of algorithm can I use?

Upvotes: 0

Views: 603

Answers (2)

Irshad Bhat
Irshad Bhat

Reputation: 8709

Try the code given below:

matrix = [[False for x in range(5)] for x in range(5)]
matrix[0][3] = True
matrix[2][2] = True

stack=[]


def find(rc):  # argument rc is a (row,col) tuple like (1,1). Don't pass it a 1,1 
    global stack
    r=rc[0] 
    c=rc[1]
    if (c+1 < 5) and (matrix[r][c+1]==True):
        print r,c+1
        stack=[]
        return
    if (c-1 > -1) and (matrix[r][c-1]==True):
        print r,c-1
        stack=[]
        return
    if (r+1 < 5) and (matrix[r+1][c]==True):
        print r+1,c
        stack=[]
        return
    if (r-1 > -1) and (matrix[r-1][c]==True):
        print r-1,c
        stack=[]
        return
    if r+1 < 5: stack.append((r+1,c))
    if r-1 > -1: stack.append((r-1,c))
    if c+1 < 5: stack.append((r,c+1))
    if c-1 > -1: stack.append((r,c-1))
    find(stack.pop(0))

>>> find((1,1))
2 2
>>> find((0,0))
0 3
>>> find((4,0))
2 2
>>> find((4,4))
2 2
>>> find((0,4)) 
0 3

Upvotes: 0

yurib
yurib

Reputation: 8147

BFS - search the immediate neighbors, then the immediate neighbors of each of your immediate neighbors and so on... at each such step you'll be searching cells that are one step further than those of the previous step. also, keep track of which cells were already checked so you don't repeat them

Upvotes: 2

Related Questions