Find shortest paths

drawMap.m

function drawMap(map)
    save_hold = ishold();
    [height, width] = size(map);
    rectangle('Position', [0.5 -0.5-height width height]);
    for i = 1:height
        for j = 1:width
            here = map(i, j);
            if here == 'S'
                rectangle('Position', [j-0.3 -i-0.3 0.6 0.6],...
                          'FaceColor', [1 0 0],...
                          'Curvature', 1,...
                          'EdgeColor', 'none');
            elseif here == 'O'
                rectangle('Position', [j-0.5 -i-0.5 1 1],...
                          'FaceColor', [0 0 0],...
                          'EdgeColor', 'none');
            elseif here == 'D'
                rectangle('Position', [j-0.3 -i-0.3 0.6 0.6],...
                          'FaceColor', [0 0 1],...
                          'Curvature', 1,...
                          'EdgeColor', 'none');
            end
        end
    end
    axis([0 width+1 -height-1 0]);
    axis equal;
    if save_hold
        hold on;
    else
        hold off;
    end
end

drawPath.m

function drawPath(path)
    save_hold = ishold();
    hold on;
    plot(path(:,2),-path(:,1),'LineWidth',3);
    if save_hold
        hold on;
    else
        hold off;
    end
end

findPathsAndDraw.m

load input map;
paths = findShortestPaths(map);
if size(paths, 2) ~= 0
    num_paths = size(paths, 3);
    hold on;
    drawMap(map);
    for i = 1:num_paths
        drawPath(paths(:,:,i));
    end
else
    disp('Cannot find any path.');
end
clear;

findShortestPaths.m

function paths = findShortestPaths(map)
    if ~isValidMap(map)
        return 
    end

    sp = findPoint(map, 'S');
    dp = findPoint(map, 'D');
    if sp(1) == 0 || dp(1) == 0
        return
    end
    
    tmp = map;
    [height, width] = size(tmp);
    stack = [int64(1) sp(1) sp(2)];
    path_stack = [];
    paths = [];
    shortest = int64(height*width);
    offsets = int64([1 0; -1 0; 0 1; 0 -1]);
    
    while size(stack, 1) ~= 0
        out = stack(end, 1:3);
        lvl = out(1);
        pos = out(2:3);
        stack = stack(1:(end-1), 1:3);
        
        for i = lvl:size(path_stack,1)
           tmp(path_stack(i,1), path_stack(i,2)) ...
               = map(path_stack(i,1), path_stack(i,2)); 
        end
        path_stack(lvl,1:2) = pos;
        path_stack = path_stack(1:lvl,1:2);
        
        if tmp(pos(1), pos(2)) == 'D'
            if shortest > lvl
               shortest = lvl;
               paths = path_stack;
            elseif shortest == lvl
                    paths = cat(3, paths, path_stack);
            end
        else
            tmp(pos(1), pos(2)) = 'O';
            for i = 1:4
               new_pos = pos + offsets(i, 1:2);
               if ~isValidPoint(tmp, new_pos)
                   continue
               end
               if tmp(new_pos(1), new_pos(2)) == 'O'
                   continue
               end
               stack(end+1, 1:3) = [lvl+1, new_pos];
            end
        end
    end
end

function pos = findPoint(map, val)
    pos = [0 0];
    [height, width] = size(map);
    for i = int64(1:height)
       for j = int64(1:width)
           if map(i, j) == val
               if pos(1) ~= 0
                   pos = [0 0];
                   return
               else
                   pos = [i j];
               end
           end
       end
    end
end

function rtn = isValidPoint(map, pos)
    [height, width] = size(map);
    pos_1_w = 0 < pos(1) && pos(1) <= height;
    pos_2_w = 0 < pos(2) && pos(2) <= width;
    rtn = pos_1_w && pos_2_w;
end

function rtn = isValidMap(map)
    [height, width] = size(map);
    rtn = 1;
    for i = 1:height
       for j = 2:width
          if ~isValidElem(map(i, j))
              rtn = 0;
              return
          end
       end
    end
end

function rtn = isValidElem(elem)
    rtn = (elem == 'S' || elem == 'R' || elem == 'O' || elem == 'D');
end

test.m

map = ['RRRRRRRR';...
       'ROORRORR';...
       'RRRRORRR';...
       'RSRODRRR'];
save input map;
findPathsAndDraw