function W = solver(B)
W = mysolver(B,1);
S = mygrade(B,W);

W2 = mysolver(B,2);
S2 = mygrade(B,W2);

if S2 < S
    W = W2;
end

% W3 = mysolver(B,3);
% S3 = mygrade(B,W3);
% 
% if S3 < S
%     W = W3;
% end

% S3 = S;
% fprintf('scores = %4d, %4d, %4d, improvement = %4d, %4d\n', S, S2, S3, S2 - S, S3 - S);


end

% function score = mygrade(B,W)
%     score = myconcom(B,W);
% end

function score = mygrade(B,W)
% function [score W Wlab C B] = myconcom(B,W)
% CONCOM Finds connected components and scores the solution
%      Inputs:
%         B - Board, a matrix with component ID's, 0's means no component.
%         W - Wiring, a matrix (nx4) matrix with wires, invalid wires are
%             ignored but charged into the score. 
%
% The MATLAB Contest Team 
% April, 2008 

[ro,co] = size(B);
dW = abs(W(:,[1 2])-W(:,[3 4]));
% Extract bridges from W
Bridges = W(~any(dW,2),[1 2]);
% Calculate the wiring cost: (Bridge cost is 25, but 1 is alredy counted in W
wiringCost = size(W,1) + 24 * size(Bridges,1); 
% Keep only valid wires in W
W = W(all(W(:,[1 3])>0 & W(:,[1 3])<=ro & W(:,[2 4])>0 & W(:,[2 4])<=co,2) & (sum(dW,2)==1),:);
% Change wiring coordinates to linear indexing:
V = sort([sub2ind([ro,co],W(:,1),W(:,2)) sub2ind([ro,co],W(:,3),W(:,4))],2);
BridgeIdx = sub2ind([ro,co],Bridges(:,1),Bridges(:,2));
% Create a graph (E (edges)):
E = zeros(size(V));
[node2idx,dummy,E(:)]= unique(V);
nN = numel(node2idx);
idx2node(node2idx) = 1:nN;
% Build an adjacency list for edges:
A = zeros(nN,4);  % [v ^ > <]
for i = 1:nN
    [j,k] = find(node2idx(i)==V);
    A(i,2*(diff(V(j,:),[],2)>1)+k) = sum(E(j,:),2)-i;
end
% Keep bridges that exist over wires and are not over components
BridgeIdx = intersect(BridgeIdx,V(:));
BridgeIdx = BridgeIdx(B(BridgeIdx)==0);
% Remove bridges that do not separate vertical and horizontal wires
BridgeIdx = BridgeIdx(any(A(idx2node(BridgeIdx),[1 2]),2) & any(A(idx2node(BridgeIdx),[3 4]),2));
% Add extra nodes where Bridges exist:
A = [A;zeros(numel(BridgeIdx),4)];
node2idx = [node2idx; BridgeIdx];
j = nN;
for i = idx2node(BridgeIdx)
    j = j+1;
    A(j,:) = A(i,:);
    if A(i,3) 
        A(A(i,3),4)=j; 
    end
    if A(i,4) 
        A(A(i,4),3)=j; 
    end
    A(i,[3 4]) = 0;
    A(j,[1 2]) = 0;
end
% Label nodes
labels = zeros(size(A,1),1);
tv = find(~labels,1);
cc = 1;
while ~isempty(tv)
    while ~isempty(tv)
        labels(tv) = cc;
        tv = nonzeros(A(tv,:));
        tv = tv(labels(tv) == 0);
    end
    cc = cc+1;
    tv = find(~labels,1);
end

% Copy labels to a board
C = zeros(ro,co);
C(node2idx) = labels;
H = ~C & B>0;
C(H) = cc+(0:nnz(H)-1);    
C(BridgeIdx)=-1;

% Label wires
Wlab = zeros(size(V,1),1);
for i=1:size(A,1)
    for j = 1:4
        if A(i,j)
            Wlab(V(:,1)==node2idx(i) & V(:,2)==node2idx(A(i,j))) = labels(i);
        end
    end
end

% find short-circuited components and remove them:
P = unique(nonzeros(B));
for i = 1:cc-1
    p = unique(nonzeros(B(C==i))); 
    if numel(p)>1
        P = setdiff(P,p);
    end
end
% consider the largest island for every non-short-circuited component and
% remove it from the board:
for i = 1:numel(P)
    [sz,ch] = max(sparse(C(B==P(i)),1,1));
    if sz>1
       B(C==ch)=0;
    end
end

score = sum(nonzeros(B)) + wiringCost;
    
end

function W = mysolver(B,rz)

%%
function path = simplepath(row,col,label)
% fprintf('simple path, r=%d c=%d, r=%d c=%d\n', row(1), col(1), row(2), col(2));
deltar = row(1) - row(2);
deltac = col(1) - col(2);
if abs(deltar)+abs(deltac) > 11
    path = zeros(0,4);
    return
end
dr = sign(deltar);
dc = sign(deltac);


% adjacent
if (abs(deltar) == 1 && dc == 0) || (dr == 0 && abs(deltac) == 1)
    path = [row(1) col(1) row(2) col(2)];
    return
end

% try step to next row
if dr ~= 0
    r = row(2) + dr;
    c = col(2);
    if B(r,c) == label
        path = [r c row(2) col(2)];
%         fprintf('found a wire %d\n', label);
        return
    end
    if B(r,c) == 0
        path = simplepath([row(1) r], [col(1) c], label);
        if size(path,1) > 0
            path = [path; r c row(2) col(2)];
            return
        end
    end
end

% try step to next col
if dc ~= 0
    r = row(2);
    c = col(2) + dc;
    if B(r,c) == label
        path = [r c row(2) col(2)];
%         fprintf('found a wire %d\n', label);
        return
    end
    if B(r,c) == 0
        path = simplepath([row(1) r], [col(1) c], label);
        if size(path,1) > 0
            path = [path; r c row(2) col(2)];
            return
        end
    end
end

path = zeros(0,4);
end


%% - solver - - - -
% size(B)
% fprintf('\nsolver\n');

Borig = B;

W = zeros(0,4);

% make a sorted list of all pins
pin = sort(B(B>0),'descend');
npins = size(pin,1);
if npins < 1
    return
end

% pin, count, benefit
pincount = zeros(npins,3);
pincount(1,1) = pin(1);
k = 1;
count = 1;
for i = 2:npins
    if pin(i) == pincount(k,1)
        count = count + 1;
    else
        pincount(k,2) = count;
        k = k + 1;
        count = 1;
        pincount(k,1) = pin(i);
    end
end
pincount(k,2) = count;
pincount = pincount(1:k,:);
% calculate the benefit of a path
for i = 1:k
    if pincount(i,2) >= 2
        p = pincount(i,1);
        [row col] = find(B == p);
        d = 0;
        for j = 2:size(row,1);
            d = d + abs(row(j)-row(j-1)) + abs(col(j)-col(j-1));
        end
        pincount(i,3) = pincount(i,2)*p - d;
    end
end
if rz == 1
    [s ix] = sort(pincount(:,3),'descend');
elseif rz == 2
    [s ix] = sort(pincount(:,1),'descend');
else
    ix = randperm(size(pincount,1));
end

pincount = pincount(ix,:);

% fprintf('pincount ...\n');
% pincount
% pause

for i = 1:k
    if pincount(i,2) >= 2
        p = pincount(i,1);
        [row col] = find(B == p);
        N = size(row,1);
        % find all pairwise distances
        Npairs = N*(N-1)/2;
        dist = zeros(Npairs,3);
        x = 0;
        for a = 1:N
            for b = (a+1):N
                x = x + 1;
                dist(x,1) = a;
                dist(x,2) = b;
                dist(x,3) = abs(row(a)-row(b)) + abs(col(a)-col(b));
            end
        end
        % sort by distance
        [d ix] = sort(dist(:,3));
        dist = dist(ix,:);
        
        % try to connect the closest pair possible
        npins = 0;
        for x = 1:Npairs
            a = dist(x,1);
            b = dist(x,2);
%             path = simplepath([row(a); row(b)], [col(a); col(b)], -p);
            path = complexpath(B,[row(a); row(b)], [col(a); col(b)], -p, 2*p);
            if size(path,1) > 0
%                 fprintf('p = %d, connect a=%d, b=%d, dist = %d\n', p, a, b, dist(x,3));
%                 fprintf('\nFound path, p = %d, r=%d c=%d, r=%d, c=%d\n', p, row(a), col(a), row(b), col(b));
                W = [W; path];
                B = addwirepath(B,path,-p);
                pinlist = [row(a) col(a); row(b) col(b)];
                npins = 2;
                edit = [1:(a-1) (a+1):(b-1) (b+1):N];
                row = [row(a); row(b); row(edit)];
                col = [col(a); col(b); col(edit)];
                break
            else
%                 fprintf('p = %d, cannot connect a=%d, b=%d, dist = %d\n', p, a, b, dist(x,3));
            end
        end
        
        if npins < 2
            continue
        end
        
        for j = 3:N
            % find all pins and wires
            [row2 col2] = find(B == -p);
            Npinwires = size(row2,1);
%             fprintf('npins = %d, nwires = %d\n', npins, Npinwires - npins);
            
            % find all pairwise distances
            % a = already connected (pin or wire), b = not yet connected
            Npairs =  Npinwires * (N - npins);
            dist = zeros(Npairs,3);
            x = 0;
            for a = 1:Npinwires
                for b = (npins+1):N
                    x = x + 1;
                    dist(x,1) = a;
                    dist(x,2) = b;
                    dist(x,3) = abs(row2(a)-row(b)) + abs(col2(a)-col(b));
                end
            end
            % sort by distance
            [d ix] = sort(dist(:,3));
            dist = dist(ix,:);
            
            % try to connect closest pair possible
            connected = false;
            for x = 1:Npairs
                a = dist(x,1);
                b = dist(x,2);
%                 path = simplepath([row2(a); row(b)], [col2(a); col(b)], -p);
                path = complexpath(B,[row2(a); row(b)], [col2(a); col(b)], -p, p);
                if size(path,1) > 0
%                     fprintf('\nfound path, p = %d, r=%d c=%d, r=%d, c=%d\n', p, row2(a), col2(a), row(b), col(b));
%                     if size(path,1) > p
% %                         fprintf('warning: pathlen = %d, pin = %d\n', size(path,1), p);
%                         break
%                     end
                    W = [W; path];
                    B = addwirepath(B,path,-p);
                    pinlist = [pinlist; row(b) col(b)];
                    npins = npins + 1;
                    connected = true;
                    if b ~= j
                        t = row(j); row(j) = row(b); row(b) = t;
                        t = col(j); col(j) = col(b); col(b) = t;
                    end
                    break
                end
            end
          
            if ~connected
                break
            end
        end
        
    end
end

% fprintf('soln:\n');
% W
% pause

%% -- phase 2 --
% fprintf('-- phase 2 --\n');

[BH BV] = buildbridges(Borig,B,W);

% make a sorted list of all pins
pin = sort(B(B>0),'descend');
npins = size(pin,1);
if npins < 1
    return
end

% pin, count, benefit
pincount = zeros(npins,3);
pincount(1,1) = pin(1);
k = 1;
count = 1;
for i = 2:npins
    if pin(i) == pincount(k,1)
        count = count + 1;
    else
        pincount(k,2) = count;
        k = k + 1;
        count = 1;
        pincount(k,1) = pin(i);
    end
end
pincount(k,2) = count;
pincount = pincount(1:k,:);
% calculate the benefit of a path
for i = 1:k
    if pincount(i,2) >= 2
        p = pincount(i,1);
        [row col] = find(B == p);
        d = 0;
        for j = 2:size(row,1);
            d = d + abs(row(j)-row(j-1)) + abs(col(j)-col(j-1));
        end
        pincount(i,3) = pincount(i,2)*p - d;
    end
end
if rz == 1
    [s ix] = sort(pincount(:,3),'descend');
elseif rz == 2
    [s ix] = sort(pincount(:,1),'descend');
else
    ix = randperm(size(pincount,1));
end
pincount = pincount(ix,:);

% fprintf('pincount ...\n');
% pincount
% pause

for i = 1:k
    p = pincount(i,1);
    
    [row2 col2] = find(B == -p);
    Npinwires = size(row2,1);
    
    if Npinwires == 0
%         fprintf('p = %d, no previous pinwires\n', p);
    
        if pincount(i,2) >= 2
            p = pincount(i,1);
            [row col] = find(B == p);
            N = size(row,1);
            % find all pairwise distances
            Npairs = N*(N-1)/2;
            dist = zeros(Npairs,3);
            x = 0;
            for a = 1:N
                for b = (a+1):N
                    x = x + 1;
                    dist(x,1) = a;
                    dist(x,2) = b;
                    dist(x,3) = abs(row(a)-row(b)) + abs(col(a)-col(b));
                end
            end
            % sort by distance
            [d ix] = sort(dist(:,3));
            dist = dist(ix,:);

            % try to connect the closest pair possible
            npins = 0;
            connected = false;
            for x = 1:Npairs
                a = dist(x,1);
                b = dist(x,2);
                path = bridgepath(B,BH,BV,[row(a); row(b)], [col(a); col(b)], -p, 2*p);
                if size(path,1) > 0
%                     fprintf('\nBRIDGE path, p = %d, r=%d c=%d, r=%d, c=%d\n', p, row(a), col(a), row(b), col(b));
                    W = [W; path];
                    [B BH BV] = addbridgewirepath(B,BH,BV,path,-p);
                    connected = true;
                    break
                end
            end
            if ~connected
                continue
            end
        end
    end
    
    [row col] = find(B == p);
    Npins = size(row,1);
    
%     [row2 col2] = find(B == -p);
%     Npinwires = size(row2,1);
    
      if Npins > 0
%     if Npinwires > 0 && Npins > 0
%         fprintf('p = %d, Npinwires = %d, Npins = %d\n', p, Npinwires, Npins);
        for j = 1:Npins
            [row2 col2] = find(B == -p);
            Npinwires = size(row2,1);
    
            % find all pairwise distances
            % a = already connected (pin or wire), b = not yet connected
            Npairs =  Npinwires * (Npins-j+1);
            dist = zeros(Npairs,3);
            x = 0;
            for a = 1:Npinwires
                for b = j:Npins
                    x = x + 1;
                    dist(x,1) = a;
                    dist(x,2) = b;
                    dist(x,3) = abs(row2(a)-row(b)) + abs(col2(a)-col(b));
                end
            end
            % sort by distance
            [d ix] = sort(dist(:,3));
            dist = dist(ix,:);
            
            % try to connect closest pair possible
            connected = false;
            for x = 1:Npairs
                a = dist(x,1);
                b = dist(x,2);
                path = bridgepath(B,BH,BV,[row2(a); row(b)], [col2(a); col(b)], -p, p);
                if size(path,1) > 0
%                      fprintf('\nEXTRA BRIDGE path, p = %d, r=%d c=%d, r=%d, c=%d\n', p, row2(a), col2(a), row(b), col(b));
                    W = [W; path];
                    [B BH BV] = addbridgewirepath(B,BH,BV,path,-p);
                    connected = true;
                    if b ~= j
                        t = row(j); row(j) = row(b); row(b) = t;
                        t = col(j); col(j) = col(b); col(b) = t;
                    end
                    break
                end
            end
          
            if ~connected
                break
            end
        end
    end
    
end

end

%%
function [BH BV] = buildbridges(Borig,B,path)
[NR NC] = size(B);
BH = Borig == 0;
BV = Borig == 0;
BH(:,1) = false;
BH(:,NC) = false;
BV(1,:) = false;
BV(NR,:) = false;
Npath = size(path,1);
for i = 1:Npath
    if path(i,1) == path(i,3) % horizontal
        BH(path(i,1),path(i,2)) = false;
        BH(path(i,3),path(i,4)) = false;
    end
    if path(i,2) == path(i,4) % vertical
        BV(path(i,1),path(i,2)) = false;
        BV(path(i,3),path(i,4)) = false;
    end
end
% figure(100);
% imagesc(BH & (B < 0)), colormap(gray), axis image, title('Horizontal');
% figure(101);
% imagesc(BV & (B < 0)), colormap(gray), axis image, title('Vertical');
end


%%
function [B BH BV] = addbridgewirepath(B,BH,BV,path,label)
N = size(path,1);
for i = 1:N
    if path(i,1) == path(i,3) % horizontal
        BH(path(i,1),path(i,2)) = false;
        BH(path(i,3),path(i,4)) = false;
    end
    if path(i,2) == path(i,4) % vertical
        BV(path(i,1),path(i,2)) = false;
        BV(path(i,3),path(i,4)) = false;
    end
   
    if path(i,1) == path(i,3) && path(i,2) == path(i,4)
        B(path(i,1),path(i,2)) = -9999;
    else
        B(path(i,1),path(i,2)) = label;
        B(path(i,3),path(i,4)) = label;
    end
end
end

%%
function B = addwirepath(B,path,label)
N = size(path,1);
for i = 1:N
%     if B(path(i,1),path(i,2)) == 0
%         B(path(i,1),path(i,2)) = label;
%     end
    B(path(i,1),path(i,2)) = label;
%     if B(path(i,3),path(i,4)) == 0
%         B(path(i,3),path(i,4)) = label;
%     end
    B(path(i,3),path(i,4)) = label;
end
end

%%
function path = complexpath(B,row,col,label,maxpathlen)

    function path = traceback(dr,dc,t)
        PR(dr,dc) = r(i);
        PC(dr,dc) = c(i);
        path = zeros(t,4);
        for j = 1:t
            path(j,1:2) = [dr dc];
            pr = PR(dr,dc);
            pc = PC(dr,dc);
            path(j,3:4) = [pr pc];
            dr = pr;
            dc = pc;
        end
        if dr ~= row(2) || dc ~= col(2)
            fprintf('traceback fails\n');
            path
            fprintf('rowcol\n');
            [row col]
            fprintf('r c\n');
            [dr dc]
        end
    end

% - complexpath -
[NR NC] = size(B);
PR = zeros(NR,NC);
PC = zeros(NR,NC);
C = -ones(NR,NC);
C(row(2),col(2)) = 0; % source

rnext = zeros(NR*NC,1);
cnext = zeros(NR*NC,1);
count = 1;
rnext(1) = row(2);
cnext(1) = col(2);
%
% cutoff
%
for step = 0:min(9,maxpathlen)
%     [r c] = find(C == step);

    if count < 1, break, end
    N = count;
    r = rnext(1:N);
    c = cnext(1:N);
    count = 0;
    for i = 1:N
        dc = c(i);
        if r(i) > 1
            dr = r(i)-1;
            if (B(dr,dc) == label) || (dr == row(1) && dc == col(1))
%             if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if B(dr,dc) == 0 && C(dr,dc) == -1
                C(dr,dc) = step+1;
                PR(dr,dc) = r(i);
                PC(dr,dc) = c(i);
                count = count + 1; rnext(count) = dr; cnext(count) = dc;
            end
        end
        if r(i) < NR
            dr = r(i) + 1;
            if (B(dr,dc) == label) || (dr == row(1) && dc == col(1)) 
%             if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if B(dr,dc) == 0 && C(dr,dc) == -1
                C(dr,dc) = step+1;
                PR(dr,dc) = r(i);
                PC(dr,dc) = c(i);
                count = count + 1; rnext(count) = dr; cnext(count) = dc;
            end
        end
            
        dr = r(i);
        if c(i) > 1
            dc = c(i) - 1;
            if B(dr,dc) == label || (dr == row(1) && dc == col(1))
%             if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if B(dr,dc) == 0 && C(dr,dc) == -1
                C(dr,dc) = step+1;
                PR(dr,dc) = r(i);
                PC(dr,dc) = c(i);
                count = count + 1; rnext(count) = dr; cnext(count) = dc;
            end
        end
        if c(i) < NC
            dc = c(i) + 1;
            if B(dr,dc) == label || (dr == row(1) && dc == col(1))
%             if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if B(dr,dc) == 0 && C(dr,dc) == -1
                C(dr,dc) = step+1;
                PR(dr,dc) = r(i);
                PC(dr,dc) = c(i);
                count = count + 1; rnext(count) = dr; cnext(count) = dc;
            end
        end 
    end
end
path = zeros(0,4);
end

%%

function path = bridgepath(B,BH,BV,row,col,label,maxpathlen)

    function path = traceback(dr,dc,step)
%         fprintf('traceback, dr = %d, dc = %d, step = %d\n', dr, dc, step);
        PR(dr,dc) = r(i);
        PC(dr,dc) = c(i);
        path = zeros(step,4);
        j = 0;
        while dr ~= row(2) || dc ~= col(2)
            j = j + 1;
            path(j,1:2) = [dr dc];
            pr = PR(dr,dc);
            pc = PC(dr,dc);
            path(j,3:4) = [pr pc];
            dr = pr;
            dc = pc;
            if BRIDGE(dr,dc)
                j = j + 1;
                path(j,:) = [dr dc dr dc];
            end
        end
        path = path(1:j,:);
    end

% - bridgexpath -
% fprintf('bridgepath ...\n');
[NR NC] = size(B);
BRIDGE = false(NR,NC);
PR = zeros(NR,NC);
PC = zeros(NR,NC);
C = -ones(NR,NC);
C(row(2),col(2)) = 0; % source

maxstep = min(75+26,maxpathlen+1);
stepcount = zeros(maxstep+1+25,1);
for step = 0:maxstep
    if step == 0
        r = row(2);
        c = col(2);
    else
        if stepcount(step) == 0
            continue
        else
            [r c] = find(C == step);
        end
    end
    
    N = size(r,1);
%     fprintf('step = %d, N = %d\n', step, N);
    for i = 1:N
        dc = c(i);
        if r(i) > 1
            dr = r(i)-1;
            if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if C(dr,dc) == -1
                if B(dr,dc) == 0
                    C(dr,dc) = step+1; stepcount(step+1) = 1;
                    PR(dr,dc) = r(i);
                    PC(dr,dc) = c(i);
                elseif BV(dr,dc)
                    C(dr,dc) = step+1+25; stepcount(step+1+25) = 1;
                    PR(dr,dc) = r(i);
                    PC(dr,dc) = c(i);
                    BRIDGE(dr,dc) = true;
%                     fprintf('possible bridge, r=%d, c=%d\n', r, c);
                end
            end
        end
        if r(i) < NR
            dr = r(i) + 1;
            if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if C(dr,dc) == -1
                if B(dr,dc) == 0
                    C(dr,dc) = step+1; stepcount(step+1) = 1;
                    PR(dr,dc) = r(i);
                    PC(dr,dc) = c(i);
                elseif BV(dr,dc)
                    C(dr,dc) = step+1+25; stepcount(step+1+25) = 1;
                    PR(dr,dc) = r(i);
                    PC(dr,dc) = c(i);
                    BRIDGE(dr,dc) = true;
%                     fprintf('possible bridge, r=%d, c=%d\n', r, c);
                end
            end
        end
            
        dr = r(i);
        if c(i) > 1
            dc = c(i) - 1;
            if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if C(dr,dc) == -1
                if B(dr,dc) == 0
                    C(dr,dc) = step+1; stepcount(step+1) = 1;
                    PR(dr,dc) = r(i);
                    PC(dr,dc) = c(i);
                elseif BH(dr,dc)
                    C(dr,dc) = step+1+25; stepcount(step+1+25) = 1;
                    PR(dr,dc) = r(i);
                    PC(dr,dc) = c(i);
                    BRIDGE(dr,dc) = true;
%                     fprintf('possible bridge, r=%d, c=%d\n', r, c);
                end
            end
        end
        if c(i) < NC
            dc = c(i) + 1;
            if (dr == row(1) && dc == col(1)) || B(dr,dc) == label
                path = traceback(dr,dc,step+1);
                return
            end
%             expand();
            if C(dr,dc) == -1
                if B(dr,dc) == 0
                    C(dr,dc) = step+1; stepcount(step+1) = 1;
                    PR(dr,dc) = r(i);
                    PC(dr,dc) = c(i);
                elseif BH(dr,dc)
                    C(dr,dc) = step+1+25; stepcount(step+1+25) = 1;
                    PR(dr,dc) = r(i);
                    PC(dr,dc) = c(i);
                    BRIDGE(dr,dc) = true;
%                     fprintf('possible bridge, r=%d, c=%d\n', r, c);
                end
            end
        end 
    end
end
path = zeros(0,4);
end