CODEWITHSUNDEEP
pythonpython-3.xlistdata-structures
sensualbumfuzzle
sensualbumfuzzle

Reputation: 95

how to check path connection in matrix?

I have defined a matrix which has all of its elements initialized to 0 and the program randomly converts any element to 1 , and keeps doing it until there is path which connects the top row to the bottom row(up/down/left/right , no diagonal movement). For example:

[0,0,0]
[0,0,0]
[0,0,0]

1st iteration:

[0,0,0]
[0,1,0]
[0,0,0]

many more iterations later:

[1,1,0]
[0,1,1]
[0,0,1]

Now it is visible that there is a path from the top to bottom . I have tried using various approaches but all don't work properly so instead of asking you to correct my algorithm , I'd like to know how you would come about this problem (Code isn't necessary , the logic is fine.)

Upvotes: 1

Views: 341

Answers (2)

Elliot Way
Elliot Way

Reputation: 243

The grid is an basically an undirected graph. If the problem is to check if there is a path from the top to the bottom, it makes sense to use a grid traversal algorithm. Breadth-first search makes sense because we can initialize the queue to every 1 on the top row. If the traversal visits a cell on the bottom, then the grid contains a path; if it never does, then there isn't one.

But that's not quite the problem! Searching through the whole grid takes time. Every time you flip a cell to 1, you're only adding a single node to the graph, and we can detect when the grid has a path from top to bottom more efficiently than by using breadth-first search from scratch every time.

One strategy to do this would be to maintain several separate lists of connected cells. Every time you add a new 1, you add it to the list any adjacent 1s are in. If there are none, create a new list. If there are more than one adjacent 1s that are in different lists, combine those lists. There is a path from top to bottom when a list contains a 1 on both the top and bottom rows.

There's still some optimization left to figure out; ideally you can check which list an adjacent 1 is in faster than searching through every list. I think it's possible to make the check for a path O(1), but I haven't checked it carefully to make sure.

I suggest you first try the bread-first search version, then try the multiple updating list version, then, if you're not bored of the problem, try to optimize it.

Upvotes: 1

Harut Hunanyan
Harut Hunanyan

Reputation: 178

I have an idea of solving this, using sort of CheckPath() method, with recursive approach.

It will work like this: Starting from the top, it searches for a 1 in a row (I mean simple iterating), then if it finds, it calls itself, checking if there's a 1 either at the bottom (in the next row), or on the right. If there is, repeat the steps,starting from the latest 1 it found, until it gets to the last row.

Note, that you can miss checking the left, as if you started your iteration process from left to the right, you have already checked all possible 'left-sides'.

This answer is sort of an idea, and I haven't implemented it, so I can't help with a code, yet.

Upvotes: 0

Related Questions