function CBA = solver(BAA), QDA = rand(7,1);NCA = 3;FAA = BAA;[ABA BAA] = WCA(FAA,1);DBA = XCA(FAA,BAA,ABA,NCA,1);
OBA = 3*2;

GDA = rand(17,1);

WAA = QCA(FAA,DBA);VAA = WAA;CBA = DBA;
if VAA > 0
EBA = XCA(FAA,BAA,ABA,NCA,2);XAA = QCA(FAA,EBA);
if XAA < VAA
CBA = EBA;VAA = XAA;
end
end
if VAA > 0
[ABA BAA] = WCA(FAA,3);FBA = XCA(FAA,BAA,ABA,NCA,3);YAA = QCA(FAA,FBA);
if YAA < VAA
CBA = FBA;VAA = YAA;
end
end
if VAA > 0
GBA = XCA(FAA,BAA,ABA,NCA,4);ZAA = QCA(FAA,GBA);
if ZAA < VAA
CBA = GBA;
end
end; if ~isempty(find(CBA==0,1,'first'));CBA = CBA(1:find(CBA==0,1,'first')-1,:);end;
end
function JDA = QCA(BAA,CBA), [DDA,WBA] = size(BAA);ECA = abs(CBA(:,[1 2])-CBA(:,[3 4]));HAA = CBA(~any(ECA,2),[1 2]);RDA = size(CBA,1) + 24 * size(HAA,1);
CBA = CBA(all(CBA(:,[1 3])>0 & CBA(:,[1 3])<=DDA & CBA(:,[2 4])>0 & CBA(:,[2 4])<=WBA,2) & (sum(ECA,2)==1),:);BBA = sort([(CBA(:,2)-1)*DDA+CBA(:,1) (CBA(:,4)-1)*DDA+CBA(:,3)],2);
GAA = (HAA(:,2)-1)*DDA+HAA(:,1);JAA = zeros(size(BBA));[SCA,GCA,JAA(:)]= unique(BBA);RCA = numel(SCA);
HCA(SCA) = 1:RCA;AAA = zeros(RCA,4);
for i = 1:RCA
[j,JCA] = find(SCA(i)==BBA);
AAA(i,2*(diff(BBA(j,:),[],2)>1)+JCA) = sum(JAA(j,:),2)-i;
end
GAA = intersect(GAA,BBA(:));GAA = GAA(BAA(GAA)==0);GAA = GAA(any(AAA(HCA(GAA),[1 2]),2) & any(AAA(HCA(GAA),[3 4]),2));
AAA = [AAA;zeros(numel(GAA),4)];SCA = [SCA; GAA];j = RCA;
for i = HCA(GAA)
j = j+1;AAA(j,:) = AAA(i,:);
if AAA(i,3)
AAA(AAA(i,3),4)=j;
end
if AAA(i,4)
AAA(AAA(i,4),3)=j;
end
AAA(i,[3 4]) = 0;AAA(j,[1 2]) = 0;
end
MCA = zeros(size(AAA,1),1);PDA = find(~MCA,1);TBA = 1;
while ~isempty(PDA)
while ~isempty(PDA)
MCA(PDA) = TBA;PDA = nonzeros(AAA(PDA,:));PDA = PDA(MCA(PDA) == 0);
end
TBA = TBA+1;PDA = find(~MCA,1);
end
IAA = zeros(DDA,WBA);IAA(SCA) = MCA;KAA = ~IAA & BAA>0;IAA(KAA) = TBA+(0:nnz(KAA)-1);IAA(GAA)=-1;HBA = zeros(size(BBA,1),1);
for i=1:size(AAA,1)
for j = 1:4
if AAA(i,j)
HBA(BBA(:,1)==SCA(i) & BBA(:,2)==SCA(AAA(i,j))) = MCA(i);
end
end
end
SAA = unique(nonzeros(BAA));
for i = 1:TBA-1
UCA = unique(nonzeros(BAA(IAA==i)));
if numel(UCA)>1
SAA = setdiff(SAA,UCA);
end
end
for i = 1:numel(SAA)
[LDA,UBA] = max(sparse(IAA(BAA==SAA(i)),1,1));
if LDA>1
BAA(IAA==UBA)=0;
end
end
JDA = sum(nonzeros(BAA)) + RDA;
end
function [ZCA JCA] = NBA(BAA)
YCA = sort(BAA(BAA>0),'descend');
TCA = size(YCA,1);
if TCA < 1
ZCA = [];JCA = 0;return
end
ZCA = zeros(TCA,3);ZCA(1,1) = YCA(1);JCA = 1;BCA = 1;
for i = 2:TCA
if YCA(i) == ZCA(JCA,1)
BCA = BCA + 1;else ZCA(JCA,2) = BCA;JCA = JCA + 1;BCA = 1;ZCA(JCA,1) = YCA(i);
end
end
ZCA(JCA,2) = BCA;ZCA = ZCA(1:JCA,:);
for i = 1:JCA
if ZCA(i,2) >= 2
UCA = ZCA(i,1);[EDA XBA] = find(BAA == UCA);DCA = 0;
for j = 2:size(EDA,1);
DCA = DCA + abs(EDA(j)-EDA(j-1)) + abs(XBA(j)-XBA(j-1));
end
ZCA(i,3) = ZCA(i,2)*UCA - DCA;
end
end
end
function [CBA BAA] = WCA(BAA,HDA), CCA = 9;[ZCA JCA] = NBA(BAA);CBA = zeros(size(BAA,1)*size(BAA,2),4);
if HDA <= 2
IBA = 2 + floor(rand*2);
[IDA ICA] = sort(ZCA(:,IBA),'descend');
else
[IDA ICA] = sort(ZCA(:,1),'descend');
end
ZCA = ZCA(ICA,:);
for i = 1:JCA
if ZCA(i,2) >= 2
UCA = ZCA(i,1);[EDA XBA] = find(BAA == UCA);LAA = size(EDA,1);OAA = LAA*(LAA-1)/2;dist = zeros(OAA,3);SDA = 0;
for KBA = 1:LAA
for PBA = (KBA+1):LAA
SDA = SDA + 1;dist(SDA,1) = KBA;dist(SDA,2) = PBA;dist(SDA,3) = abs(EDA(KBA)-EDA(PBA)) + abs(XBA(KBA)-XBA(PBA));
end
end
[DCA ICA] = sort(dist(:,3));dist = dist(ICA,:);TCA = 0;
for SDA = 1:OAA
if dist(SDA,3) > CCA+1
break
end
KBA = dist(SDA,1);PBA = dist(SDA,2);path = ZBA(BAA,[EDA(KBA); EDA(PBA)], [XBA(KBA); XBA(PBA)], -UCA, 2*UCA);
if size(path,1) > 0
CBA(find(CBA==0,1,'first'):find(CBA==0,1,'first')+size(path,1)-1,:) = path;BAA = MBA(BAA,path,-UCA);TCA = 2;edit = [1:(KBA-1) (KBA+1):(PBA-1) (PBA+1):LAA];EDA = [EDA(KBA); EDA(PBA); EDA(edit)];
XBA = [XBA(KBA); XBA(PBA); XBA(edit)];
break
else
end
end
if TCA < 2
continue
end
for j = 3:LAA
[FDA YBA] = find(BAA == -UCA);RAA = size(FDA,1);OAA = RAA * (LAA - TCA);dist = zeros(OAA,3);SDA = 0;
for KBA = 1:RAA
for PBA = (TCA+1):LAA
SDA = SDA + 1;dist(SDA,1) = KBA;dist(SDA,2) = PBA;dist(SDA,3) = abs(FDA(KBA)-EDA(PBA)) + abs(YBA(KBA)-XBA(PBA));
end
end

