Winner GUO (asdf1)

2004-11-10 09:00:00 UTC

# KickOff10

by Yi Cao

Status: Passed
Results: 1227081
CPU Time: 75.5951
Score: 1229.48
Submitted at: 2004-11-03 20:15:47 UTC
Scored at: 2004-11-04 05:30:55 UTC

Current Rank: 1194th
Basis for: KickOff10test (diff)

Code
function mv = solver(ai,af,w)

rand('state',10);
nBlocks = length(w);
[m,n] = size(ai);
[Ii,Ji,si]=find(sparse(ai));
[si,k]=sort(si);
Ii=Ii(k);
Ji=Ji(k);
[If,Jf,sf]=find(sparse(af));
[sf,k]=sort(sf);
If=If(k);
Jf=Jf(k);
mB=sum(Ii-If | Ji-Jf);

% Make increment tables
% N=1, E=2, S=3, W=4
I = [0  1  0 -1];
J = [1  0 -1  0];

mv = [];
while mB

% Pick a random block
bid = ceil(rand*nBlocks);
i=Ii(bid);
j=Ji(bid);

% Move it in a random direction
ni = i + I;
nj = j + J;

% Is it a legal move? Check edges
K = find((ni<1) | (ni>m) | (nj<1) | (nj>n));

% Is it a legal move? Check for collision
for k=1:length(ni);
if any(K==k)
continue
end
if any(Ii==ni(k) & Ji==nj(k))
K=[K k];
end
end
r=1:4;
r(K)=[];
ni(K)=[];
nj(K)=[];
if isempty(ni)
continue
end
mn=ceil(rand*length(r));
ni=ni(mn);
nj=nj(mn);
r=r(mn);

% Check distance
% Get the target location
ti=If(bid);
tj=Jf(bid);
d = abs(ti-i) + abs(tj-j);
dn = abs(ti-ni) + abs(tj-nj);
% Have we moved closer to the target location?
if (d<dn) && (rand>0.05)
continue
end

% Move the block
Ii(bid)=ni;
Ji(bid)=nj;

% Record the move
mv(end+1,[1 2]) = [bid r];
mB=sum(Ii-If | Ji-Jf);

end