function WAA = OBA(BAA)
[NCA,MCA]=size(BAA);
AAA=nan(NCA+2,MCA+2);
AAA(2:end-1,2:end-1)=BAA;
HAA = AAA;
ICA = 5;
WBA = 4;
XBA = 10;
YAA = zeros(0,4);
WAA = YAA;
SAA = inf;
for ZDA = [1 3]
[UAA EAA] = UCA(HAA,YAA,WBA,ZDA);
[VAA GAA] = WCA(HAA,EAA,UAA,0,XBA,ZDA);
for AEA = [3 1]
if ZDA == 3 && AEA == 1 && SAA > 2550
return
end
XAA = VCA(HAA,GAA,VAA,ICA,XBA,AEA)-1;
TAA = LCA(BAA,XAA);
if TAA <= SAA
SAA = TAA;
WAA = XAA;
else
end
end
end
end
function LDA = LCA(AAA,WAA)
NCA=size(AAA,1);
AAA(WAA(:,1)+(WAA(:,2)-1)*NCA)=0;
AAA(WAA(:,3)+(WAA(:,4)-1)*NCA)=0;
LDA=sum(AAA(:))+size(WAA,1)+sum(WAA(:,1)==WAA(:,3)&WAA(:,2)==WAA(:,4))*24;
end
function [YCA DCA] = FBA(AAA)
XCA = sort(AAA(AAA>0),'descend');
OCA = size(XCA,1);
if OCA < 1
YCA = [];
DCA = 0;
return
end
YCA = zeros(OCA,3);
YCA(1,1) = XCA(1);
DCA = 1;
VBA = 1;
for i = 2:OCA
if XCA(i) == YCA(DCA,1)
VBA = VBA + 1;
else
YCA(DCA,2) = VBA;
DCA = DCA + 1;
VBA = 1;
YCA(DCA,1) = XCA(i);
end
end
YCA(DCA,2) = VBA;
YCA = YCA(1:DCA,:);
for i = 1:DCA
if YCA(i,2) >= 2
QCA = YCA(i,1);
[HDA RBA] = find(AAA == QCA);
YBA = 0;
for j = 2:size(HDA,1);
YBA = YBA + abs(HDA(j)-HDA(j-1)) + abs(RBA(j)-RBA(j-1));
end
YCA(i,3) = YCA(i,2)*QCA - 0.85*YBA;
end
end
end
function [WAA AAA] = UCA(AAA,WAA,XBA,JDA)
[YCA DCA] = FBA(AAA);
if DCA < 1
return
end
[KDA CCA] = sort(YCA(:,JDA),'descend');
YCA = YCA(CCA,:);
for i = 1:DCA
if YCA(i,2) >= 2
QCA = YCA(i,1);
[HDA RBA] = find(AAA == QCA);
JAA = size(HDA,1);
MAA = JAA*(JAA-1)/2;
dist = zeros(MAA,3);
ZDA = 0;
for BBA = 1:JAA
for GBA = (BBA+1):JAA
ZDA = ZDA + 1;
dist(ZDA,1) = BBA;
dist(ZDA,2) = GBA;
dist(ZDA,3) = abs(HDA(BBA)-HDA(GBA)) + abs(RBA(BBA)-RBA(GBA));
end
end
[YBA CCA] = sort(dist(:,3));
dist = dist(CCA,:);
OCA = 0;
for ZDA = 1:MAA
if dist(ZDA,3) > XBA+1
break
end
BBA = dist(ZDA,1);
GBA = dist(ZDA,2);
path = TBA(AAA,[HDA(BBA); HDA(GBA)], [RBA(BBA); RBA(GBA)], -QCA, XBA, 2*QCA);
if size(path,1) > 0
WAA = [WAA; path];
AAA = DBA(AAA,path,-QCA);
OCA = 2;
edit = [1:(BBA-1) (BBA+1):(GBA-1) (GBA+1):JAA];
HDA = [HDA(BBA); HDA(GBA); HDA(edit)];
RBA = [RBA(BBA); RBA(GBA); RBA(edit)];
break
else
end
end
if OCA < 2
continue
end
for j = 3:JAA
[IDA SBA] = find(AAA == -QCA);
OAA = size(IDA,1);
MAA = OAA * (JAA - OCA);
dist = zeros(MAA,3);
ZDA = 0;
for BBA = 1:OAA
for GBA = (OCA+1):JAA
ZDA = ZDA + 1;
dist(ZDA,1) = BBA;
dist(ZDA,2) = GBA;
dist(ZDA,3) = abs(IDA(BBA)-HDA(GBA)) + abs(SBA(BBA)-RBA(GBA));
end
end
[YBA CCA] = sort(dist(:,3));
dist = dist(CCA,:);
UBA = false;
for ZDA = 1:MAA
if dist(ZDA,3) > XBA+1
break
end
BBA = dist(ZDA,1);
GBA = dist(ZDA,2);
path = TBA(AAA,[IDA(BBA); HDA(GBA)], [SBA(BBA); RBA(GBA)], -QCA, XBA, QCA);
if size(path,1) > 0
WAA = [WAA; path];
AAA = DBA(AAA,path,-QCA);
OCA = OCA + 1;
UBA = true;
HDA([j GBA]) = HDA([GBA j]);
RBA([j GBA]) = RBA([GBA j]);
break
end
end
if ~UBA
break
end
end
end
end
end
function [WAA AAA] = VCA(HAA,AAA,WAA,ICA,ECA,JDA)
[CAA FAA] = JBA(HAA,AAA,WAA);
[YCA DCA] = FBA(AAA);
if DCA < 1
return
end
[KDA CCA] = sort(YCA(:,JDA),'descend');
YCA = YCA(CCA,:);
for i = 1:DCA
QCA = YCA(i,1);
[IDA SBA] = find(AAA == -QCA);
OAA = size(IDA,1);
if OAA == 0
if YCA(i,2) >= 2
[HDA RBA] = find(AAA == QCA);
JAA = size(HDA,1);
MAA = JAA*(JAA-1)/2;
dist = zeros(MAA,3);
ZDA = 0;
for BBA = 1:JAA
for GBA = (BBA+1):JAA
ZDA = ZDA + 1;
dist(ZDA,1) = BBA;
dist(ZDA,2) = GBA;
dist(ZDA,3) = abs(HDA(BBA)-HDA(GBA)) + abs(RBA(BBA)-RBA(GBA));
end
end
[YBA CCA] = sort(dist(:,3));
dist = dist(CCA,:);
KCA = min((ICA*25)+ECA,2*QCA+1);
UBA = false;
for ZDA = 1:MAA
if dist(ZDA,3) > KCA+1
break
end
BBA = dist(ZDA,1);
GBA = dist(ZDA,2);
path = IBA(AAA,CAA,FAA,[HDA(BBA); HDA(GBA)], [RBA(BBA); RBA(GBA)], -QCA, ICA, ECA, 2*QCA);
if size(path,1) > 0
WAA = [WAA; path];
AAA = DBA(AAA,path,-QCA);
[AAA CAA FAA] = CBA(AAA,CAA,FAA,path,-QCA);
UBA = true;
break
end
end
if ~UBA
continue
end
end
end
[HDA RBA] = find(AAA == QCA);
NAA = size(HDA,1);
KCA = min((ICA*25)+ECA,QCA+1);
for j = 1:NAA
[IDA SBA] = find(AAA == -QCA);
OAA = size(IDA,1);
MAA = OAA * (NAA-j+1);
dist = zeros(MAA,3);
ZDA = 0;
for BBA = 1:OAA
for GBA = j:NAA
ZDA = ZDA + 1;
dist(ZDA,1) = BBA;
dist(ZDA,2) = GBA;
dist(ZDA,3) = abs(IDA(BBA)-HDA(GBA)) + abs(SBA(BBA)-RBA(GBA));
end
end
[YBA CCA] = sort(dist(:,3));
dist = dist(CCA,:);
UBA = false;
for ZDA = 1:MAA
if dist(ZDA,3) > KCA+1
break
end
BBA = dist(ZDA,1);
GBA = dist(ZDA,2);
path = IBA(AAA,CAA,FAA,[IDA(BBA); HDA(GBA)], [SBA(BBA); RBA(GBA)], -QCA, ICA, ECA, QCA);
if size(path,1) > 0
WAA = [WAA; path];
AAA = DBA(AAA,path,-QCA);
[AAA CAA FAA] = CBA(AAA,CAA,FAA,path,-QCA);
UBA = true;
HDA([j GBA]) = HDA([GBA j]);
RBA([j GBA]) = RBA([GBA j]);
break
end
end
if ~UBA
break
end
end
end
end
function [WAA AAA] = WCA(HAA,AAA,WAA,ICA,ECA,JDA)
[YCA DCA] = FBA(AAA);
if DCA < 1
return
end
[KDA CCA] = sort(YCA(:,JDA),'descend');
YCA = YCA(CCA,:);
for i = 1:DCA
QCA = YCA(i,1);
[IDA SBA] = find(AAA == -QCA);
OAA = size(IDA,1);
if OAA == 0
if YCA(i,2) >= 2
[HDA RBA] = find(AAA == QCA);
JAA = size(HDA,1);
MAA = JAA*(JAA-1)/2;
dist = zeros(MAA,3);
ZDA = 0;
for BBA = 1:JAA
for GBA = (BBA+1):JAA
ZDA = ZDA + 1;
dist(ZDA,1) = BBA;
dist(ZDA,2) = GBA;
dist(ZDA,3) = abs(HDA(BBA)-HDA(GBA)) + abs(RBA(BBA)-RBA(GBA));
end
end
[YBA CCA] = sort(dist(:,3));
dist = dist(CCA,:);
KCA = min((ICA*25)+ECA,2*QCA+1);
UBA = false;
for ZDA = 1:MAA
if dist(ZDA,3) > KCA+1
break
end
BBA = dist(ZDA,1);
GBA = dist(ZDA,2);
path = TBA(AAA,[HDA(BBA); HDA(GBA)], [RBA(BBA); RBA(GBA)], -QCA, ECA, 2*QCA);
if size(path,1) > 0
WAA = [WAA; path];
AAA = DBA(AAA,path,-QCA);
UBA = true;
break
end
end
if ~UBA
continue
end
end
end
[HDA RBA] = find(AAA == QCA);
NAA = size(HDA,1);
KCA = min((ICA*25)+ECA,QCA+1);
for j = 1:NAA
[IDA SBA] = find(AAA == -QCA);
OAA = size(IDA,1);
MAA = OAA * (NAA-j+1);
dist = zeros(MAA,3);
ZDA = 0;
for BBA = 1:OAA
for GBA = j:NAA
ZDA = ZDA + 1;
dist(ZDA,1) = BBA;
dist(ZDA,2) = GBA;
dist(ZDA,3) = abs(IDA(BBA)-HDA(GBA)) + abs(SBA(BBA)-RBA(GBA));
end
end
[YBA CCA] = sort(dist(:,3));
dist = dist(CCA,:);
UBA = false;
for ZDA = 1:MAA
if dist(ZDA,3) > KCA+1
break
end
BBA = dist(ZDA,1);
GBA = dist(ZDA,2);
path = TBA(AAA,[IDA(BBA); HDA(GBA)], [SBA(BBA); RBA(GBA)], -QCA, ECA, 2*QCA);
if size(path,1) > 0
WAA = [WAA; path];
AAA = DBA(AAA,path,-QCA);
UBA = true;
HDA([j GBA]) = HDA([GBA j]);
RBA([j GBA]) = RBA([GBA j]);
break
end
end
if ~UBA
break
end
end
end
end
function [CAA FAA] = JBA(HAA,AAA,path)
[LAA KAA] = size(AAA);
CAA = HAA == 0;
FAA = CAA;
CAA(:,[1 KAA]) = false;
FAA([1 LAA],:) = false;
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)
FAA(path(i,1),path(i,2)) = false;
FAA(path(i,3),path(i,4)) = false;
end
end
end
function [AAA CAA FAA] = CBA(AAA,CAA,FAA,path,FCA)
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;
if path(i,2) == path(i,4)
AAA(path(i,1),path(i,2)) = -9999;
end
end
if path(i,2) == path(i,4)
FAA(path(i,1),path(i,2)) = false;
FAA(path(i,3),path(i,4)) = false;
end
end
end
function AAA = DBA(AAA,path,FCA)
AAA(path(1,1),path(1,2)) = FCA;
for i = 1:size(path,1);
AAA(path(i,3),path(i,4)) = FCA;
end
end
function path = TBA(AAA,HDA,RBA,FCA,XBA,JCA)
function path = UDA(dr,ZBA,PDA)
QAA(dr,ZBA) = EDA(i);
PAA(dr,ZBA) = LBA(i);
path = zeros(PDA,4);
for j = 1:PDA
path(j,1:2) = [dr ZBA];
CDA = QAA(dr,ZBA);
TCA = PAA(dr,ZBA);
path(j,3:4) = [CDA TCA];
dr = CDA;
ZBA = TCA;
end
end
[LAA KAA] = size(AAA);
QAA = zeros(LAA,KAA);
PAA = zeros(LAA,KAA);
IAA = -ones(LAA,KAA);
IAA(HDA(2),RBA(2)) = 0;
IAA(HDA(1),RBA(1)) = -2;
IAA( AAA == FCA ) = -2;
GDA = zeros(LAA*KAA,1);
QBA = zeros(LAA*KAA,1);
VBA = 1;
GDA(1) = HDA(2);
QBA(1) = RBA(2);
for step = 0:min(XBA,JCA)
if VBA < 1, break, end
JAA = VBA;
EDA = GDA(1:JAA);
LBA = QBA(1:JAA);
VBA = 0;
for i = 1:JAA
NBA = LBA(i);
FDA = EDA(i);
ZBA = NBA;
dr = FDA-1;
ABA = dr + (ZBA-1)*LAA;
QDA = IAA(ABA);
if QDA == -2
path = UDA(dr,ZBA,step+1);
return
elseif QDA == -1 && AAA(ABA) == 0
IAA(ABA) = step+1;
QAA(ABA) = FDA;
PAA(ABA) = NBA;
VBA = VBA + 1; GDA(VBA) = dr; QBA(VBA) = ZBA;
end
dr = FDA + 1;
ABA = dr + (ZBA-1)*LAA;
QDA = IAA(ABA);
if QDA == -2
path = UDA(dr,ZBA,step+1);
return
elseif QDA == -1 && AAA(ABA) == 0
IAA(ABA) = step+1;
QAA(ABA) = FDA;
PAA(ABA) = NBA;
VBA = VBA + 1; GDA(VBA) = dr; QBA(VBA) = ZBA;
end
dr = FDA;
ZBA = NBA - 1;
ABA = dr + (ZBA-1)*LAA;
QDA = IAA(ABA);
if QDA == -2
path = UDA(dr,ZBA,step+1);
return
elseif QDA == -1 && AAA(ABA) == 0
IAA(ABA) = step+1;
QAA(ABA) = FDA;
PAA(ABA) = NBA;
VBA = VBA + 1; GDA(VBA) = dr; QBA(VBA) = ZBA;
end
ZBA = NBA + 1;
ABA = dr + (ZBA-1)*LAA;
QDA = IAA(ABA);
if QDA == -2
path = UDA(dr,ZBA,step+1);
return
elseif QDA == -1 && AAA(ABA) == 0
IAA(ABA) = step+1;
QAA(ABA) = FDA;
PAA(ABA) = NBA;
VBA = VBA + 1; GDA(VBA) = dr; QBA(VBA) = ZBA;
end
end
end
path = zeros(0,4);
end
function path = IBA(AAA,CAA,FAA,HDA,RBA,FCA,ICA,ECA,JCA)
function path = UDA(ABA,step)
RAA(ABA) = DEA;
dr=mod(ABA,LAA);
ZBA=ceil(ABA/LAA);
path = zeros(step,4);
j = 0;
while dr ~= HDA(2) || ZBA ~= RBA(2)
j = j + 1;
path(j,1:2) = [dr ZBA];
ABA = dr + (ZBA-1)*LAA;
DDA = RAA(ABA);
CDA=mod(DDA,LAA);
TCA=ceil(DDA/LAA);
path(j,3:4) = [CDA TCA];
dr = CDA;
ZBA = TCA;
if DAA(dr,ZBA)
j = j + 1;
path(j,:) = [dr ZBA dr ZBA];
end
end
path = path(1:j,:);
end
[LAA KAA] = size(AAA);
DAA = false(LAA,KAA);
RAA = zeros(LAA,KAA);
IAA = -ones(LAA,KAA);
IAA(HDA(2),RBA(2)) = 0;
IAA(HDA(1),RBA(1)) = -2;
IAA( AAA == FCA ) = -2;
KCA = min((ICA*25)+ECA,JCA+1);
ODA = zeros(KCA+26,1);
for step = 0:KCA
if step == 0
CEA = HDA(2) + (RBA(2)-1)*LAA;
elseif ODA(step) == 0
continue
else
CEA = find(IAA == step);
end
JAA = numel(CEA);
for i = 1:JAA
DEA = CEA(i);
ABA = DEA - LAA;
QDA = IAA(ABA);
if QDA == -2
path = UDA(ABA,step+1);
return
elseif QDA == -1
if AAA(ABA) == 0
IAA(ABA) = step+1; ODA(step+1) = 1;
RAA(ABA) = DEA;
elseif CAA(ABA)
IAA(ABA) = step+26; ODA(step+26) = 1;
RAA(ABA) = DEA;
DAA(ABA) = true;
end
end
ABA = DEA + LAA;
QDA = IAA(ABA);
if QDA == -2
path = UDA(ABA,step+1);
return
elseif QDA == -1
if AAA(ABA) == 0
IAA(ABA) = step+1; ODA(step+1) = 1;
RAA(ABA) = DEA;
elseif CAA(ABA)
IAA(ABA) = step+26; ODA(step+26) = 1;
RAA(ABA) = DEA;
DAA(ABA) = true;
end
end
ABA = DEA - 1;
QDA = IAA(ABA);
if QDA == -2
path = UDA(ABA,step+1);
return
elseif QDA == -1
if AAA(ABA) == 0
IAA(ABA) = step+1; ODA(step+1) = 1;
RAA(ABA) = DEA;
elseif FAA(ABA)
IAA(ABA) = step+26; ODA(step+26) = 1;
RAA(ABA) = DEA;
DAA(ABA) = true;
end
end
ABA = DEA + 1;
QDA = IAA(ABA);
if QDA == -2
path = UDA(ABA,step+1);
return
elseif QDA == -1
if AAA(ABA) == 0
IAA(ABA) = step+1; ODA(step+1) = 1;
RAA(ABA) = DEA;
elseif FAA(ABA)
IAA(ABA) = step+26; ODA(step+26) = 1;
RAA(ABA) = DEA;
DAA(ABA) = true;
end
end
end
end
path = zeros(0,4);
end