function TBA = solver(DAA)
KAA = DAA;
PEA = 4;
JDA = 4;
KDA = 9;
XBA = zeros(0,4);
TBA = XBA;
NBA = inf;
for CHA = [1 3]
[RBA GAA] = JFA(KAA,XBA,JDA,CHA);
[SBA IAA] = LFA(KAA,GAA,RBA,0,KDA,CHA);
for EHA = [3 1]
if CHA == 3 && EHA ==1 && NBA > 1000
return
end
UBA = KFA(KAA,IAA,SBA,PEA,KDA,EHA);
OBA = UEA(KAA,UBA);
if OBA <= NBA
NBA = OBA;
TBA = UBA;
else
end
end
end
end
function AGA = UEA(DAA,TBA)
[VFA,YCA] = size(DAA);
MDA = abs(TBA(:,[1 2])-TBA(:,[3 4]));
NAA = TBA(~any(MDA,2),[1 2]);
AHA = size(TBA,1) + 24 * size(NAA,1);
TBA = TBA(all(TBA(:,[1 3])>0 & TBA(:,[1 3])<=VFA & TBA(:,[2 4])>0 & TBA(:,[2 4])<=YCA,2) & (sum(MDA,2)==1),:);
SBA = sort([sub2ind([VFA,YCA],TBA(:,1),TBA(:,2)) sub2ind([VFA,YCA],TBA(:,3),TBA(:,4))],2);
MAA = sub2ind([VFA,YCA],NAA(:,1),NAA(:,2));
VAA = zeros(size(SBA));
[XEA,QDA,VAA(:)]= unique(SBA);
VEA = numel(XEA);
XDA(XEA) = 1:VEA;
AAA = zeros(VEA,4);
for i = 1:VEA
[j,HEA] = find(XEA(i)==SBA);
AAA(i,2*(diff(SBA(j,:),[],2)>1)+HEA) = sum(VAA(j,:),2)-i;
end
MAA = intersect(MAA,SBA(:));
MAA = MAA(DAA(MAA)==0);
MAA = MAA(any(AAA(XDA(MAA),[1 2]),2) & any(AAA(XDA(MAA),[3 4]),2));
AAA = [AAA;zeros(numel(MAA),4)];
XEA = [XEA; MAA];
j = VEA;
for i = XDA(MAA)
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
KEA = zeros(size(AAA,1),1);
RGA = find(~KEA,1);
SCA = 1;
while ~isempty(RGA)
while ~isempty(RGA)
KEA(RGA) = SCA;
RGA = nonzeros(AAA(RGA,:));
RGA = RGA(KEA(RGA) == 0);
end
SCA = SCA+1;
RGA = find(~KEA,1);
end
PAA = zeros(VFA,YCA);
PAA(XEA) = KEA;
YAA = ~PAA & DAA>0;
PAA(YAA) = SCA+(0:nnz(YAA)-1);
PAA(MAA)=-1;
WBA = zeros(size(SBA,1),1);
for i=1:size(AAA,1)
for j = 1:4
if AAA(i,j)
WBA(SBA(:,1)==XEA(i) & SBA(:,2)==XEA(AAA(i,j))) = KEA(i);
end
end
end
JBA = unique(nonzeros(DAA));
for i = 1:SCA-1
FFA = unique(nonzeros(DAA(PAA==i)));
if numel(FFA)>1
JBA = setdiff(JBA,FFA);
end
end
for i = 1:numel(JBA)
[IGA,TCA] = max(sparse(PAA(DAA==JBA(i)),1,1));
if IGA>1
DAA(PAA==TCA)=0;
end
end
AGA = sum(nonzeros(DAA)) + AHA;
end
function [NFA HEA] = HCA(DAA)
MFA = sort(DAA(DAA>0),'descend');
AFA = size(MFA,1);
if AFA < 1
NFA = [];
HEA = 0;
return
end
NFA = zeros(AFA,3);
NFA(1,1) = MFA(1);
HEA = 1;
HDA = 1;
for i = 2:AFA
if MFA(i) == NFA(HEA,1)
HDA = HDA + 1;
else
NFA(HEA,2) = HDA;
HEA = HEA + 1;
HDA = 1;
NFA(HEA,1) = MFA(i);
end
end
NFA(HEA,2) = HDA;
NFA = NFA(1:HEA,:);
for i = 1:HEA
if NFA(i,2) >= 2
FFA = NFA(i,1);
[WFA ZCA] = find(DAA == FFA);
LDA = 0;
for j = 2:size(WFA,1);
LDA = LDA + abs(WFA(j)-WFA(j-1)) + abs(ZCA(j)-ZCA(j-1));
end
NFA(i,3) = NFA(i,2)*FFA - 0.85*LDA;
end
end
end
function [TBA DAA] = JFA(DAA,TBA,KDA,YFA)
[NFA HEA] = HCA(DAA);
if HEA < 1
return
end
[ZFA GEA] = sort(NFA(:,YFA),'descend');
NFA = NFA(GEA,:);
for i = 1:HEA
if NFA(i,2) >= 2
FFA = NFA(i,1);
[WFA ZCA] = find(DAA == FFA);
DBA = size(WFA,1);
GBA = DBA*(DBA-1)/2;
dist = zeros(GBA,3);
CHA = 0;
for ACA = 1:DBA
for ICA = (ACA+1):DBA
CHA = CHA + 1;
dist(CHA,1) = ACA;
dist(CHA,2) = ICA;
dist(CHA,3) = abs(WFA(ACA)-WFA(ICA)) + abs(ZCA(ACA)-ZCA(ICA));
end
end
[LDA GEA] = sort(dist(:,3));
dist = dist(GEA,:);
AFA = 0;
for CHA = 1:GBA
if dist(CHA,3) > KDA+1
break
end
ACA = dist(CHA,1);
ICA = dist(CHA,2);
path = BDA(DAA,[WFA(ACA); WFA(ICA)], [ZCA(ACA); ZCA(ICA)], -FFA, KDA, 2*FFA);
if size(path,1) > 0
TBA = [TBA; path];
DAA = CCA(DAA,path,-FFA);
AFA = 2;
edit = [1:(ACA-1) (ACA+1):(ICA-1) (ICA+1):DBA];
WFA = [WFA(ACA); WFA(ICA); WFA(edit)];
ZCA = [ZCA(ACA); ZCA(ICA); ZCA(edit)];
break
else
end
end
if AFA < 2
continue
end
for j = 3:DBA
[XFA ADA] = find(DAA == -FFA);
IBA = size(XFA,1);
GBA = IBA * (DBA - AFA);
dist = zeros(GBA,3);
CHA = 0;
for ACA = 1:IBA
for ICA = (AFA+1):DBA
CHA = CHA + 1;
dist(CHA,1) = ACA;
dist(CHA,2) = ICA;
dist(CHA,3) = abs(XFA(ACA)-WFA(ICA)) + abs(ADA(ACA)-ZCA(ICA));
end
end
[LDA GEA] = sort(dist(:,3));
dist = dist(GEA,:);
DDA = false;
for CHA = 1:GBA
if dist(CHA,3) > KDA+1
break
end
ACA = dist(CHA,1);
ICA = dist(CHA,2);
path = BDA(DAA,[XFA(ACA); WFA(ICA)], [ADA(ACA); ZCA(ICA)], -FFA, KDA, FFA);
if size(path,1) > 0
TBA = [TBA; path];
DAA = CCA(DAA,path,-FFA);
AFA = AFA + 1;
DDA = true;
WFA([j ICA]) = WFA([ICA j]);
ZCA([j ICA]) = ZCA([ICA j]);
break
end
end
if ~DDA
break
end
end
end
end
end
function [TBA DAA] = KFA(KAA,DAA,TBA,PEA,IEA,YFA)
[EAA HAA] = NCA(KAA,DAA,TBA);
[NFA HEA] = HCA(DAA);
if HEA < 1
return
end
[ZFA GEA] = sort(NFA(:,YFA),'descend');
NFA = NFA(GEA,:);
for i = 1:HEA
FFA = NFA(i,1);
[XFA ADA] = find(DAA == -FFA);
IBA = size(XFA,1);
if IBA == 0
if NFA(i,2) >= 2
[WFA ZCA] = find(DAA == FFA);
DBA = size(WFA,1);
GBA = DBA*(DBA-1)/2;
dist = zeros(GBA,3);
CHA = 0;
for ACA = 1:DBA
for ICA = (ACA+1):DBA
CHA = CHA + 1;
dist(CHA,1) = ACA;
dist(CHA,2) = ICA;
dist(CHA,3) = abs(WFA(ACA)-WFA(ICA)) + abs(ZCA(ACA)-ZCA(ICA));
end
end
[LDA GEA] = sort(dist(:,3));
dist = dist(GEA,:);
REA = min((PEA*25)+IEA,2*FFA+1);
DDA = false;
for CHA = 1:GBA
if dist(CHA,3) > REA+1
break
end
ACA = dist(CHA,1);
ICA = dist(CHA,2);
path = LCA(DAA,EAA,HAA,[WFA(ACA); WFA(ICA)], [ZCA(ACA); ZCA(ICA)], -FFA, PEA, IEA, 2*FFA);
if size(path,1) > 0
TBA = [TBA; path];
DAA = CCA(DAA,path,-FFA);
[DAA EAA HAA] = BCA(DAA,EAA,HAA,path,-FFA);
DDA = true;
break
end
end
if ~DDA
continue
end
end
end
[WFA ZCA] = find(DAA == FFA);
HBA = size(WFA,1);
REA = min((PEA*25)+IEA,FFA+1);
for j = 1:HBA
[XFA ADA] = find(DAA == -FFA);
IBA = size(XFA,1);
GBA = IBA * (HBA-j+1);
dist = zeros(GBA,3);
CHA = 0;
for ACA = 1:IBA
for ICA = j:HBA
CHA = CHA + 1;
dist(CHA,1) = ACA;
dist(CHA,2) = ICA;
dist(CHA,3) = abs(XFA(ACA)-WFA(ICA)) + abs(ADA(ACA)-ZCA(ICA));
end
end
[LDA GEA] = sort(dist(:,3));
dist = dist(GEA,:);
DDA = false;
for CHA = 1:GBA
if dist(CHA,3) > REA+1
break
end
ACA = dist(CHA,1);
ICA = dist(CHA,2);
path = LCA(DAA,EAA,HAA,[XFA(ACA); WFA(ICA)], [ADA(ACA); ZCA(ICA)], -FFA, PEA, IEA, FFA);
if size(path,1) > 0
TBA = [TBA; path];
DAA = CCA(DAA,path,-FFA);
[DAA EAA HAA] = BCA(DAA,EAA,HAA,path,-FFA);
DDA = true;
WFA([j ICA]) = WFA([ICA j]);
ZCA([j ICA]) = ZCA([ICA j]);
break
end
end
if ~DDA
break
end
end
end
end
function [TBA DAA] = LFA(KAA,DAA,TBA,PEA,IEA,YFA)
[NFA HEA] = HCA(DAA);
if HEA < 1
return
end
[ZFA GEA] = sort(NFA(:,YFA),'descend');
NFA = NFA(GEA,:);
for i = 1:HEA
FFA = NFA(i,1);
[XFA ADA] = find(DAA == -FFA);
IBA = size(XFA,1);
if IBA == 0
if NFA(i,2) >= 2
[WFA ZCA] = find(DAA == FFA);
DBA = size(WFA,1);
GBA = DBA*(DBA-1)/2;
dist = zeros(GBA,3);
CHA = 0;
for ACA = 1:DBA
for ICA = (ACA+1):DBA
CHA = CHA + 1;
dist(CHA,1) = ACA;
dist(CHA,2) = ICA;
dist(CHA,3) = abs(WFA(ACA)-WFA(ICA)) + abs(ZCA(ACA)-ZCA(ICA));
end
end
[LDA GEA] = sort(dist(:,3));
dist = dist(GEA,:);
REA = min((PEA*25)+IEA,2*FFA+1);
DDA = false;
for CHA = 1:GBA
if dist(CHA,3) > REA+1
break
end
ACA = dist(CHA,1);
ICA = dist(CHA,2);
path = BDA(DAA,[WFA(ACA); WFA(ICA)], [ZCA(ACA); ZCA(ICA)], -FFA, IEA, 2*FFA);
if size(path,1) > 0
TBA = [TBA; path];
DAA = CCA(DAA,path,-FFA);
DDA = true;
break
end
end
if ~DDA
continue
end
end
end
[WFA ZCA] = find(DAA == FFA);
HBA = size(WFA,1);
REA = min((PEA*25)+IEA,FFA+1);
for j = 1:HBA
[XFA ADA] = find(DAA == -FFA);
IBA = size(XFA,1);
GBA = IBA * (HBA-j+1);
dist = zeros(GBA,3);
CHA = 0;
for ACA = 1:IBA
for ICA = j:HBA
CHA = CHA + 1;
dist(CHA,1) = ACA;
dist(CHA,2) = ICA;
dist(CHA,3) = abs(XFA(ACA)-WFA(ICA)) + abs(ADA(ACA)-ZCA(ICA));
end
end
[LDA GEA] = sort(dist(:,3));
dist = dist(GEA,:);
DDA = false;
for CHA = 1:GBA
if dist(CHA,3) > REA+1
break
end
ACA = dist(CHA,1);
ICA = dist(CHA,2);
path = BDA(DAA,[XFA(ACA); WFA(ICA)], [ADA(ACA); ZCA(ICA)], -FFA, IEA, 2*FFA);
if size(path,1) > 0
TBA = [TBA; path];
DAA = CCA(DAA,path,-FFA);
DDA = true;
WFA([j ICA]) = WFA([ICA j]);
ZCA([j ICA]) = ZCA([ICA j]);
break
end
end
if ~DDA
break
end
end
end
end
function [EAA HAA] = NCA(KAA,DAA,path)
[FBA EBA] = size(DAA);
EAA = KAA == 0;
HAA = EAA;
EAA(:,[1 EBA]) = false;
HAA([1 FBA],:) = false;
for i = 1:size(path,1)
if path(i,1) == path(i,3)
EAA(path(i,1),path(i,2)) = false;
EAA(path(i,3),path(i,4)) = false;
end
if path(i,2) == path(i,4)
HAA(path(i,1),path(i,2)) = false;
HAA(path(i,3),path(i,4)) = false;
end
end
end
function [DAA EAA HAA] = DHA(DAA,EAA,HAA,path,JEA)
for i = 1:size(path,1);
if path(i,1) == path(i,3)
EAA(path(i,1),path(i,2)) = false;
EAA(path(i,3),path(i,4)) = false;
end
if path(i,2) == path(i,4)
HAA(path(i,1),path(i,2)) = false;
HAA(path(i,3),path(i,4)) = false;
end
if path(i,1) == path(i,3) && path(i,2) == path(i,4)
DAA(path(i,1),path(i,2)) = -9999;
else
DAA(path(i,1),path(i,2)) = JEA;
DAA(path(i,3),path(i,4)) = JEA;
end
end
end
function [DAA EAA HAA] = BCA(DAA,EAA,HAA,path,JEA)
for i = 1:size(path,1);
if path(i,1) == path(i,3)
EAA(path(i,1),path(i,2)) = false;
EAA(path(i,3),path(i,4)) = false;
if path(i,2) == path(i,4)
DAA(path(i,1),path(i,2)) = -9999;
end
end
if path(i,2) == path(i,4)
HAA(path(i,1),path(i,2)) = false;
HAA(path(i,3),path(i,4)) = false;
end
end
end
function DAA = CCA(DAA,path,JEA)
DAA(path(1,1),path(1,2)) = JEA;
for i = 1:size(path,1);
DAA(path(i,3),path(i,4)) = JEA;
end
end
function path = BDA(DAA,WFA,ZCA,JEA,KDA,QEA)
function path = QGA(dr,NDA,JGA)
LBA(dr,NDA) = SFA(i);
KBA(dr,NDA) = QCA(i);
path = zeros(JGA,4);
for j = 1:JGA
path(j,1:2) = [dr NDA];
RFA = LBA(dr,NDA);
IFA = KBA(dr,NDA);
path(j,3:4) = [RFA IFA];
dr = RFA;
NDA = IFA;
end
end
[FBA EBA] = size(DAA);
LBA = zeros(FBA,EBA);
KBA = zeros(FBA,EBA);
PAA = -ones(FBA,EBA);
PAA(WFA(2),ZCA(2)) = 0;
PAA(WFA(1),ZCA(1)) = -2;
PAA( DAA == JEA ) = -2;
UFA = zeros(FBA*EBA,1);
XCA = zeros(FBA*EBA,1);
HDA = 1;
UFA(1) = WFA(2);
XCA(1) = ZCA(2);
for step = 0:min(KDA,QEA)
if HDA < 1, break, end
DBA = HDA;
SFA = UFA(1:DBA);
QCA = XCA(1:DBA);
HDA = 0;
for i = 1:DBA
NDA = QCA(i);
if SFA(i) > 1
dr = SFA(i)-1;
ZBA = dr + (NDA-1)*FBA;
KGA = PAA(ZBA);
if KGA == -2
path = QGA(dr,NDA,step+1);
return
elseif KGA == -1 && DAA(ZBA) == 0
PAA(ZBA) = step+1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
HDA = HDA + 1; UFA(HDA) = dr; XCA(HDA) = NDA;
end
end
if SFA(i) < FBA
dr = SFA(i) + 1;
ZBA = dr + (NDA-1)*FBA;
KGA = PAA(ZBA);
if KGA == -2
path = QGA(dr,NDA,step+1);
return
elseif KGA == -1 && DAA(ZBA) == 0
PAA(ZBA) = step+1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
HDA = HDA + 1; UFA(HDA) = dr; XCA(HDA) = NDA;
end
end
dr = SFA(i);
if QCA(i) > 1
NDA = QCA(i) - 1;
ZBA = dr + (NDA-1)*FBA;
KGA = PAA(ZBA);
if KGA == -2
path = QGA(dr,NDA,step+1);
return
elseif KGA == -1 && DAA(ZBA) == 0
PAA(ZBA) = step+1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
HDA = HDA + 1; UFA(HDA) = dr; XCA(HDA) = NDA;
end
end
if QCA(i) < EBA
NDA = QCA(i) + 1;
ZBA = dr + (NDA-1)*FBA;
KGA = PAA(ZBA);
if KGA == -2
path = QGA(dr,NDA,step+1);
return
elseif KGA == -1 && DAA(ZBA) == 0
PAA(ZBA) = step+1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
HDA = HDA + 1; UFA(HDA) = dr; XCA(HDA) = NDA;
end
end
end
end
path = zeros(0,4);
end
function path = LCA(DAA,EAA,HAA,WFA,ZCA,JEA,PEA,IEA,QEA)
function path = QGA(dr,NDA,step)
ZBA = dr + (NDA-1)*FBA;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
path = zeros(step,4);
j = 0;
while dr ~= WFA(2) || NDA ~= ZCA(2)
j = j + 1;
path(j,1:2) = [dr NDA];
ZBA = dr + (NDA-1)*FBA;
RFA = LBA(ZBA);
IFA = KBA(ZBA);
path(j,3:4) = [RFA IFA];
dr = RFA;
NDA = IFA;
if FAA(dr,NDA)
j = j + 1;
path(j,:) = [dr NDA dr NDA];
end
end
path = path(1:j,:);
end
[FBA EBA] = size(DAA);
FAA = false(FBA,EBA);
LBA = zeros(FBA,EBA);
KBA = zeros(FBA,EBA);
PAA = -ones(FBA,EBA);
PAA(WFA(2),ZCA(2)) = 0;
PAA(WFA(1),ZCA(1)) = -2;
PAA( DAA == JEA ) = -2;
REA = min((PEA*25)+IEA,QEA+1);
HGA = zeros(REA+26,1);
for step = 0:REA
if step == 0
SFA = WFA(2);
QCA = ZCA(2);
elseif HGA(step) == 0
continue
else
[SFA QCA] = find(PAA == step);
end
DBA = size(SFA,1);
for i = 1:DBA
dr = SFA(i);
if QCA(i) > 1
NDA = QCA(i) - 1;
ZBA = dr + (NDA-1)*FBA;
KGA = PAA(ZBA);
if KGA == -2
path = QGA(dr,NDA,step+1);
return
elseif KGA == -1
if DAA(ZBA) == 0
PAA(ZBA) = step+1; HGA(step+1) = 1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
elseif EAA(dr,NDA)
PAA(ZBA) = step+26; HGA(step+26) = 1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
FAA(ZBA) = true;
end
end
end
if QCA(i) < EBA
NDA = QCA(i) + 1;
ZBA = dr + (NDA-1)*FBA;
KGA = PAA(ZBA);
if KGA == -2
path = QGA(dr,NDA,step+1);
return
elseif KGA == -1
if DAA(ZBA) == 0
PAA(ZBA) = step+1; HGA(step+1) = 1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
elseif EAA(dr,NDA)
PAA(ZBA) = step+26; HGA(step+26) = 1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
FAA(ZBA) = true;
end
end
end
NDA = QCA(i);
if SFA(i) > 1
dr = SFA(i)-1;
ZBA = dr + (NDA-1)*FBA;
KGA = PAA(ZBA);
if KGA == -2
path = QGA(dr,NDA,step+1);
return
elseif KGA == -1
if DAA(ZBA) == 0
PAA(ZBA) = step+1; HGA(step+1) = 1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
elseif HAA(dr,NDA)
PAA(ZBA) = step+26; HGA(step+26) = 1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
FAA(ZBA) = true;
end
end
end
if SFA(i) < FBA
dr = SFA(i) + 1;
ZBA = dr + (NDA-1)*FBA;
KGA = PAA(ZBA);
if KGA == -2
path = QGA(dr,NDA,step+1);
return
elseif KGA == -1
if DAA(ZBA) == 0
PAA(ZBA) = step+1; HGA(step+1) = 1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
elseif HAA(dr,NDA)
PAA(ZBA) = step+26; HGA(step+26) = 1;
LBA(ZBA) = SFA(i);
KBA(ZBA) = QCA(i);
FAA(ZBA) = true;
end
end
end
end
end
path = zeros(0,4);
end