Creating paths in a 2D array
-
Hello! Given a 2D array each node in the array may or may not be "alive" based on random values. I'm trying to find a way to connect "live" nodes in this 2D array to each other so that no isolated groups are created during the process, meaning that from any live node I can reach any other live node via the created paths. A picture to visualize the problem.[^] Can someone point me in the right direction?
-
Hello! Given a 2D array each node in the array may or may not be "alive" based on random values. I'm trying to find a way to connect "live" nodes in this 2D array to each other so that no isolated groups are created during the process, meaning that from any live node I can reach any other live node via the created paths. A picture to visualize the problem.[^] Can someone point me in the right direction?
Hi, You are not really giving enough information about the problem you are trying to solve. The screenshot implies that there are impassable nodes.
Member 15615426 wrote:
Can someone point me in the right direction?
If you are trying to find the Eulerian path check out Fleury's algorithm as that might be what you're are looking for.
-
Hello! Given a 2D array each node in the array may or may not be "alive" based on random values. I'm trying to find a way to connect "live" nodes in this 2D array to each other so that no isolated groups are created during the process, meaning that from any live node I can reach any other live node via the created paths. A picture to visualize the problem.[^] Can someone point me in the right direction?
You can use BFS or DFS to determine whether or not there is a path. The graph is not required to execute the bfs, but the matrix itself will be utilized as one. Begin the traversal from the upper right corner, and if there is a method to the lower right corner, there is a path.