[DCA ICA] = sort(dist(:,3));dist = dist(ICA,:);ACA = false;
for SDA = 1:OAA
if dist(SDA,3) > CCA+1
break
end
KBA = dist(SDA,1);PBA = dist(SDA,2);path = ZBA(BAA,[FDA(KBA); EDA(PBA)], [YBA(KBA); XBA(PBA)], -UCA, UCA);
if size(path,1) > 0
CBA(find(CBA==0,1,'first'):find(CBA==0,1,'first')+size(path,1)-1,:) = path;BAA = MBA(BAA,path,-UCA);TCA = TCA + 1;ACA = true;EDA([j PBA]) = EDA([PBA j]);XBA([j PBA]) = XBA([PBA j]);
break
end
end
if ~ACA
break
end
end
end
end
end
function [CBA BAA] = XCA(FAA,BAA,CBA,NCA,HDA), [CAA EAA] = RBA(FAA,BAA,CBA(1:find(CBA==0,1,'first')-1,:));[ZCA JCA] = NBA(BAA);
if JCA < 1
return
end
if mod(HDA,2) == 1
IBA = 2 + floor(rand*2);
[IDA ICA] = sort(ZCA(:,IBA),'descend');
else
[IDA ICA] = sort(ZCA(:,1),'descend');
end
ZCA = ZCA(ICA,:);
for i = 1:JCA
UCA = ZCA(i,1);[FDA YBA] = find(BAA == -UCA);RAA = size(FDA,1);
if RAA == 0 && ZCA(i,2) >= 2

