流过二进制矩阵

Question

我已经提供了一个mxn随机生成的二进制矩阵,它允许流过值1但不通过值0.我需要确定是否存在从随机生成的矩阵的顶部到底部的流的路径.1s必须彼此相邻.它适用于Matlab编程.任何有关如何编码问题或算法示例的有用资源的参考将不胜感激.

我有一些代码,最初搜索顶行的前1.代码后来搜索当前1下方和附近的所有周围位置.流动只能沿对角线向下,直接向左或直接向右移动.

我的目的是看看是否有一种方法,在给定上述限制的情况下,仅在1之后从矩阵的顶部到底部遍历

Random=randi([0 1],6,6)


n =0;
while Random[0,n] ~= 1
        n=n+1;
end
CoOrds = [0,n];

for i = 0:5
    if Random[i+1, n-1] == 1
        n=n-1;
    elseif Random [i,n-1] == 1
        i = i-1;
        n = n-1;
    elseif Random [i+1,n] ==1
        n=n;
    elseif Random [i+1,n+1] ==1
        n=n+1;
    elseif Random[i,n+1] == 1
        i = i-1;
        n=n+1;
    end
end

Answer 1

您可以使用bwlabel和regionprops检查路径是否存在:

lb = bwlabel(Random, 8);  %// find 8-connected regions of the random mask
st = regionprops(lb, 'BounbdingBox');  %// find bounding boxes for all regions
b = vertcat(st.BounbdingBox);

有效路径是其边界框高度(第4个条目'BoundingBox')等于的路径size(Random,1):

validPathRegion = find( b(:,4) == size(Random,1) );