flood3(B, vi, viCount, cand, candCount, C, D)

function [viUnPad, vi, viCount, cand, candCount, C, D] = flood3(B, vi, viCount, cand, candCount, C, D)
%FLOOD3  Faster replacement for subfunction flood in runSolutionVector.m.
%
% Written by Markus Buehren
% 06.11.2009

startIndex = 1; % upper left corner

% pad board
[startRow, startCol] = ind2sub(size(B), startIndex);
tmp = zeros(size(B) + 2);
tmp(2:end-1, 2:end-1) = B;
B = tmp;
tmp = []; %#ok
startIndex = sub2ind(size(B), startRow+1, startCol+1);

% flood board
[vi, viCount, cand, candCount, C, D] = ...
  floodboard(B, startIndex, vi, viCount, cand, candCount, C, D);

% unpad board
[viRow, viCol] = ind2sub(size(B), vi(1:viCount));
viUnPad = sub2ind(size(B)-2, viRow-1, viCol-1);


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [vi, viCount, cand, candCount, C, D] = ...
  floodboard(B, startIndex, vi, viCount, cand, candCount, C, D)

[NR NC] = size(B);
Bs = B(startIndex);

if isempty(C)
  % matrix C contains the following values:
  % -1: already visited
  %  0: barriers
  % other: color from B
  C = B;
  C(startIndex) = -1; % start

  % matrix D contains ones where a candidate was saved before
  D = zeros(NR, NC);

  % vi contains the indices of the cluster connected to the start point
  vi = zeros(NR*NC, 1);
  vi(1) = startIndex;
  viCount      = 1;
  viCountStart = 1;

  cand = zeros(NR*NC, 1);
  candCount = 0;

else

  if candCount == 0
    % no candidates, nothing will change
    return
  end

  % find candidates with same color as start point
  candIdxBs = (B(cand(1:candCount)) == Bs);

  % add candidates with same color to vi
  candTmp = cand(candIdxBs);
  viCountStart = viCount + 1;
  viCount = viCount + length(candTmp);
  vi(viCountStart:viCount) = candTmp;
  C(candTmp) = -1;

  % only keep candidates not used above
  candTmp = cand(~candIdxBs);
  candCount = length(candTmp);
  cand(1:candCount) = candTmp;
end


% step directions
dZ = [-1 1 -NR NR];

while 1
  if viCountStart > viCount
    % no more candidates
    return
  end

  viCountTmp = viCountStart;
  viCountStart = viCount + 1;
  for i = viCountTmp:viCount

    % get next index to check
    zi = vi(i);

    % loop over neighbors
    for s = 1:4

      % get the neighbor index Z
      Z = zi + dZ(s);

      if C(Z) == Bs
        % set element to visited
        C(Z) = -1;

        % save index in vi
        viCount = viCount + 1;
        vi(viCount) = Z;

      elseif C(Z) > 0 && D(Z) == 0
        % different color, save as candidate
        candCount = candCount + 1;
        cand(candCount) = Z;
        D(Z) = 1;
      end
    end
  end
end