[EDA XBA] = find(BAA == UCA);LAA = size(EDA,1);OAA = LAA*(LAA-1)/2;dist = zeros(OAA,3);SDA = 0;
for KBA = 1:LAA
for PBA = (KBA+1):LAA
SDA = SDA + 1;dist(SDA,1) = KBA;dist(SDA,2) = PBA;dist(SDA,3) = abs(EDA(KBA)-EDA(PBA)) + abs(XBA(KBA)-XBA(PBA));
end
end
[DCA ICA] = sort(dist(:,3));dist = dist(ICA,:);PCA = min((NCA*25)+9,2*UCA+1);ACA = false;
for SDA = 1:OAA
if dist(SDA,3) > PCA+1
break
end
KBA = dist(SDA,1);PBA = dist(SDA,2);path = QBA(BAA,CAA,EAA,[EDA(KBA); EDA(PBA)], [XBA(KBA); XBA(PBA)], -UCA, NCA, 2*UCA);
if size(path,1) > 0
CBA(find(CBA==0,1,'first'):find(CBA==0,1,'first')+size(path,1)-1,:) = path;[BAA CAA EAA] = LBA(BAA,CAA,EAA,path,-UCA);ACA = true;
break
end
end
if ~ACA
continue
end
end
[EDA XBA] = find(BAA == UCA);QAA = size(EDA,1);PCA = min((NCA*25)+9,UCA+1);
for j = 1:QAA
[FDA YBA] = find(BAA == -UCA);RAA = size(FDA,1);OAA = RAA * (QAA-j+1);dist = zeros(OAA,3);SDA = 0;
for KBA = 1:RAA
for PBA = j:QAA
SDA = SDA + 1;dist(SDA,1) = KBA;dist(SDA,2) = PBA;dist(SDA,3) = abs(FDA(KBA)-EDA(PBA)) + abs(YBA(KBA)-XBA(PBA));
end
end
[DCA ICA] = sort(dist(:,3));dist = dist(ICA,:);ACA = false;
for SDA = 1:OAA
if dist(SDA,3) > PCA+1
break
end
KBA = dist(SDA,1);PBA = dist(SDA,2);path = QBA(BAA,CAA,EAA,[FDA(KBA); EDA(PBA)], [YBA(KBA); XBA(PBA)], -UCA, NCA, UCA);
if size(path,1) > 0
CBA(find(CBA==0,1,'first'):find(CBA==0,1,'first')+size(path,1)-1,:) = path;[BAA CAA EAA] = LBA(BAA,CAA,EAA,path,-UCA);ACA = true;EDA([j PBA]) = EDA([PBA j]);XBA([j PBA]) = XBA([PBA j]);
break
end
end
if ~ACA
break
end
end
end; CBA = CBA(1:find(CBA==0,1,'first')-1,:);
end
function [CAA EAA] = RBA(FAA,BAA,path), [NAA MAA] = size(BAA);CAA = FAA == 0;EAA = FAA == 0;CAA(:,1) = false;CAA(:,MAA) = false;
EAA(1,:) = false;EAA(NAA,:) = false;PAA = size(path,1);
for i = 1:PAA
if path(i,1) == path(i,3)
CAA(path(i,1),path(i,2)) = false;CAA(path(i,3),path(i,4)) = false;
end
if path(i,2) == path(i,4)
EAA(path(i,1),path(i,2)) = false;EAA(path(i,3),path(i,4)) = false;
end
end
end
function [BAA CAA EAA] = LBA(BAA,CAA,EAA,path,LCA)
for i = 1:size(path,1);
if path(i,1) == path(i,3)
CAA(path(i,1),path(i,2)) = false;CAA(path(i,3),path(i,4)) = false;
end
if path(i,2) == path(i,4)
EAA(path(i,1),path(i,2)) = false;EAA(path(i,3),path(i,4)) = false;
end
if path(i,1) == path(i,3) && path(i,2) == path(i,4)
BAA(path(i,1),path(i,2)) = -9999;else BAA(path(i,1),path(i,2)) = LCA;BAA(path(i,3),path(i,4)) = LCA;
end
end
end
function BAA = MBA(BAA,path,LCA), BAA(path(1,1),path(1,2)) = LCA;
for i = 1:size(path,1);
BAA(path(i,3),path(i,4)) = LCA;
end
end
function path = ZBA(BAA,EDA,XBA,LCA,OCA)
function path = ODA(dr,FCA,MDA), UAA(dr,FCA) = BDA(i);TAA(dr,FCA) = SBA(i);path = zeros(MDA,4);
for j = 1:MDA
path(j,1:2) = [dr FCA];ADA = UAA(dr,FCA);VCA = TAA(dr,FCA);path(j,3:4) = [ADA VCA];dr = ADA;FCA = VCA;
end
end
[NAA MAA] = size(BAA);UAA = zeros(NAA,MAA);TAA = zeros(NAA,MAA);IAA = -ones(NAA,MAA);IAA(EDA(2),XBA(2)) = 0;IAA(EDA(1),XBA(1)) = -2;IAA( BAA == LCA ) = -2;
CDA = zeros(NAA*MAA,1);VBA = zeros(NAA*MAA,1);BCA = 1;CDA(1) = EDA(2);VBA(1) = XBA(2);CCA = 9;
for step = 0:min(CCA,OCA)
if BCA < 1, break, end
LAA = BCA;BDA = CDA(1:LAA);SBA = VBA(1:LAA);BCA = 0;
for i = 1:LAA
FCA = SBA(i);
if BDA(i) > 1
dr = BDA(i)-1;JBA = 1 + (dr-1) + (FCA-1)*NAA;NDA = IAA(JBA);
if NDA == -2
path = ODA(dr,FCA,step+1);return
elseif NDA == -1 && BAA(JBA) == 0
IAA(JBA) = step+1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);BCA = BCA + 1; CDA(BCA) = dr; VBA(BCA) = FCA;
end
end
if BDA(i) < NAA
dr = BDA(i) + 1;JBA = 1 + (dr-1) + (FCA-1)*NAA;NDA = IAA(JBA);
if NDA == -2
path = ODA(dr,FCA,step+1);return
elseif NDA == -1 && BAA(JBA) == 0
IAA(JBA) = step+1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);BCA = BCA + 1; CDA(BCA) = dr; VBA(BCA) = FCA;
end
end
dr = BDA(i);
if SBA(i) > 1
FCA = SBA(i) - 1;JBA = 1 + (dr-1) + (FCA-1)*NAA;NDA = IAA(JBA);
if NDA == -2
path = ODA(dr,FCA,step+1);return
elseif NDA == -1 && BAA(JBA) == 0
IAA(JBA) = step+1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);BCA = BCA + 1; CDA(BCA) = dr; VBA(BCA) = FCA;
end
end
if SBA(i) < MAA
FCA = SBA(i) + 1;JBA = 1 + (dr-1) + (FCA-1)*NAA;NDA = IAA(JBA);
if NDA == -2
path = ODA(dr,FCA,step+1);return
elseif NDA == -1 && BAA(JBA) == 0
IAA(JBA) = step+1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);BCA = BCA + 1; CDA(BCA) = dr; VBA(BCA) = FCA;
end
end
end
end
path = zeros(0,4);
end
function path = QBA(BAA,CAA,EAA,EDA,XBA,LCA,NCA,OCA)
function path = ODA(dr,FCA,step), JBA = 1 + (dr-1) + (FCA-1)*NAA;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);path = zeros(step,4);j = 0;
while dr ~= EDA(2) || FCA ~= XBA(2)
j = j + 1;path(j,1:2) = [dr FCA];JBA = 1 + (dr-1) + (FCA-1)*NAA;ADA = UAA(JBA);VCA = TAA(JBA);path(j,3:4) = [ADA VCA];dr = ADA;FCA = VCA;
if DAA(dr,FCA)
j = j + 1;path(j,:) = [dr FCA dr FCA];
end
end
path = path(1:j,:);
end
[NAA MAA] = size(BAA);DAA = false(NAA,MAA);UAA = zeros(NAA,MAA);TAA = zeros(NAA,MAA);IAA = -ones(NAA,MAA);IAA(EDA(2),XBA(2)) = 0;IAA(EDA(1),XBA(1)) = -2;
IAA( BAA == LCA ) = -2;KCA = 9;PCA = min((NCA*25)+KCA,OCA+1);KDA = zeros(PCA+26,1);
for step = 0:PCA
if step == 0
BDA = EDA(2);SBA = XBA(2);
elseif KDA(step) == 0
continue
else [BDA SBA] = find(IAA == step);
end
LAA = size(BDA,1);
for i = 1:LAA
dr = BDA(i);
if SBA(i) > 1
FCA = SBA(i) - 1;JBA = dr + (FCA-1)*NAA;NDA = IAA(JBA);
if NDA == -2
path = ODA(dr,FCA,step+1);return
elseif NDA == -1
if BAA(JBA) == 0
IAA(JBA) = step+1; KDA(step+1) = 1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);
elseif CAA(dr,FCA)
IAA(JBA) = step+26; KDA(step+26) = 1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);DAA(JBA) = true;
end
end
end
if SBA(i) < MAA
FCA = SBA(i) + 1;JBA = dr + (FCA-1)*NAA;NDA = IAA(JBA);
if NDA == -2
path = ODA(dr,FCA,step+1);return
elseif NDA == -1
if BAA(JBA) == 0
IAA(JBA) = step+1; KDA(step+1) = 1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);
elseif CAA(dr,FCA)
IAA(JBA) = step+26; KDA(step+26) = 1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);DAA(JBA) = true;
end
end
end
FCA = SBA(i);
if BDA(i) > 1
dr = BDA(i)-1;JBA = dr + (FCA-1)*NAA;NDA = IAA(JBA);
if NDA == -2
path = ODA(dr,FCA,step+1);return
elseif NDA == -1
if BAA(JBA) == 0
IAA(JBA) = step+1; KDA(step+1) = 1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);
elseif EAA(dr,FCA)
IAA(JBA) = step+26; KDA(step+26) = 1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);DAA(JBA) = true;
end
end
end
if BDA(i) < NAA
dr = BDA(i) + 1;JBA = dr + (FCA-1)*NAA;NDA = IAA(JBA);
if NDA == -2
path = ODA(dr,FCA,step+1);return
elseif NDA == -1
if BAA(JBA) == 0
IAA(JBA) = step+1; KDA(step+1) = 1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);
elseif EAA(dr,FCA)
IAA(JBA) = step+26; KDA(step+26) = 1;UAA(JBA) = BDA(i);TAA(JBA) = SBA(i);DAA(JBA) = true;
end
end
end
end
end
path = zeros(0,4);
end