function mv = solver(Ai,Af,w)
n_blk = length(w);
[n_row,n_col] = size(Ai);
% 1 RIGHT, 2 DOWN, 3 LEFT, 4 UP
I = [0 1 0 -1];
J = [1 0 -1 0];
Ci = zeros(n_blk,2);
Cf = Ci;
for row = 1:n_row,
for col = 1:n_col,
b = Ai(row,col);
if b > 0,
Ci(b,:) = [row,col];
end
b = Af(row,col);
if b > 0,
Cf(b,:) = [row,col];
end
end
end
C = Ci;
A = Ai;
mv = zeros(0,2);
[sw,ind] = sort(w);
ind = ind';
Def = sum(sum(abs(Cf - C)));
MDef = Def;
while 1,
n_move = 0;
for b = ind,
while 1,
dir = sign(Cf(b,:) - C(b,:));
if dir == [0 0],
break
end
r = C(b,1);
c = C(b,2);
if rand > 0.5,
if (dir(1) ~= 0) && (A(r+dir(1),c) == 0),
dir = 3 - dir(1);
else
if (dir(2) ~= 0) && (A(r,c+dir(2)) == 0),
dir = 2 - dir(2);
else
break
end
end
else
if (dir(2) ~= 0) && (A(r,c+dir(2)) == 0),
dir = 2 - dir(2);
else
if (dir(1) ~= 0) && (A(r+dir(1),c) == 0),
dir = 3 - dir(1);
else
break
end
end
end
n_move = n_move + 1;
nr = r + I(dir);
nc = c + J(dir);
A(nr,nc) = b;
A(r,c) = 0;
C(b,:) = [nr,nc];
mv = [mv;[b,dir]];
end
end
if n_move == 0,
MDef = Def;
MA = A;
MC = C;
Mmv = mv;
for j = 1:n_blk,
b = ceil(rand*n_blk);
r = C(b,1);
c = C(b,2);
dir = ceil(rand*4);
nr = r + I(dir);
nc = c + J(dir);
if (nr >= 1) && (nr <= n_row) && (nc >= 1) && (nc <= n_col),
if A(nr,nc) == 0,
A(nr,nc) = b;
A(r,c) = 0;
C(b,:) = [nr,nc];
mv = [mv;[b,dir]];
end
end
end
else
Def = sum(sum(abs(Cf - C)));
if Def == 0,
break
end
if Def >= MDef,
A = MA;
C = MC;
mv = Mmv;
Def = MDef;
end
end
end
|
