# Diffing "New 1.15" and "New 1.1"

 Title: New 1.15 New 1.1 Author: the cyclist the cyclist Submitted: 2004-11-09 21:42:55 UTC 2004-11-09 21:47:52 UTC Status: Passed Passed Score: 41.5228 41.5448 Result: 40679 40679 CPU Time: 65.1477 65.4055 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 movesTLL79 = TLL79(A,B,w0,optmove,[ipos1 ipos2],[fpos1 fpos2],optscore); scoreTLL79=sum(w0(movesTLL79(:,1))); if (scoreTLL79-optscore)>0; movesA5 = Arrange6(A, B, w0); scoreA5=sum(w0(movesA5(:,1))); if scoreTLL79= 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); if ok && flag==0 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)]; res1 = sum(w0(moves(:,1))); res2 = sum(w0(mov(:,1))); if res20)*(1:n)' sum(mov,2)]; 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)'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) && row0 && 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) && col0 && 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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function mv = TLL79(Ai,Af,w,optmove,Ci,Cf,optscore) dist = optscore; n_blk = length(w); I = [0 1 0 -1]; J = [1 0 -1 0]; mv = solv(Ai,Af,w,optmove,optscore); sc = sum(w(mv(:,1))); mv_len = size(mv,1); if mv_len==optmove;return;end; if ((sc-optscore)<20)||((mv_len-optmove)<2);return;end num_fail = 0; max_try = 75; 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), 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 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, if (mv(j,1) == mv(j+3,1)) && (abs(mv(j,2) - mv(j+3,2)) == 2) b = mv(j,1); sit = 0; if (mv(j,1) == mv(j+1,1)) && (mv(j,1) == mv(j+2,1)) && (mv(j+1,2) == mv(j+2,2)), b1 = A(C(b,1) + I(mv(j+1,2)),C(b,2) + J(mv(j+1,2))); sit = 1; else if (mv(j,1) == mv(j+1,1)) && (mv(j,1) ~= mv(j+2,1)) && (abs(mv(j+1,2) - mv(j+2,2)) == 2), b1 = mv(j+2,1); sit = 1; else if (mv(j,1) ~= mv(j+1,1)) && (mv(j,1) == mv(j+2,1)) && (abs(mv(j+1,2) - mv(j+2,2)) == 2), b1 = mv(j+1,1); sit = 1; else if (mv(j,1) == mv(j+1,1)) && (mv(j,1) ~= mv(j+2,1)), b1 = mv(j+2,1); sit = 3; else if (mv(j,1) ~= mv(j+1,1)) && (mv(j,1) == mv(j+2,1)), b1 = mv(j+1,1); sit = 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 else if sit ~= 0, if A(C(b1,1) + I(mv(j+sit-1,2)),C(b1,2) + J(mv(j+sit-1,2))) == 0, sc = sc - w(b) - w(b1); mv(j:j+1,:) = mv([j+sit-1 j+4-sit],:); mv = mv([1:j+1,j+4:end],:); mv_len = mv_len - 2; if sc == dist, return end end end end end end 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 = solv(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 score120)||((length(move)-optmove)>5); move1=solver3(aInit,aFinal,wt,1111,optscore); if ( ~isempty(move1) ) isPerfect=length(move1)==Dperfect; score1=sum(wt(move1(:,1))); if score1bscore ) 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] = movefrompos(hv, [hvix hviy], [hvfx hvfy], aInit, aFinal, wtinit, 1, dist+6); 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] = movefrompos(item, pinit, pfin, curpos, finpos, wt, strategy, recur) 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] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur); 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] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur); 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 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] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur); 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 0 && curpos(pinit(1)+dirx, pinit(2)) > 0 [move1 cost1 curposnew1] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur); if cost1 0 [move1 cost1 curposnew1] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur); if cost1 0 [move1 cost1 curposnew1] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur); if cost1 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] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0) && all(pinit+mv2 <= sz) && ~curpos(pinit(1)+mv2(1),pinit(2)+mv2(2)) [move1 cost1 curposnew1] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0) && all(pinit+mv3 <= sz) && ~curpos(pinit(1)+mv3(1),pinit(2)+mv3(2)) [move1 cost1 curposnew1] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0) && all(pinit+mv1 <= sz) && curpos(pinit(1)+mv1(1),pinit(2)+mv1(2)) > 0 [move1 cost1 curposnew1] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0) && all(pinit+mv2 <= sz) && curpos(pinit(1)+mv2(1),pinit(2)+mv2(2)) > 0 [move1 cost1 curposnew1] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0) && all(pinit+mv3 <= sz) && curpos(pinit(1)+mv3(1),pinit(2)+mv3(2)) > 0 [move1 cost1 curposnew1] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 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] = onemove(item, pinit, tmppos2-pinit, pfin, curpos, finpos, wt, strategy, -1); if ~isinf(costnew3) [move4 costnew4 curpostmp] = onemove(item, tmppos2, tmppos4-tmppos2, pfin, curpostmp, finpos, wt, strategy, -1); if ~isinf(costnew4) [move5 costnew5 curpostmp] = movefrompos(item, tmppos4, pfin, curpostmp, finpos, wt, -strategy, recur-1); 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] = movefrompos(newitem, newpos, pfin2, curpos, finpos, wt, strategy, -1); 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] = movefrompos(newitem, newpos, newpos+mv1, curpos, finpos, wt, strategy, -1); 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] = movefrompos(newitem, newpos, newpos+mv2, curpos, finpos, wt, strategy, -1); 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] = movefrompos(newitem, newpos, newpos+mv3, curpos, finpos, wt, strategy, -1); 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] = movefrompos(newitem, newpos, newpos+mv1, curpos, finpos, wt, strategy, -1); case 2, [move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv2, curpos, finpos, wt, strategy, -1); case 3, [move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv3, curpos, finpos, wt, strategy, -1); 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] = movefrompos(item, pinit+movedir, pfin, curpos, finpos, wt, strategy, recur-1); else [move2 costnew curposnew] = movefrompos(item, pinit+movedir, pfin, curpos, finpos, wt, strategy, 0); 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 nmv01&&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 score1r2 d_r=-1; elseif r1c2 d_c=-1; elseif c1 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 score0, 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 score1wn(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)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```