| Code: | function W = solver(B)
W1 = solver1(B,0);
W2 = solver1(B,2);
%W3 = solver1(B,1);
W3 = zeros(0,4);
g1 = grade(B,W1);
g2 = grade(B,W2);
g3 = grade(B,W3);
if g1 < g2 && g1 < g3;
W = W1;
elseif g2 < g3
W = W2;
else
W = W3;
end
function W = solver1(B,mode)
W = zeros(0,4);
%return
A = makeA(B);
n = numel(B);
[nr,nc] = size(B);
pinIds = unique(B(B>0));
pinGains = zeros(numel(pinIds),1);
pinVars = zeros(numel(pinIds),1);
for i=1:numel(pinIds)
pin = pinIds(i);
gain = sum(B(B==pin));
pinGains(i) = gain;
[vr,vc] = find(B==pin);
pinVars(i) = var(vr)+var(vc);
end
%[gains,idx] = sort(pinGains,1,'descend');
[gains,idx] = sort(pinGains./(pinVars+0.001),1,'descend');
%idx = randperm(numel(pinIds));
pinIds = pinIds(idx);
pinGains = pinGains(idx);
Aold = A;
bridges = zeros(n,1);
newBridges = bridges;
for i = 1:numel(pinIds)
pin = pinIds(i);
gain = pinGains(i);
D = B;
D(B==pin) = 0;
A(find(D),:) = inf;
A(:,find(D)) = inf;
j = find(B==pin);
if mode==0 || mode == 1
[jr,jc] = ind2sub(size(B),j);
jmr = median(jr);
jmc = median(jc);
di = abs(jr-jmr) + abs(jc-jmc);
[dummy,jidx] = sort(di);
j = j(jidx);
else
j = j(randperm(numel(j)));
end
tar = zeros(n,1);
tar(j(1)) = 1;
for i = 2:numel(j)
v = j(i);
vl = shortest_path(v,tar,A,bridges,gain);
[r,c] = ind2sub(size(B),vl);
W = [W; [r(1:end-1)' c(1:end-1)' r(2:end)' c(2:end)']];
gain = gain - numel(vl) + 1;
% update bridges
for k = 2:numel(vl)-1
if bridges(vl(k))
W = [W; r(k)' c(k)' r(k)' c(k)'];
gain = gain - 25;
end
newBridges(vl(k)) = 1;
end
% update A and Aold
for k = 2:numel(vl)
%A(vl(k-1),vl(k)) = inf;
%A(vl(k),vl(k-1)) = inf;
Aold(vl(k-1),vl(k)) = inf;
Aold(vl(k),vl(k-1)) = inf;
if k ~= numel(vl)
% corner
if diff(diff(vl(k-1:k+1))) ~= 0
if vl(k) > 1
Aold(vl(k),vl(k)-1) = inf;
Aold(vl(k)-1,vl(k)) = inf;
end
if vl(k) < n
Aold(vl(k),vl(k)+1) = inf;
Aold(vl(k)+1,vl(k)) = inf;
end
if vl(k)-nr >= 1
Aold(vl(k),vl(k)-nr) = inf;
Aold(vl(k)-nr,vl(k)) = inf;
end
if vl(k)+nr <= n
Aold(vl(k),vl(k)+nr) = inf;
Aold(vl(k)+nr,vl(k)) = inf;
end
end
end
end
tar(vl) = 1;
%reshape(tar,size(B))
end
bridges = newBridges;
A = Aold;
end
function A = makeA(B)
n = numel(B);
A = inf*ones(n);
sz = size(B);
nr = sz(1);
nc = sz(2);
for v = 1:n
[r,c] = ind2sub(sz,v);
if r > 1
A(v,v-1) = 1;
A(v-1,v) = 1;
end
if r < sz(1)
A(v,v+1) = 1;
A(v+1,v) = 1;
end
if c > 1
A(v,v-nr) = 1;
A(v-nr,v) = 1;
end
if c < sz(2)
A(v,v+nr) = 1;
A(v+nr,v) = 1;
end
end
function vl = shortest_path(src,target,A,bridges,limit)
n = size(A,1);
dist = inf*ones(n,1);
prev = zeros(n,1);
dist(src) = 0;
visit = ones(n,1);
vl = [];
while 1
%j = min(dist.*visit);
[j,u] = min(dist.*visit);
if j >= limit*.3
break
end
%us = find(dist == j);
%u = us(ceil(numel(us)*rand(1)));
if target(u)
while u ~= src
vl = [vl u];
u = prev(u);
end
vl = [vl src];
break
end
visit(u) = inf;
alt = dist(u)+A(:,u)+bridges*25;
j = find(alt < dist);
prev(j) = u;
dist(j) = alt(j);
%ind2sub([7,9],u)
%reshape(dist,7,9)
end
%function [score W Wlab C B] = concom(B,W)
function score = grade(B,W)
% CONCOM Finds connected components and scores the solution
% Inputs:
% B - Board, a matrix with component ID's, 0's means no component.
% W - Wiring, a matrix (nx4) matrix with wires, invalid wires are
% ignored but charged into the score.
%
% The MATLAB Contest Team
% April, 2008
[ro,co] = size(B);
dW = abs(W(:,[1 2])-W(:,[3 4]));
% Extract bridges from W
Bridges = W(~any(dW,2),[1 2]);
% Calculate the wiring cost: (Bridge cost is 25, but 1 is alredy counted in W
wiringCost = size(W,1) + 24 * size(Bridges,1);
% Keep only valid wires in W
W = W(all(W(:,[1 3])>0 & W(:,[1 3])<=ro & W(:,[2 4])>0 & W(:,[2 4])<=co,2) & (sum(dW,2)==1),:);
% Change wiring coordinates to linear indexing:
V = sort([sub2ind([ro,co],W(:,1),W(:,2)) sub2ind([ro,co],W(:,3),W(:,4))],2);
BridgeIdx = sub2ind([ro,co],Bridges(:,1),Bridges(:,2));
% Create a graph (E (edges)):
E = zeros(size(V));
[node2idx,dummy,E(:)]= unique(V);
nN = numel(node2idx);
idx2node(node2idx) = 1:nN;
% Build an adjacency list for edges:
A = zeros(nN,4); % [v ^ > <]
for i = 1:nN
[j,k] = find(node2idx(i)==V);
A(i,2*(diff(V(j,:),[],2)>1)+k) = sum(E(j,:),2)-i;
end
% Keep bridges that exist over wires and are not over components
BridgeIdx = intersect(BridgeIdx,V(:));
BridgeIdx = BridgeIdx(B(BridgeIdx)==0);
% Remove bridges that do not separate vertical and horizontal wires
BridgeIdx = BridgeIdx(any(A(idx2node(BridgeIdx),[1 2]),2) & any(A(idx2node(BridgeIdx),[3 4]),2));
% Add extra nodes where Bridges exist:
A = [A;zeros(numel(BridgeIdx),4)];
node2idx = [node2idx; BridgeIdx];
j = nN;
for i = idx2node(BridgeIdx)
j = j+1;
A(j,:) = A(i,:);
if A(i,3)
A(A(i,3),4)=j;
end
if A(i,4)
A(A(i,4),3)=j;
end
A(i,[3 4]) = 0;
A(j,[1 2]) = 0;
end
% Label nodes
labels = zeros(size(A,1),1);
tv = find(~labels,1);
cc = 1;
while ~isempty(tv)
while ~isempty(tv)
labels(tv) = cc;
tv = nonzeros(A(tv,:));
tv = tv(labels(tv) == 0);
end
cc = cc+1;
tv = find(~labels,1);
end
% Copy labels to a board
C = zeros(ro,co);
C(node2idx) = labels;
H = ~C & B>0;
C(H) = cc+(0:nnz(H)-1);
C(BridgeIdx)=-1;
% Label wires
Wlab = zeros(size(V,1),1);
for i=1:size(A,1)
for j = 1:4
if A(i,j)
Wlab(V(:,1)==node2idx(i) & V(:,2)==node2idx(A(i,j))) = labels(i);
end
end
end
% find short-circuited components and remove them:
P = unique(nonzeros(B));
for i = 1:cc-1
p = unique(nonzeros(B(C==i)));
if numel(p)>1
P = setdiff(P,p);
end
end
% consider the largest island for every non-short-circuited component and
% remove it from the board:
for i = 1:numel(P)
[sz,ch] = max(sparse(C(B==P(i)),1,1));
if sz>1
B(C==ch)=0;
end
end
score = sum(nonzeros(B)) + wiringCost;
|