Winner GUO (asdf1)

Finish 2004-11-10 09:00:00 UTC

TLL212

by Timothy Alderson

Status: Passed
Results: 40669
CPU Time: 64.4082
Score: 41.4527
Submitted at: 2004-11-09 23:06:06 UTC
Scored at: 2004-11-09 23:09:20 UTC

Current Rank: 82nd
Based on: It Takes A Thief (diff)

Comments
Please login or create a profile.
Code
function moves = solver(A, B, w0)

[moves,optmove,optscore] = cbest(A, B, w0);
curscore = sum( w0( moves(:,1) ) );
if length(moves) - optmove < 20 || curscore/optscore < 1.15
    return;
else
    lenw = length(w0);
    nseq = randperm(lenw);
    A1 = A;
    B1 = B;
    w01 = w0;
    for i=1:lenw
        A1(A==i) = nseq(i);
        B1(B==i) = nseq(i);
        w01( nseq(i) ) = w0(i);
    end;
    [moves2,optmove,optscore] = cbest(A1, B1, w01);
    moves22 = moves2;
    for i=1:lenw
        moves22( moves2(:,1)==nseq(i), 1) = i;
    end;
    curscore2 = sum( w0( moves22(:,1) ) );
    if curscore2 < curscore
        moves = moves22;
    end;
end;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [moves,optmove,optscore] = cbest(A, B, w0)

n = length(w0);
ipos1=zeros(n,1);
ipos2=ipos1;
fpos1=ipos1;
fpos2=ipos1;
for i=1:n
    [ipos1(i) ipos2(i)] = find(A==i);
    [fpos1(i) fpos2(i)] = find(B==i);
end
optmove = sum(abs(fpos1-ipos1)+abs(fpos2-ipos2));
optscore= sum((abs(fpos1-ipos1)+abs(fpos2-ipos2)).*w0);score=inf;

if n~=28 || (numel(A)/n) <= 1.98

  mv = TLL79(A,B,w0,optmove,optscore);
  movesTLL79=improve(A,B,w0,optmove,optscore,[ipos1 ipos2],[fpos1 fpos2],mv);

  scoreTLL79=sum(w0(movesTLL79(:,1)));

  if (scoreTLL79-optscore)>0;

    movesA5 = Arrange6(A, B, w0);
    scoreA5=sum(w0(movesA5(:,1)));
%  scoreA5=Inf;

    if scoreTLL79<scoreA5,
      moves = movesTLL79;
    else
      moves = movesA5;
    end
  else;
    moves = movesTLL79;
  end;
  flag =0;

else
    flag=1;
end

