Alternating up and down in my script to find path through 'maze'

조회 수: 1 (최근 30일)
The Legend
The Legend 2020년 1월 9일
댓글: The Legend 2020년 1월 10일
Scrip folder is attached! (.zip)
The point of this script is to find if a path exists of 1's between the bottom row and top row. A path consisting of straight lines only, no diagonals.
Concept of the script
The maze:
0 1 1 0 1 1 0 (path is made bold)
0 1 0 0 0 0 0
0 1 1 1 1 0 0
0 0 0 0 1 0 0
1 1 1 0 1 1 0
1 0 1 1 1 0 0
1 1 0 0 0 0 0
Initiating step:
Search the bottom row for values equal to 1, then change these into 2's.
Looping step:
Now scan the row above for values equal to 1, which are attached to values of 2. (Like a virus)
Now scan left and right of these new 2's for other 1's that are attached to these, and turn these into 2's aswell.
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 1 1 1 1 0 0
0 0 0 0 1 0 0
2 2 2 0 1 1 0
2 0 1 1 1 0 0
2 2 0 0 0 0 0
As can be seen above we now encounter a point where there's only 0s above and so the script should go down.
I am unable to find an efficient way for alternating up and down within my script, so that it keeps searching for new 1's connected to 2's.
I have been struggling with this specific problem for over 5 hours already and am getting really upset.
Any help is greatly aprecciated!

채택된 답변

Meg Noah
Meg Noah 2020년 1월 10일
Here's a solution to finding paths that connect the top of the grid to the bottom using 4-neighbors
clc
close all
clear all
maze = [ ...
0 1 1 0 1 1 0; ...
0 1 0 0 0 0 0; ...
0 1 1 1 1 0 0; ...
0 0 0 0 1 0 0; ...
1 1 1 0 1 1 0; ...
1 0 1 1 1 0 0; ...
1 1 0 0 0 0 0];
amazing = bwlabel(maze,4);
[ny,nx] = size(amazing);
stats = regionprops(amazing,'PixelList');
for iblob = 1:length(stats)
% check if the path has a pixel in row 1 and a pixel in the last row
if ((min(stats(iblob).PixelList(:,2)) == 1) && ...
(max(stats(iblob).PixelList(:,2)) == ny))
disp(['Success: path ' num2str(iblob) ' connects top and bottom.']);
amazing(amazing == iblob) = 10*iblob;
else
% path fails
amazing(amazing == iblob) = 0;
end
end
npaths = sum(unique(amazing))-1;
disp(['[Found ' num2str(npaths) ' paths in the maze.']);
amazing
The solution prints out
Success: path 1 connects top and bottom.
[Found 9 paths in the maze.
amazing =
0 10 10 0 0 0 0
0 10 0 0 0 0 0
0 10 10 10 10 0 0
0 0 0 0 10 0 0
10 10 10 0 10 10 0
10 0 10 10 10 0 0
10 10 0 0 0 0 0

추가 답변 (0개)

카테고리

Help CenterFile Exchange에서 Labyrinth problems에 대해 자세히 알아보기

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by