if ((n >= 18 && n <= 20) || n==28 || n==23 || (n>=13 && n <= 16)) &&...
        (flag || length(moves) > 1.18*optmove) && (numel(A)/n) > 1.98

    if ((score-optscore)<20)||(~flag&&(length(moves)-optmove)<2);return;end;

    ym = size(A,1);
    M = [ym 1 -ym -1];
    mask = isfinite(w0(:))';
    w = abs(w0(:)')+.1;

    rand('seed',42);
    [mov, ok] = mainsolver(A,B,w,mask);
    mov = 1*(mov==M(1)) + 2*(mov==M(2)) + 3*(mov==M(3)) + 4*(mov==M(4));
    mov = [(mov>0)*(1:n)' sum(mov,2)];

    mov=improve(A,B,w0,optmove,optscore,[ipos1 ipos2],[fpos1 fpos2],mov);

    if ok && flag==0
        res1 = sum(w0(moves(:,1)));
        res2 = sum(w0(mov(:,1)));
        if res2<res1
            moves = mov;
        end
    else
        moves = mov;
    end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [mov, ok] = mainsolver(A,B,w,mask)
n = sum(mask);
if n==0
    ok = 0;
    return
end
[mov, ok] = easysolver(A,B,w,mask);
if ok
    return
end
ipos = zeros(size(mask));
for i=find(mask)
    ipos(i) = find(A==i);
end
pos = cumsum([ipos; mov]);
invw = max(w)+1-w;
blockers = sum(findoverlaps(pos));
for leaveout = ceil(2*log(n)):(n-1)
    mmask = mask;
    choosew = sum(blockers).*invw;
    for i = 1:leaveout
        randi = rand*sum(mmask.*choosew);
        small=find(cumsum(mmask.*choosew)>=randi);
        choose = small(1);
        mmask(choose) = false;
    end
    Ap = zeros(size(A));
    Bp = zeros(size(B));
    for i = find(mmask)
        Ap(ipos(i)) = i;
        Bp(B==i) = i;
    end
    [partialmov, ok] = mainsolver(Ap, Bp, w+min(w)*rand(size(w)), mmask);
    blockers = blockers + sum(findoverlaps(cumsum([ipos;partialmov])));
    if ~ok
        continue
    end
    for i = find(mask)
        Ap(ipos(i)) = i;
    end
    for i = 1:3*sum(mask)
        randi = rand*sum(w.*(~mmask & mask));
        small=find(cumsum(w.*(~mmask & mask))>=randi);
        choose = small(1);
        [trymov, ok] = imoves(choose,partialmov,Ap,B,mmask);
        if ok
            partialmov = trymov;
            mmask(choose) = true;
            if isequal(mmask,mask)
                ok = 1;
                mov = partialmov;
                return
            end
        else
            dropw = blockers.*invw;
            randi = rand*sum(dropw.*(mmask&mask));
            small=find(cumsum(dropw.*(mmask&mask))>=randi);
            choose = small(1);
            mmask(choose) = false;
            partialmov(find(partialmov(:,choose)),:) = [];
        end
    end
    ok = 0;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [mov, ok] = imoves(c,mov,A,B,mask)
mov(find(mov(:,c)),:) = [];
nmov = size(mov,1);
n = length(mask);
[crow,ccol] = find(A==c);
[trow,tcol] = find(B==c);
if nmov == 0 && crow==trow && ccol==tcol
    ok = 1;
    return
end
[rows,cols] = size(A);
slices = false(rows, cols, nmov+1);
ipos = zeros(1,n);
for i=find(mask)
    ipos(i) = find(A(:)==i);
end
pos = cumsum([ipos; mov],1);
for k=1:(nmov+1)
    R = zeros(size(A));
    R(pos(k,mask)) = -1;
    slices(:,:,k) = (R==-1);
end
target = sub2ind(size(slices),trow,tcol,nmov+1);
optlen = abs(crow-trow) + abs(ccol-tcol);
nnnn = numel(slices);
path = dijkstra(nnnn,find(A==c), target, slices, (1+0.1*log(nnnn))*optlen);
if isempty(path)
    ok = 0;
    return
end
for i=length(path):-1:2
    if path(i)-path(i-1) < rows*cols
        k = floor((path(i-1)-1)/(rows*cols))+1;
        mov = [mov(1:(k-1),:); zeros(1,n); mov(k:end,:)];
        mov(k,c) = path(i)-path(i-1);
    end
end
ok = 1;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [moves, ok] = easysolver(A,B,w,mask)
global TEST
TEST=1;
NFIDDLE = 5;
ok = 0;
ym = size(A,1);
n = length(mask);
M = [ym 1 -ym -1];
moves = [];
ipos = zeros(1,n);
for i = find(mask)
    [row,col] = find(A==i);
    [rowt,colt] = find(B==i);
    nm = abs(col-colt) + abs(row-rowt);
    moves = [moves; zeros(nm,i-1) ...
        [M(1)*ones(max((colt-col),0),1); ...
        M(2)*ones(max((rowt-row),0),1); ...
        M(3)*ones(max((col-colt),0),1); ...
        M(4)*ones(max((row-rowt),0),1)] ...
        zeros(nm,n-i)];
    ipos(i) = (col-1)*ym + row;
end
nmov = size(moves,1);
if nmov == 0
    ok = 1;
    return
end
moves = moves(randperm(nmov),:);
for i=1:NFIDDLE
    pos = cumsum([ipos; moves]);
    okmov = min(find(any(findoverlaps(pos),2)))-1;
    if isempty(okmov)
        ok = 1;
        return
    end
    indperm = localfiddler(pos(okmov,:),moves(okmov:nmov,:),w);
    moves(okmov:nmov,:) = moves(okmov-1+indperm,:);
end
pos = cumsum([ipos; moves]);
small=find(any(findoverlaps(pos),2));
okmov = small(1)-1;
if isempty(okmov)
    ok=1;
    return
end
oldmoves = moves;
for i = 1:ceil(sqrt(nmov-okmov))
    pos = cumsum([ipos; moves]);
    overlap = findoverlaps(pos);
    if ~any(overlap(:))
        ok = 1;
        return
    else
        small=find(any(overlap,2));
        oli = small(1);
        small=find(overlap(oli,:));
        one = small(1);
        small=find(overlap(oli,:));
        other = small(end);
        rowinds = [oli-1 ...
            min(find(moves(:,one) & (1:nmov)'>=oli)) ...
            min(find(moves(:,other) & (1:nmov)'>=oli)) ...
            max(find(moves(:,one) & (1:nmov)'<oli-1)) ...
            max(find(moves(:,other) & (1:nmov)'<oli-1))];
        indperm = localfiddler(pos(oli-1,:),moves(rowinds,:),w);
        moves(rowinds,:) = moves(rowinds(indperm),:);
    end
end
pos = cumsum([ipos; moves]);
small=find(any(findoverlaps(pos),2));
if small(1)-1 < okmov
    moves = oldmoves;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function indperm = localfiddler(ipos,mov,w)
M = 4;
[nmov,n] = size(mov);
if nmov <= M
    M = nmov;
    P = perms(1:M);
else
    M = min(M,nmov);
    inds = (M+1):nmov;
    P = [perms(1:M) inds(ones(prod(2:M),1),:)];
    for i=1:size(P,1)
        P(i,M+1:nmov) = inds(randperm(nmov-M));
    end
end
f = zeros(size(P,1),1);
for i=1:size(P,1)
    newmov = mov(P(i,:),:);
    pos = cumsum([ipos;newmov]);
    overlap = findoverlaps(pos);
    if ~any(overlap(:))
        indperm = P(i,:);
        return
    else
        p = any(overlap,1);
        for c = 1:n
            if p(c)
                small=find(overlap(:,c));
                f(i) = f(i)+w(c)*small(1);
            else
                f(i) = f(i)+w(c)*nmov;
            end
        end
    end
end
[DNC, best] = max(f);
indperm = P(best,:);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function overlaps = findoverlaps(pos)
[npos,n] = size(pos);
cols = find(all(pos));
pos = pos(:,cols);
A = zeros(npos,length(cols));
[sortpos, ind] = sort(pos,2);
ind1 = ind(:,1:end-1);
ind2 = ind(:,2:end);
dp = diff(sortpos,1,2)==0;
for i=1:npos
    A(i,ind1(i,dp(i,:))) = true;
    A(i,ind2(i,dp(i,:))) = true;
end
overlaps = zeros(npos,n);
overlaps(:,cols) = A;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [path] = dijkstra(n, s, d, R, optlen)
[rows,cols,depth] = size(R);
R = R(:);
visited = false(1,n);
distance = inf*ones(1,n);
parent = zeros(1,n);
distance(s) = 0;
stack = zeros(1,n);
stack(1)=s;
next = 1;
last = 1;
for i = 1:(n-1),
    if next>last
        break
    else
        u = stack(next);
        next = next + 1;
    end
    visited(u) = true;
    ndx = u - 1;
    k = floor(ndx/(rows*cols)) + 1;
    ndx = rem(ndx, rows*cols);
    col = floor(ndx/rows) + 1;
    ndx = rem(ndx, rows);
    row = floor(ndx) + 1;
    v = u + 1;
    if v>0 && v<=n && ~R(v) && row<rows
        if distance(u) + 1 < distance(v)
            distance(v) = distance(u) + 1;
            parent(v) = u;
            if ~visited(v)
                if (v==d) && (distance(d) == optlen)
                    break
                end
                last = last + 1;
                stack(last) = v;
            end
        end
    end
    v = u - 1;
    if v>0 && v<=n && ~R(v) && row>1
        if distance(u) + 1 < distance(v)
            distance(v) = distance(u) + 1;
            parent(v) = u;
            if ~visited(v)
                if (v==d) && (distance(d) == optlen)
                    break
                end
                last = last + 1;
                stack(last) = v;
            end
        end
    end
    v = u + rows;
    if v>0 && v<=n && ~R(v) && col<cols
        if distance(u) + 1 < distance(v)
            distance(v) = distance(u) + 1;
            parent(v) = u;
            if ~visited(v)
                if (v==d) && (distance(d) == optlen)
                    break
                end
                last = last + 1;
                stack(last) = v;
            end
        end
    end
    v = u - rows;
    if v>0 && v<=n && ~R(v) && col>1
        if distance(u) + 1 < distance(v)
            distance(v) = distance(u) + 1;
            parent(v) = u;
            if ~visited(v)
                if (v==d) && (distance(d) == optlen)
                    break
                end
                last = last + 1;
                stack(last) = v;
            end
        end
    end
    v = u + rows*cols;
    if v>0 && v<=n && ~R(v) && k < depth
        if distance(u) < distance(v)
            distance(v) = distance(u);
            parent(v) = u;
            if ~visited(v)
                if (v==d) && (distance(d) == optlen)
                    break
                end
                last = last + 1;
                stack(last) = v;
            end
        end
    end
end

if parent(d) ~= 0
    path = zeros(1,distance(d)+depth);
    pathi = length(path);
    t = d;
    path(pathi) = d;
    pathi = pathi - 1;
    while t ~= s
        p = parent(t);
        path(pathi) = p;
        pathi = pathi - 1;
        t = p;
    end
else
    path = [];
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% This procedure tries to improve a given solution by removing
% repeated moves, and locally reordering some of the moves
% to reduce the energy.

function mv = improve(Ai,Af,w,optmove,optscore,Ci,Cf,mv)

dist = optscore;
n_blk = length(w);
I = [0  1  0 -1];
J = [1  0 -1  0];

sc = sum(w(mv(:,1))); mv_len = size(mv,1);
if sc==optscore; return;end;
if ((sc-optscore)<20)||((mv_len-optmove)<2);return;end

num_fail = 0; max_try = min(75,mv_len); max_fail = max_try;

for j_try = 1:max_try,

  sc_old = sc; A = Ai; C = Ci;

  j = 1;
  while j < mv_len,

    if (mv(j,1) == mv(j+1,1)) && (abs(mv(j,2) - mv(j+1,2)) == 2),

      % Removes consecutive opposite moves

      sc = sc - 2*w(mv(j,1));
      mv = mv([1:j-1,j+2:mv_len],:);
      mv_len = mv_len - 2;
      if sc == dist, return; end

    else

      % Make the next move earlier if it is not blocked

      if A(C(mv(j+1,1),1) + I(mv(j+1,2)),C(mv(j+1,1),2) + J(mv(j+1,2))) == 0,
        mv([j j+1],:)=mv([j+1 j],:);
      else
        if j+3 <= mv_len,
	  b = mv(j,1); c=mv(j+1,1); d=mv(j+2,1);

	  % Check if one block is going around another

          sit=0;
          if (b == mv(j+3,1)) && (abs(mv(j,2) - mv(j+3,2)) == 2)
            if (b == c) && (b == d) && (mv(j+1,2) == mv(j+2,2)),

	      % Here, one block is going around another. See if it cheaper
	      % for the second block to get out of the way of the first

              b1 = A(C(b,1) + I(mv(j+1,2)),C(b,2) + J(mv(j+1,2))); sit=1;

            else
              if (b == c) && (b ~= d) && (abs(mv(j+1,2) - mv(j+2,2)) == 2),

		% The blocks are swapping positions in a 4x4 square. Make the
		% lighter one move the further distance.

                b1 = d; sit=1;

              else
                if (b~=c) && (b==d) && (abs(mv(j+1,2) - mv(j+2,2)) == 2),

		  % Again, the blocks are swapping positions in a 4x4 square.
		  % Make the lighter one move the further distance.

                   b1 = c; sit = 1;

                else
                  if (b == c) && (b ~= d),

		    % A block is pushed out of the 4x4 square, while another
		    % takes its place by a convoluted path. Push the block
		    % out first, and then use a single push for the remaining
		    % block

		    sc = sc-2*w(b); mv(j,1)=d; mv(j,2)=mv(j+2,2);
		    mv=mv([1:j+1,j+4:mv_len],:); mv_len = mv_len - 2;
		  end
                end
              end
            end
	  end

          if sit == 1,
            if w(b1) < w(b),
              mv(j,1) = b1; mv(j+3,1) = b1;
              sc = sc - 2*(w(b)-w(b1));
            end
          end

	end
      end

      if sc==dist, return; end;

      b = mv(j,1); r = C(b,1); c = C(b,2);
      nr = r + I(mv(j,2)); nc = c + J(mv(j,2));
      A(r,c) = 0; A(nr,nc) = b;
      C(b,1) = nr; C(b,2) = nc;
      j = j + 1;
    end
  end

  if sc_old == sc,
    num_fail = num_fail+1;
    if num_fail == max_fail,
      break
    end
  else
    num_fail = 0;
  end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function move = TLL79(aInit, aFinal, wt, optmove, optscore)
o = [3; 4; 1; 2];
[move,score] = solverA(aInit, aFinal, wt, optmove, optscore,0);
if ((score-optscore)>20)||((length(move)-optmove)>3);
    [mv2,score2] = solverA(aFinal, aInit, wt, optmove, optscore,0);
    if score > score2
        move = mv2(end:-1:1,:);
        score = score2;
        move(:,2)=o(move(:,2));
    end
    if ((score-optscore)>20)||((length(move)-optmove)>3);
        a = aInit;
        midmoves = floor(size(move,1)/2);
        I = [0  1  0 -1];
        J = [1  0 -1  0];
        for k = 1:midmoves
            [row, col] = find(a==move(k,1));
            a(row,col) = 0;
            % new position of the block
            row = row + I(move(k,2));
            col = col + J(move(k,2));
            % place the block in the new position
            a(row, col) = move(k,1);
        end
        oldscore1 = sum(wt(move(1:midmoves,1)));
        oldscore2 = sum(wt(move(midmoves+1:size(move,1),1)));
        [newmove,newscore] = solverA(aInit, a, wt, optmove, optscore,1);
        [newmove2,newscore2] = solverA(a, aFinal, wt, optmove, optscore,1);
        newscore1 = sum(wt(newmove(:,1)));
        newscore2 = sum(wt(newmove2(:,1)));
        oldmove = move;
        if(newscore1 < oldscore1)
            move = newmove;
            if(newscore2 < oldscore2)
                for itr = 1:size(newmove2,1)
                    move(end+1,[1 2]) = [newmove2(itr,1) newmove2(itr,2)];
                end
            else
                for itr = midmoves+1:size(oldmove,1)
                    move(end+1,[1 2]) = [oldmove(itr,1) oldmove(itr,2)];
                end
            end
        else
            if(newscore2 < oldscore2)
                move = [];
                for itr = 1:midmoves
                    move(end+1,[1 2]) = [oldmove(itr,1) oldmove(itr,2)];
                end
                for itr = 1:size(newmove2,1)
                    move(end+1,[1 2]) = [newmove2(itr,1) newmove2(itr,2)];
                end
            end
        end
    end
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [move,score] = solverA(aInit, aFinal, wt, optmove, optscore,half)
global Dperfect
Dperfect=optmove;if half;optmove=1e20;optscore=1e20;end;
[move,isPerfect,score]=solver2(aInit,aFinal,wt,1111,optscore);
if ~isPerfect;
    move1=solver1(aInit,aFinal,wt,score);
    if ( ~isempty(move1) )
        isPerfect=length(move1)==Dperfect;
        score1=sum(wt(move1(:,1)));
        if score1<score;
            score=score1;move=move1;
        end;
    end
end;
if ((score-optscore)>20)||((length(move)-optmove)>5);
    move1=solver3(aInit,aFinal,wt,1111,optscore);
    if ( ~isempty(move1) )
        isPerfect=length(move1)==Dperfect;
        score1=sum(wt(move1(:,1)));
        if score1<score;score=score1;
            move=move1;
        end;
    end
end;
if isPerfect;score=0;end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function move = solver1(aInit, aFinal, wt, bscore)
COUNTERS=0;
allmoves  = [];
wtinitori = wt;
sortbydist   = 0;
sortbyweight = 1;
minw = 10000;
if sortbyweight
    [tmp inds] = sort(-wt);
    wtinit = wtinitori;
end;
lenwt = length(wt);
absx = zeros(lenwt,1);
absy = absx;
for index = 1:lenwt
    [hvix hviy] = find(aInit  == index);
    [hvfx hvfy] = find(aFinal == index);
    absx(index) = abs(hvix-hvfx);
    absy(index) = abs(hviy-hvfy);
end;
if sortbydist
    dist = abs(absx) + abs(absy);
    [tmp inds] = sort(-dist);
    wtinit = wtinitori;
end;
for index = 1:length(inds)
    hv = inds(index);
    [hvix hviy] = find(aInit  == hv);
    [hvfx hvfy] = find(aFinal == hv);
    dist = abs(hvix-hvfx)+abs(hviy-hvfy);
    wt(hv) = -Inf;
    wtinit(hv) = wtinit(hv)+minw+10000;
    [move cost aInit COUNTERS] = movefrompos(hv, [hvix hviy], [hvfx hvfy], aInit, aFinal, wtinit, 1, dist+5, COUNTERS);
    if COUNTERS>500;move=[];return;end;
    if isinf(cost) || isempty(move)
    else
        move = [move(:,1) 3*abs(move(:,4))-move(:,4)+2*abs(move(:,5))-move(:,5) ];
        allmoves = [allmoves; move];
        if ( sum(wtinitori(allmoves(:,1)))>bscore )
            move=[];
            return;
        end
    end;
end;
count   = 1;
oldinds = [];
while ~isequal(aFinal,aInit)
    sortbyweight = sortbydist;
    sortbydist   = ~sortbyweight;
    if sortbyweight
        inds = find(aFinal ~= aInit);
        inds = aFinal(inds);
        inds = inds(inds > 0);
        [tmp indices] = sort(-wt(inds));

        inds = inds(indices);
    end;
    if sortbydist
        for index = 1:length(wt)
            [hvix hviy] = find(aInit  == index);
            [hvfx hvfy] = find(aFinal == index);
            dist(index) = abs(hvix-hvfx)+abs(hviy-hvfy);
        end;
        [tmp inds] = sort(-dist);
        firstzeros = find(tmp == 0);
        inds(firstzeros:end) = [];
    end;
    wtinit = wtinitori;
    notmove = setdiff(oldinds, inds);
    for hv = 1:length(notmove)
        wtinit(notmove(hv)) = wtinit(notmove(hv))+minw+10000;
    end;
    for hind = 1:length(inds)
        hv = inds(hind);
        [hvix hviy] = find(aInit  == hv);
        [hvfx hvfy] = find(aFinal == hv);
        dist = abs(hvix-hvfx)+abs(hviy-hvfy);
        wtinit(hv) = wtinit(hv)+minw+10000;
        [move cost aInit COUNTERS] = movefrompos(hv, [hvix hviy], [hvfx hvfy], aInit, aFinal, wtinit, 1, dist+6, COUNTERS);
        if COUNTERS>500;move=[];return;end;
        if hind > 1
            wtinit(inds(hind-1)) = wtinit(inds(hind-1))-minw-10000;
        end;
        if isinf(cost) || isempty(move)
        else
            move = [move(:,1) 3*abs(move(:,4))-move(:,4)+2*abs(move(:,5))-move(:,5) ];
            allmoves = [allmoves; move];
            if ( sum(wtinitori(allmoves(:,1)))>bscore )
                move=[];
                return;
            end
        end;
    end;
    oldinds = inds;
    count = count+1;
end;
move = allmoves;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [move, cost, curposnew,COUNTERS] = movefrompos(item, pinit, pfin, curpos, finpos, wt, strategy, recur,COUNTERS)
CONTERS=COUNTERS+1;
cost = 0;
curposnew = curpos;
if isequal(pinit,pfin), move = []; return; end;
if recur == 0, move = []; cost = 0; return; end;
diffx = pfin(1)-pinit(1);
diffy = pfin(2)-pinit(2);
dirx = sign(diffx);
diry = sign(diffy);
cost = Inf;
if (strategy < 10 && abs(diffx) > abs(diffy)) || (strategy == 11 && abs(diffx) < abs(diffy))
    if dirx && curpos(pinit(1)+dirx, pinit(2)) <= 0
        [move cost curposnew COUNTERS] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if length(move) > 0 && cost/size(move,1) == mod(wt(curpos(pinit(1),pinit(2))),10000), return; end;
    end;
    if diry && curpos(pinit(1), pinit(2)+diry) <= 0
        [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if length(move1) > 0 && cost1/size(move1,1) == mod(wt(curpos(pinit(1),pinit(2))),10000)
            move=move1;
            cost=cost1;
            curposnew=curposnew1;
            return;
        end;
        if cost1<cost
            move = move1;
            cost = cost1;
            curposnew = curposnew1;
        end
    end;
else
    if diry && curpos(pinit(1), pinit(2)+diry) <= 0
        [move cost curposnew COUNTERS] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if length(move) > 0 && cost/size(move,1) == mod(wt(curpos(pinit(1),pinit(2))),10000), return; end;
    end;
    if dirx && curpos(pinit(1)+dirx, pinit(2)) <= 0
        [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if length(move1) > 0 && cost1/size(move1,1) == mod(wt(curpos(pinit(1),pinit(2))),10000)
            move=move1;
            cost=cost1;
            curposnew=curposnew1;
            return;
        end;
        if cost1<cost
            move = move1;
            cost = cost1;
            curposnew = curposnew1;
        end
    end;
end;
if isinf(cost) || cost == 0
    if dirx && diry && curpos(pinit(1), pinit(2)+diry) > 0 && curpos(pinit(1)+dirx, pinit(2)) > 0
        [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if cost1<cost
            move = move1;
            cost = cost1;
            curposnew = curposnew1;
        end
        [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if cost1<cost
            move = move1;
            cost = cost1;
            curposnew = curposnew1;
        end
    else
        if dirx && curpos(pinit(1)+dirx, pinit(2)) > 0
            [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
            if cost1<cost
                move = move1;
                cost = cost1;
                curposnew = curposnew1;
            end
        end;
        if diry && curpos(pinit(1), pinit(2)+diry) > 0
            [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
            if cost1<cost
                move = move1;
                cost = cost1;
                curposnew = curposnew1;
            end
        end;
    end;
end;
if isinf(cost) && recur > 1 && abs(strategy) < 5
    mv  = [dirx diry];
    mv1 = abs(mv)-1;
    if any(mv1)
        mv2 = abs(mv1);
        mv3 = -mv;
        ok3 = 1;
    else
        mv1 = [-mv(1) 0];
        mv2 = [0 -mv(2)];
        ok3 = 0;
    end;
    sz  = size(curpos);
    strategy = strategy + sign(strategy)*1;
    if all(pinit+mv1 > 0) && all(pinit+mv1 <= sz) && ~curpos(pinit(1)+mv1(1),pinit(2)+mv1(2))
        [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if cost1<cost
            move = move1;
            cost = cost1;
            curposnew = curposnew1;
        end
    end;
    if all(pinit+mv2 > 0) && all(pinit+mv2 <= sz) && ~curpos(pinit(1)+mv2(1),pinit(2)+mv2(2))
        [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if cost1<cost
            move = move1;
            cost = cost1;
            curposnew = curposnew1;
        end
    end;
    if ok3 && all(pinit+mv3 > 0) && all(pinit+mv3 <= sz) && ~curpos(pinit(1)+mv3(1),pinit(2)+mv3(2))
        [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if cost1<cost
            move = move1;
            cost = cost1;
            curposnew = curposnew1;
        end
    end;
    if all(pinit+mv1 > 0) && all(pinit+mv1 <= sz) && curpos(pinit(1)+mv1(1),pinit(2)+mv1(2)) > 0
        [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if cost1<cost
            move = move1;
            cost = cost1;
            curposnew = curposnew1;
        end
    end;
    if all(pinit+mv2 > 0) && all(pinit+mv2 <= sz) && curpos(pinit(1)+mv2(1),pinit(2)+mv2(2)) > 0
        [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if cost1<cost
            move = move1;
            cost = cost1;
            curposnew = curposnew1;
        end
    end;
    if ok3 && all(pinit+mv3 > 0) && all(pinit+mv3 <= sz) && curpos(pinit(1)+mv3(1),pinit(2)+mv3(2)) > 0
        [move1 cost1 curposnew1 COUNTERS] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if cost1<cost
            move = move1;
            cost = cost1;
            curposnew = curposnew1;
        end
    end;

end;
if isinf(cost)
    move=[];
    curposnew = curpos;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [move, cost, curpos, COUNTERS] = onemove(item, pinit, movedir, pfin, curpos, finpos, wt, strategy, recur, COUNTERS)
COUNTERS=COUNTERS+1;
move3=0;
curcost  = mod(wt(curpos(pinit(1), pinit(2))), 10000);
costnew3 = 0;
newpos   = pinit+movedir;
if curpos(newpos(1), newpos(2)) > 0
    if wt(curpos(newpos(1), newpos(2))) > 8000
        cost = Inf;
        move = [];
        return;
    end;
    if wt(curpos(newpos(1), newpos(2))) > 2*curcost && recur > 0 && strategy > 0
        tmppos1 =  abs(movedir)-1   + pinit;
        tmppos2 =  abs(movedir)-1   + pinit;
        tmppos3 = movedir + tmppos1;
        tmppos4 = movedir + tmppos2;
        sz = size(curpos);
        wt2       = [0; wt];
        curpos2 = curpos;
        curpos2(curpos2 < 0) = 0;
        curpos2 = curpos2+1;
        tmpcost = [Inf Inf];
        if all(tmppos1 > 0) && all(tmppos1 <= sz)
            if all(tmppos3 > 0) && all(tmppos3 <= sz)
                tmpcost(1) = wt2(curpos2(tmppos1(1), tmppos1(2))) + wt2(curpos2(tmppos1(1), tmppos1(2))) + 2*curcost;
            end;
        end;
        tmpcost(2)=tmpcost(1);
        if tmpcost(2) < wt(curpos(newpos(1), newpos(2)))
            [move3 costnew3 curpostmp COUNTERS] = onemove(item, pinit, tmppos2-pinit, pfin, curpos, finpos, wt, strategy, -1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
            if ~isinf(costnew3)
                [move4 costnew4 curpostmp COUNTERS] = onemove(item, tmppos2, tmppos4-tmppos2, pfin, curpostmp, finpos, wt, strategy, -1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
                if ~isinf(costnew4)
                    [move5 costnew5 curpostmp COUNTERS] = movefrompos(item, tmppos4, pfin, curpostmp, finpos, wt, -strategy, recur-1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
                    cost = costnew3 + costnew4 + costnew5;
                    move = [move3; move4; move5];
                    if ~isinf(cost), curpos = curpostmp; end;
                    return;
                end;
            end;
        end;
    end;
    newitem = curpos(newpos(1), newpos(2));
    [pfin2(1) pfin2(2)] = find(finpos == newitem);
    dirx2 = sign(pfin2(1)-newpos(1));
    diry2 = sign(pfin2(2)-newpos(2));
    wt(newitem) = wt(newitem) + 20000;
    if isequal([dirx2 diry2],-movedir) || isequal(newpos,pfin2)
        costnew3 = Inf;
    else
        [move3 costnew3 curposnew COUNTERS] = movefrompos(newitem, newpos, pfin2, curpos, finpos, wt, strategy, -1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
        if costnew3 == 0, costnew3 = Inf; end;
        if ~isinf(costnew3), curpos = curposnew; end;
    end;
    if isinf(costnew3)
        wtdir = [ Inf Inf Inf Inf ];
        diffpos = pfin - newpos;
        if (diffpos(1) && movedir(1)) || (diffpos(2) && movedir(2))
            mv1 = abs(movedir)-1;
        else
            if any(sign(diffpos) > 0)
                mv1 = abs(movedir)-1;
            else
                mv1 = abs(abs(movedir)-1);
            end;
        end;
        mv2 = -mv1;
        mv3 = movedir;
        sz  = size(curpos);
        if all(newpos+mv1 > 0) && all(newpos+mv1 <= sz)

            if curpos(newpos(1)+mv1(1),newpos(2)+mv1(2)) <= 0
                [move3 costnew3 curpos COUNTERS] = movefrompos(newitem, newpos, newpos+mv1, curpos, finpos, wt, strategy, -1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
            else wtdir(1) = wt(curpos(newpos(1)+mv1(1),newpos(2)+mv1(2)));
            end;
        end;
        if isinf(costnew3) && all(newpos+mv2 > 0) && all(newpos+mv2 <= sz)
            if curpos(newpos(1)+mv2(1),newpos(2)+mv2(2)) <= 0
                [move3 costnew3 curpos COUNTERS] = movefrompos(newitem, newpos, newpos+mv2, curpos, finpos, wt, strategy, -1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
            else wtdir(2) = wt(curpos(newpos(1)+mv2(1),newpos(2)+mv2(2)));
            end;
        end;
        if isinf(costnew3) && all(newpos+mv3 > 0) && all(newpos+mv3 <= sz)
            if curpos(newpos(1)+mv3(1),newpos(2)+mv3(2)) <= 0
                [move3 costnew3 curpos COUNTERS] = movefrompos(newitem, newpos, newpos+mv3, curpos, finpos, wt, strategy, -1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
            else wtdir(3) = wt(curpos(newpos(1)+mv3(1),newpos(2)+mv3(2)));
            end;
        end;
        if isinf(costnew3)
            [wtdir si] = sort(wtdir);
            for index = 1:length(wtdir)
                if ~isinf(wtdir(index)) && isinf(costnew3)
                    switch si(index),
                        case 1, [move3 costnew3 curpos COUNTERS] = movefrompos(newitem, newpos, newpos+mv1, curpos, finpos, wt, strategy, -1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
                        case 2, [move3 costnew3 curpos COUNTERS] = movefrompos(newitem, newpos, newpos+mv2, curpos, finpos, wt, strategy, -1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
                        case 3, [move3 costnew3 curpos COUNTERS] = movefrompos(newitem, newpos, newpos+mv3, curpos, finpos, wt, strategy, -1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
                    end;
                end;
            end;
        end;
    end;
    wt(newitem) = wt(newitem) - 20000;
    if isinf(costnew3) || costnew3 == 0
        cost = Inf;
        move = [];
        return;
    end;
end;
if curpos(newpos(1), newpos(2)) == -item
    cost = Inf;
    move = [];
    return;
end;
curpos(newpos(1), newpos(2)) =  curpos(pinit(1), pinit(2));
curpos(pinit(1) , pinit(2) ) = -curpos(pinit(1), pinit(2));
if recur > 0
    [move2 costnew curposnew, COUNTERS] = movefrompos(item, pinit+movedir, pfin, curpos, finpos, wt, strategy, recur-1, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
else
    [move2 costnew curposnew, COUNTERS] = movefrompos(item, pinit+movedir, pfin, curpos, finpos, wt, strategy, 0, COUNTERS);if COUNTERS>500;move=[];cost=[];curposnew=[];return;end;
end;
curpos = curposnew;
if curpos(pinit(1), pinit(2))<0
    curpos(pinit(1), pinit(2)) = 0;
end;
if numel(move3)==1 && isempty(move2);
    move = [item pinit movedir];
elseif numel(move3)==1
    move = [item pinit movedir; move2];
elseif isempty(move2)
    move = [ move3; item pinit movedir];
else;
    move = [ move3; item pinit movedir; move2];
end;
cost = costnew3+costnew+curcost;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [mv,perfectMV,score] = solver2(ai,af,w,states,optscore)
global Ac Ar m2 Dperfect
perfectMV=false;
nBlocks = length(w);
[m,n] = size(ai);
m2=m+2;
n2=n+2;
A = -ones(m2,n2);
Af = A;
A( 2:m+1, 2:n+1 ) = ai;
Af( 2:m+1, 2:n+1 ) = af;
Ac=1:n2;
Ac=Ac(ones(m2,1),:);
Ar=(1:m2)';
Ar=Ar(:,ones(n2,1));
Pi=w;
Pf=w;
for i=m2+2:numel(A)-m2-1
    if A(i)>0, Pi(A(i)) = i; end
    if Af(i)>0, Pf(Af(i)) = i; end
end
P=Pi;
nmv=1;
mv = zeros(300,2);
nNOK=sum(P~=Pf);
Paths=zeros(m+n,nBlocks);
lPaths=w;
fPaths=w;
Pend=w;
bOK=w;
obs=zeros(nBlocks,2);
nmv0=0;
while nmv0<nmv&&nNOK
    obs(:)=0;
    nmv0=nmv;
    for i=1:nBlocks
        if P(i)==Pf(i)
            lPaths(i)=0;
            fPaths(i)=0;
            bOK(i)=1;
        else
            [P1,f1]=SearchPath(A,P(i),Pf(i));
            if isempty(P1)
                lPaths(i)=0;
                fPaths(i)=0;
                obs(i,1:length(f1))=f1;
            else
                if isempty(f1)
                    fPaths(i)=1;
                else
                    fPaths(i)=0;
                    obs(i,1:length(f1))=f1;
                end
                lPaths(i)=length(P1);
                Paths(1:lPaths(i),i)=P1';
                Pend(i)=P1(end);
            end
            bOK(i)=0;
        end
    end
    iP=find(~bOK&lPaths);
    PCol=zeros(length(iP));
    L=lPaths(iP);
    for i=1:length(iP)
        Pe=Pend(iP(i));
        for j=1:length(iP)
            if i~=j
                lj=L(j);
                PCol(i,j)=any(Paths(1:lj,iP(j))==Pe);
            end
        end
    end
    sPCol=sum(PCol,2);
    pOK=find(sPCol==0);
    pNOK=find(sPCol~=0);
    if isempty(pOK)
        if length(pNOK)==1
            pOK(end+1)=pNOK;
        elseif ~isempty(pNOK)
            if length(pNOK)>1&&any(fPaths(iP(pNOK)))
                pNOK(~fPaths(iP(pNOK)))=[];
            end
            iNOK1=pNOK(find(sPCol(pNOK)==1));
            for i=iNOK1'
                j=find(PCol(i,:));
                jj=iP(j);
                p=iP(i);
                pe=Pend(p);
                A(P(p))=0;
                A(pe)=p;
                [P1,f1]=SearchPath(A,P(jj),Pf(jj));
                A(P(p))=p;
                A(pe)=0;
                if isempty(f1)
                    pOK(end+1)=i;
                    break
                end
            end
        end
    end
    if length(pOK)>1
        obs1=abs(obs(:));
        temp = zeros(1,length(obs1));
        i=1;
        q=0;
        pOK1=pOK;
        while i<=length(obs1)
            temp(obs1==obs1(i))=1;
            if sum(temp)>1
                j=find(obs1==obs1(i));
                obs1(j(2:end))=[];
            end
            if any(obs1(i)==pOK)
                q=1;
                j=find(obs1(i)==pOK);
                pOK1(j)=0;
            end
            i=i+1;
        end
        if q
            pOK(pOK1~=0)=[];
        end
        if length(pOK)>1&&any(fPaths(iP(pOK)))
            pOK(~fPaths(iP(pOK)))=[];
        end
    end
    j=1;
    while j<=length(pOK)
        i=pOK(j);
        b=iP(i);
        k=nmv+1:nmv+L(i);
        mv(k,1)=b;
        mv(k,2)=Paths(1:L(i),b);
        nmv=nmv+L(i);
        A(P(b))=0;
        A(Pend(b))=b;
        P(b)=Pend(b);
        if fPaths(b)
            nNOK=nNOK-1;
        end
        j=j+1;
    end
end
P=Pi;
for i=2:nmv
    b=mv(i);
    p=mv(i,2);
    dp=p-P(b);
    if dp==1
        mv(i,2)=2;
    elseif dp==-1
        mv(i,2)=4;
    elseif dp==m2
        mv(i,2)=1;
    else
        mv(i,2)=3;
    end
    P(b)=p;
end
mv=mv(2:nmv,:);
if nNOK
    rand('state',states);
    mv2=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
    score=sum(w(mv2(:,1)));
    if abs(score-optscore)<5;perfectMV=(Dperfect==size(mv2,1));mv=mv2;return;end;
    rand('state',states*2);
    mv1=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
    score1=sum(w(mv1(:,1)));
    if score1==score;
        mv=mv2;
        score=score1;
    else
        if score1<score;
            mv2=mv1;
            score=score1;end;
        if abs(score-optscore)<5;perfectMV=(Dperfect==size(mv2,1));mv=mv2;return;end;
        rand('state',states*371);
        mv1=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
        score1=sum(w(mv1(:,1)));
        if score1==score;mv=mv2;perfectMV = Dperfect==size(mv,1);return;end;
        if score1<score;
            mv2=mv1;score=score1;
        end;
        if abs(score-optscore)<5;perfectMV=(Dperfect==size(mv2,1));mv=mv2;return;end;
        rand('state',states*173);
        mv1=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
        score1=sum(w(mv1(:,1)));
        if score1<score;
            mv2=mv1;score=score1;
        end;
        mv=mv2;
    end
    perfectMV = Dperfect==size(mv,1);
else
    score=sum(w(mv(:,1)));
    perfectMV = 1;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [P,stopped]=SearchPath(A, p1, p2)
global Ac Ar m2
c1=Ac(p1);c2=Ac(p2);
r1=Ar(p1);r2=Ar(p2);
stopped=[];
P=[];
if r1>r2
    d_r=-1;
elseif r1<r2
    d_r=1;
else
    d_r=0;
end
if c1>c2
    d_c=-1;
elseif c1<c2
    d_c=1;
else
    d_c=0;
end
n=0;
p=p1;
if d_r==0||d_c==0
    while p~=p2
        np=p+d_c*m2+d_r;
        if A(np)
            stopped=A(np);
            break
        end
        p=np;
        n=n+1;
        P(n)=p;
    end
else
    Ah=A;
    c=c2;
    i1=p2-d_r;
    r_1=r2-d_r;
    while c~=c1
        r=r_1;
        r_1=0;
        i2=i1;
        while r~=r1
            if Ah(i2)
                Afil=-Ah(i2);
                if r==r2
                    r_1=r2;
                    i1=i2-d_c*m2;
                else
                    r_1=r+d_r;
                    i1=i2-d_c*m2+d_r;
                end
                r=r-d_r;
                i2=i2-d_r;
                while r~=r1
                    if Ah(i2)==0
                        Ah(i2)=Afil;
                    end
                    r=r-d_r;
                    i2=i2-d_r;
                end
                if Ah(i2)==0
                    Ah(i2)=Afil;
                end
                break;
            end
            r=r-d_r;
            i2=i2-d_r;
        end
        if r_1==0&&Ah(i2)
            i1=i2-d_c*m2+d_r;
            r_1=r+d_r;
        end
        c=c-d_c;
        if r_1==0
            break;
        end
    end
    r=r2;
    i1=p2-d_c*m2;
    c_1=c2-d_c;
    while r~=r1
        c=c_1;
        c_1=0;
        i2=i1;
        while c~=c1
            if Ah(i2)
                if Ah(i2)<0
                    Afil=Ah(i2);
                else
                    Afil=-Ah(i2);
                end
                if c==c2
                    c_1=c2;
                    i1=i2-d_r;
                else
                    c_1=c+d_c;
                    i1=i2-d_r+d_c*m2;
                end
                c=c-d_c;
                i2=i2-d_c*m2;
                while c~=c1
                    if Ah(i2)==0
                        Ah(i2)=Afil;
                    end
                    c=c-d_c;
                    i2=i2-d_c*m2;
                end
                if Ah(i2)==0
                    Ah(i2)=Afil;
                end
                break;
            end
            c=c-d_c;
            i2=i2-d_c*m2;
        end
        if c_1==0&&Ah(i2)
            i1=i2-d_r+d_c*m2;
            c_1=c+d_c;
        end
        r=r-d_r;
        if c_1==0
            break;
        end
    end
    while p~=p2
        if c1~=c2&&Ah(p+m2*d_c)==0
            di=m2*d_c;
            dc=d_c;
            dr=0;
        elseif r1~=r2&&Ah(p+d_r)==0
            di=d_r;
            dc=0;
            dr=d_r;
        else
            if c1==c2
                stopped=Ah(p+d_r);
            elseif r1==r2
                stopped=Ah(p+m2*d_c);
            else
                stopped=[Ah(p+d_r) Ah(p+m2*d_c)];
            end
            break;
        end
        p=p+di;
        n=n+1;
        P(n)=p;
        r1=r1+dr;
        c1=c1+dc;
    end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function bmovelist = Faster10IntReps2(init,final,wts)
global Dperfect
numtimes = 8;
if(max(size(init)) > 30) && max(size(wts))/(size(init,1)*size(init,2))>0.25
    numtimes = 10;
elseif(max(size(init)) > 30)
    numtimes = 7;
elseif(max(size(init)) < 11)
    numtimes = 2;
end
bscore=1e20;
for repcount = 1:numtimes
    [movelist,c] = matrixsolver(init,final,wts);
    bf = length(wts)+1+zeros(size(init)+2);
    bf(2:end-1,2:end-1) = final;
    tries = 1;
    maxtries = 15;
    while ~isequal(c,bf) && (tries < maxtries)
        randwts = rand(size(wts));
        [addtomovelist,c] = matrixsolver(c(2:end-1,2:end-1),final,randwts);
        movelist = [movelist;addtomovelist];
        tries = tries+1;
    end
    if ~isequal(c,bf)
        movegoaltries = 0;
        while ~isequal(c,bf) && (movegoaltries<20)
            problemboxes = c(c~=bf & c~=0);
            openspots = find(c==0);
            tempfinal = bf;
            for i = 1:length(problemboxes)
                cgind = find(bf==problemboxes(i));
                tempfinal(cgind) =0;
                newind = ceil(rand*length(openspots));
                tempfinal(openspots(newind)) = problemboxes(i);
                openspots(newind) = [];
            end
            randwts = rand(size(wts));
            [addtomovelist,c] = matrixsolver(c(2:end-1,2:end-1),tempfinal(2:end-1,2:end-1),randwts);
            movelist = [movelist;addtomovelist];
            movegoaltries = movegoaltries+1;
            aftermovegoaltries = 0;
            while ~isequal(c,bf) && aftermovegoaltries<5
                randwts = rand(size(wts));
                [addtomovelist,c] = matrixsolver(c(2:end-1,2:end-1),final,randwts);
                movelist = [movelist;addtomovelist];
                aftermovegoaltries = aftermovegoaltries+1;
            end
        end
    end
    score = sum(wts(movelist(:,1)));
    if score<bscore
        bmovelist = movelist;
        if length(bmovelist)==Dperfect;return;end;
        bscore=score;
    end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [movelist,c] = matrixsolver(init,final,wts)
biggermatrix = length(wts)+1+zeros(size(init)+2);
bi = biggermatrix;
bf = bi;
bi(2:end-1,2:end-1) = init;
bf(2:end-1,2:end-1) = final;
c = bi;
[m,n] = size(c);
numboxes = length(wts);
[DNC,wtorder] = sort(wts);
movelist = zeros(0,2);
for i = 1:numboxes
    cbn = wtorder(i);
    cr = 0; cc = 0; fr = 0; fc = 0;
    for j=2:m-1,
        for k=2:n-1,
            if c(j,k)==cbn, cr = j; cc = k; if fr>0, break; end;end;
            if bf(j,k)==cbn, fr = j; fc = k; if cr>0, break; end; end
        end
        if fr>0&&cr>0, break; end
    end
    dr = fr-cr;
    dc = fc-cc;
    while dr~=0 || dc~=0
        neighborhood = [c(cr,cc+1),c(cr+1,cc),c(cr,cc-1),c(cr-1,cc)];
        opendirs = find(~neighborhood);
        desireddirs = [];
        if dr~=0
            desireddirs(end+1) = -sign(dr)+3;
        end
        if dc~=0
            desireddirs(end+1) = -sign(dc)+2;
        end
        pic = opendirs(ismember1(opendirs,desireddirs));
        if ~isempty(pic)
            if length(pic)>1
                if abs(dr)>abs(dc)
                    movedir = desireddirs(1);
                else
                    movedir = desireddirs(2);
                end
            else
                movedir = pic;
            end
        else
            ind = ceil(rand*length(desireddirs));
            boxtomove = neighborhood(desireddirs(ind));
            switch desireddirs(ind)
                case {1,3}
                    rcaxis = -1;
                case {2,4}
                    rcaxis = 1;
            end
            [c,movelist,rejectflag] = outoftheway(boxtomove,rcaxis,cbn,c,movelist,bf);
            ootwtries = 1;
            while rejectflag && ootwtries<10
                [c,movelist,rejectflag] = outoftheway(boxtomove,rcaxis,cbn,c,movelist,bf);
                ootwtries = ootwtries+1;
            end
            movedir = desireddirs(ind);
        end
        c(cr,cc) = 0;
        switch movedir
            case 1
                cc = cc+1;
            case 2
                cr = cr+1;
            case 3
                cc = cc-1;
            case 4
                cr = cr-1;
        end
        c(cr,cc) = cbn;
        movelist(end+1,:) = [cbn,movedir];
        dr = fr-cr;
        dc = fc-cc;
    end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [c,movelist,rejectflag] = outoftheway(boxnumber,rcaxis,dontmovetheseboxes,c,movelist,bf)
c_in = c;
movelist_in = movelist;
rejectflag = 0;
[cr,cc] = find(c==boxnumber);
neighborhood = [c(cr,cc+1),c(cr+1,cc),c(cr,cc-1),c(cr-1,cc)];
opendirs = find(~neighborhood);
if isempty(opendirs)
    switch rcaxis
        case -1
            bettercandidates = neighborhood([2,4]);
            worsecandidates = neighborhood([1,3]);
        case 1
            bettercandidates = neighborhood([1,3]);
            worsecandidates = neighborhood([2,4]);
    end
    wallnum = c(1,1);
    remainingcandidates = setdiff(bettercandidates,[dontmovetheseboxes,wallnum]);
    if isempty(remainingcandidates)
        remainingcandidates = setdiff(worsecandidates,[dontmovetheseboxes,wallnum]);
        if isempty(remainingcandidates)
            rejectflag = 1;
            c = c_in;
            movelist = movelist_in;
            return
        end
    end
    if length(remainingcandidates)>1
        remainingcandidates = remainingcandidates((rand>.51)+1);
    end
    [c,movelist,rejectflag] = outoftheway(remainingcandidates,-rcaxis,[dontmovetheseboxes,boxnumber],c,movelist,bf);
    if rejectflag
        c = c_in;
        movelist = movelist_in;
        return
    end
    movedir = find(neighborhood==remainingcandidates);
else
    [cr,cc] = find(c==boxnumber);
    [fr,fc] = find(bf==boxnumber);
    dr = fr-cr;
    dc = fc-cc;
    desireddirs = [];
    if dr~=0
        desireddirs(end+1) = -sign(dr)+3;
    end
    if dc~=0
        desireddirs(end+1) = -sign(dc)+2;
    end
    pic = opendirs(ismember1(opendirs,desireddirs));
    if ~isempty(pic)
        if length(pic)>1
            if abs(dr)>abs(dc)
                movedir = desireddirs(1);
            else
                movedir = desireddirs(2);
            end
        else
            movedir = pic;
        end
    else
        movedir = opendirs(ceil(rand*length(opendirs)));
    end
end
c(cr,cc) = 0;
switch movedir
    case 1
        cc = cc+1;
    case 2
        cr = cr+1;
    case 3
        cc = cc-1;
    case 4
        cr = cr-1;
end
c(cr,cc) = boxnumber;
movelist(end+1,:) = [boxnumber,movedir];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function mv = solver3(ai,af,w,states,optscore)
global mv a airow aicol afrow afcol rowDis colDis I J b m n wn Dperfect
mv = [];
aiMap = ai>0;
a = ai;
[m,n] = size(aiMap);
aiBlock = ai(aiMap);
nBlocks = length(aiBlock);
[aiOrder, aiPos] = sort(aiBlock);
[airow,aicol] = find(aiMap);
airow = airow(aiPos);
aicol = aicol(aiPos);
w0 = w;
w = w(aiPos);
wn = w;
afMap = af>0;
[afOrder, afPos ] = sort( af(afMap) );
[afrow,afcol] = find(afMap);
afrow = afrow(afPos);
afcol = afcol(afPos);
rowDis = airow-afrow;
colDis = aicol-afcol;
[nw,nd]=sort(-w);
I = [0  1  0 -1];
J = [1  0 -1  0];
recurP = [1:4; 3 4 1 2; 1:4];
iter = 0;
while (iter<2) && (( sum(abs(rowDis) + abs(colDis))>0 ) > 0)
    iter = iter + 1;
    for irr = 1:nBlocks
        ir = nd(irr);
        priority = 0;
        len=0;
        iterr = 0;
        while (iterr < 10) && (abs(rowDis(ir))+abs(colDis(ir)) > 0)
            iterr = iterr+1;
            b=ai*0;
            x = airow(ir);
            y = aicol(ir);
            b(x,y) = ir;
            if ~chainMV( ir,priority )
                break;
            end;
            len = len+1;
            if len>3
                if all( mv(end:-1:end-2,1) == ir ) && any( all( mv(end:-1:end-2,[2 2 2 2]) == recurP ) )
                    priority = Inf;
                    mv(end-1:end,:) = [];
                end;
            end
        end
    end
end
res = sum(abs(rowDis) + abs(colDis));
if res > 0
    rand('state',states);mv1=[mv;Faster10IntReps2(a,af,w0)];score=sum(w(mv1(:,1)));
    if ((length(mv1)-Dperfect)>1)&&(score>4450);rand('state',states*2);mv2=[mv;Faster10IntReps2(a,af,w0)];score1=sum(w(mv2(:,1)));if score1<score;mv1=mv2;end;end;
    mv=mv1;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function isMovable = chainMV( ir , priority)
global mv a airow aicol rowDis colDis I J b m n wn
isMovable = 0;
x = airow(ir);
y = aicol(ir);
disr = rowDis(ir);
disc = colDis(ir);
if (priority>wn(ir))||(abs(disr)+abs(disc)>0)
    mvDirects = ( disr * I + disc * J );
    [DNC, mvInd] = sort(mvDirects);
    for k = 1:2
        i = I(mvInd(k));
        j = J(mvInd(k));
        nx = x + i;
        ny = y + j;
        succMv = 0;
        if (nx>0) && (nx<=m) && (ny>0) && (ny<=n)
            if a(nx,ny) == 0
                succMv = 1;
            else
                if b(nx,ny) == 0
                    b(nx,ny) = 1;
                    succMv = chainMV( a(nx,ny) , priority );
                else
                    b(nx,ny) = 0;
                end;
            end;
        end;
        if succMv == 1
            airow(ir) = nx;
            aicol(ir) = ny;
            rowDis(ir) = rowDis(ir) + I(mvInd(k));
            colDis(ir) = colDis(ir) + J(mvInd(k));
            a(x,y) = 0;
            a(nx,ny) = ir;
            mv(end+1,:) = [ir,mvInd(k)];
            isMovable = 1;
            break;
        end;
    end;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [tf] = ismember1(a,s)
numelA = numel(a);
numelS = numel(s);
if numelA == 0 || numelS <= 1
    if (numelA == 0 || numelS == 0)
        tf = false(size(a));
        return
    elseif numelS == 1
        tf = (a == s);
        return
    end
else
    tf=false(1,numelA);
    for i=1:numelA;
        tf(i)=any(a(i)==s);
    end;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [tf] = ismember2(a,s)
numelA = numel(a);
numelS = numel(s);
if numelA == 0 || numelS <= 1
    if (numelA == 0 || numelS == 0)
        tf = false(size(a));
        return
    elseif numelS == 1
        tf = (a == s);
        return
    end
else
    tf = false(size(a));
    for i=1:numelA
        found = (a(i)==s(:));
        if ~any(found)
            tf(i) = 1;
        end
    end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [c] = setdiff(a,b)
c = unique(a(ismember2(a(:),b(:))));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [b] = unique(a)
numelA = numel(a);
if numelA<2
    b = a;
else
    b = sort(a);
    db = diff(b);
    d = db ~= 0;
    d(numelA) = true;
    b = b(d);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function ndx = sub2ind(siz,varargin)
siz = [siz ones(1,nargin-length(siz)-1)];
mt = cellfun('isempty',varargin);
if any(mt)
    ndx = zeros(~mt);
    return;
end
k = [1 cumprod(siz(1:end-1))];
ndx = 1;
for i = 1:length(siz),
    v = varargin{i};
    ndx = ndx + (v-1)*k(i);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function p = randperm(n)
[DNC,p] = sort(rand(1,n));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function P = perms(V)
V = V(:).';
n = length(V);
if n <= 1, P = V;
    return;
end
q = perms(1:n-1);
m = size(q,1);
P = zeros(n*m,n);
P(1:m,:) = [n * ones(m,1) q];
for i = n-1:-1:1
    t = q;
    t(t == i) = n;
    P((n-i)*m+1:(n-i+1)*m,:) = [i*ones(m,1) t];
end
P = V(P);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function mv = Arrange6(ai,af,w)
nBlocks = max(ai(:));
[m,n] = size(ai);
ftot=m*n;
steps=zeros(ftot,4);
steps(1,:)=[0 0 m 1 ];
steps(m,:)=[0 -1 m 0 ];
steps(ftot-m+1,:)=[-m 0 0 1 ];
steps(ftot,:)=[-m -1 0 0 ];
for ci=2:m-1
    steps(ci,:)=[0 -1 m 1 ];
end
for ci=ftot-m+2:ftot-1
    steps(ci,:)=[-m -1 0 1 ];
end
for col=m+1:m:ftot-m
    steps(col,:)=[-m 0 m 1];
    steps(col+m-1,:)=[-m -1 m 0];
    for row=1:m-2
        steps(col+row,:)=[-m -1 m 1];
    end
end
I = [0  1  0 -1];
J = [1  0 -1  0];
a = ai;
mv = [];
ww=w;
success=1;
uas=zeros(m,n);
initialmode=1;
while ~isequal(af,a)
    numw=length(w);
    wwb=1:length(w);
    wwbi=a(a==af);
    wwbi(wwbi==0)=[];
    wwb(wwbi)=[];
    [tmp,wwbi]=sort(-w(wwb));
    wwb=wwb(wwbi);
    if ( success==0 )
        fiter=true;
    else
        fiter=false;
    end
    success=0;
    while ( wwb )
        blk=wwb(1);
        wwb(1)=[];
        ci=find(af(:)==blk);
        if ( a(ci)>0 && ~fiter && initialmode ~=2 )
            continue;
        end
        [smv,fc,a]=findshortestpath(blk,a,af,w,m,n,1,[],steps);
        if ( fc==0 )
            mv=[mv;smv];
            ci=find(a(:)==blk);
            a(ci)=0;
            ci=find(af(:)==blk);
            a(ci)=blk;
            ww(blk)=0;
            success=1;
        elseif (initialmode ~=1)
            moves=[m 1 -m -1 ];
            cpos=1;
            ci=find(a(:)==blk);
            a(ci)=0;
            chmv=[];
            while ( cpos<=size(smv,1) )
                while (cpos<=size(smv,1) && a(ci+moves(smv(cpos,2)))==0 )
                    if ( initialmode )
                        if af(ci+moves(smv(cpos,2)))>0
                            break;
                        end
                    end
                    ci=ci+moves(smv(cpos,2));
                    mv=[mv;smv(cpos,:)];
                    cpos=cpos+1;
                end
                if ( initialmode )
                    break;
                end
                if ( cpos>size(smv,1))
                    continue;
                end
                upos=cpos;
                ua=uas;
                uci=ci;
                ua(uci)=1;
                while (upos<=size(smv,1) )
                    uci=uci+moves(smv(upos,2));
                    upos=upos+1;
                    ua(uci)=1;
                end
                [hmv,fc,a]=findshortestpath(a(ci+moves(smv(cpos,2))),a,af,w,m,n,2,ua,steps);
                if ( isempty(hmv) )
                    ua=zeros(m,n);
                    ua(ci)=1;
                    ua(ci+moves(smv(cpos,2)))=1;
                    [hmv,fc,a]=findshortestpath(a(ci+moves(smv(cpos,2))),a,af,w,m,n,2,ua,steps);
                end
                mv=[mv;hmv];
                chmv=[chmv;hmv];
                hpos=1;
                while (hpos<=size(hmv,1) )
                    hci=find(a(:)==hmv(hpos,1));
                    a(hci)=0;
                    hci=hci+moves(hmv(hpos,2));
                    a(hci)=hmv(hpos,1);
                    hpos=hpos+1;
                end
            end
            a(ci)=blk;
            chmv=chmv(end:-1:1,:);
            hpos=1;
            while (hpos<=size(chmv,1) )
                chmv(hpos,2)=mod(chmv(hpos,2)+2,4);
                if ( chmv(hpos,2)==0 )
                    chmv(hpos,2)=4;
                end
                hci=find(a(:)==chmv(hpos,1));
                hcin=hci+moves(chmv(hpos,2));
                if ( a(hcin)==0 && a(hci)==af(hcin))
                    a(hci)=0;
                    a(hcin)=chmv(hpos,1);
                else
                    uas(ci)=1;
                    chmv=chmv(1:hpos-1,:);
                    break;
                end
                hpos=hpos+1;
            end
            mv=[mv;chmv];
        end
    end
    if ( ~success && initialmode==1 )
        initialmode=2;
        success=1;
    end
    if ( ~success && initialmode==2 )
        initialmode=0;
        success=1;
    end
end
while ~isequal(af,a)
    bid = ceil(rand*nBlocks);
    [i,j] = find(a==bid);
    r = ceil(rand*4);
    ni = i + I(r);
    nj = j + J(r);
    if (ni<1) || (ni>m) || (nj<1) || (nj>n)
        continue
    end
    if a(ni,nj)>0
        continue
    end
    [ti,tj] = find(af==bid);
    if (i^2+j^2-ni^2-nj^2<2*(ti*(i-ni)+tj*(j-nj))) && (rand>0.051)
        continue
    end
    a(ni,nj) = bid;
    a(i,j) = 0;
    mv(end+1,[1 2]) = [bid r];
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [smv,fc,a]=findshortestpath(blk,a,af,w,m,n,mode,ua,steps)
smv=[]; fc=0;
is=zeros(100,1);
isi=1;
ise=1;
is(1) = find(a(:)==blk);
ca=zeros(m,n);
ca(is(1))=1;
cm=zeros(m,n);
om=zeros(m,n);
helpw=[0;w];
while ( isi<=ise )
    ci=is(isi);
    cv=ca(ci);
    t=ci+steps(ci,:);
    if ( mode==2 )
        t(ua(t)==1)=ci;
    end
    for ind=1:4
        mpenalty=0;
        if ( a(t(ind))>0 )
            mpenalty=2*helpw(a(t(ind))+1);
        end
        if ca(t(ind))==0
            ca(t(ind))=cv+1;
            if ( mode==1 )
                cm(t(ind))=cm(ci)+mpenalty+w(blk)+0.1*(a(t(ind))>0);
            else
                cm(t(ind))=cm(ci)+2*helpw(a(t(ind))+1);
            end
            om(t(ind))=om(ci)+(a(t(ind))>0);
            if ( mode==1 || a(t(ind))>0 )
                ise=ise+1;
                is(ise)=t(ind);
            end
        else
            if ( cm(ci)+mpenalty+w(blk)<cm(t(ind)) )
                ca(t(ind))=ca(ci)+1;
                cm(t(ind))=cm(ci)+mpenalty+w(blk);
                om(t(ind))=om(ci)+(a(t(ind))>0);
                if ( mode==1 || a(t(ind))>0 )
                    ise=ise+1;
                    is(ise)=t(ind);
                end
            end
        end
    end
    isi=isi+1;
end
if ( mode==1 )
    ci=find(af(:)==blk);
else
    cm(ca==0)=Inf;
    ui=find(a==0);
    [tmp,mi]=min(cm(ui));
    ci=ui(mi);
end
cv=ca(ci);
if ( cv==0 )
    return;
end
tmv=[];
while ( cv>1 )
    t=ci+steps(ci,:);
    pi=find(ca(t)==cv-1);
    [tmp,ni]=min(cm(t(pi)));
    ci=t(pi(ni));
    if ( mode==1 )
        tmv(end+1,[1 2]) = [blk pi(ni)];
    else
        tmv(end+1,[1 2]) = [a(ci) pi(ni)];
    end
    cv=cv-1;
end
if ( mode==1 )
    smv=[tmv(end:-1:1,:)];
    fc=om(find(af(:)==blk));
else
    smv=tmv;
    fc=0;
end