function [AA,AB]=solver(AD)
rand('state',0);
rand(7,1);
[AL,n]=size(AD);
CK=sum(AD(:)>0);
rows=AL+4;
CP=5:rows;
cols=n+4;
cv=5:cols;
fill=(CK-nnz(AD<0))/(AL*n);
i=repmat(CP',[n 1]);
j=reshape(repmat(cv,[AL 1]),[AL*n 1]);
DK=AL+8;
DL=n+8;
DM=-ones(DK,DL);
DM(CP,cv)=AD;
AK=[i;i;i;i];
DW=[j;j;j;j];
DX=[i;i;i-2;i+2];
EA=[j-2;j+2;j;j];
EF=[i;i;i-4;i+4];
EG=[j-4;j+4;j;j];
EM=[i-2;i+2;i-2;i+2];
EP=[j-2;j+2;j+2;j-2];
ES=[i+2;i-2;i-2;i+2];
ET=[j-2;j+2;j-2;j+2];
EV=AK+(DW-1)*DK;
EZ=DX+(EA-1)*DK;
FB=(EV+EZ)*0.5;
FI=(DM(EV)<0) | (DM(FB)<0) | (DM(EZ)<0);
AK(FI)=[];
DW(FI)=[];
DX(FI)=[];
EA(FI)=[];
EV(FI)=[];
EZ(FI)=[];
FB(FI)=[];
EF(FI)=[];
EM(FI)=[];
ES(FI)=[];
EG(FI)=[];
EP(FI)=[];
ET(FI)=[];
[FJ,FK,FL]=FM(FB,EV,EZ);
FU=EF+(EG-1)*DK;
FV=EM+(EP-1)*DK;
FW=ES+(ET-1)*DK;
FX=[FU FV FW];
FY=(EZ+FU)*0.5;
FZ=(EZ+FV)*0.5;
GA=(EZ+FW)*0.5;
GB=[FY FZ GA];
GD=[AK DW DX EA];
GE=[DX EA EF EG];
GF=[DX EA EM EP];
GG=[DX EA ES ET];
GH={GE,GF,GG};
[AA,AB]=GJ( ...
DM,...
EV,EZ,FB,...
CK,...
FX,GB,GD,GH,...
FJ,FK,FL);
GK=sum(AD(AD>0));
GL=0.81*GK;
for GQ=GR(CK)
if (size(AA,1)<=3) || (AB>GL)
AA=AA - 4;
return
end
[HC,HD]=HE( ...
DM,...
GQ,0,...
EV,EZ,FB,...
CK, ...
FX,GB,GD,...
FJ,FK,FL);
if (HD>AB)
AB=HD;
AA=HC;
end
end
HH=1;
while HH<=(min((CK*0.0078125)+1,3)*(AB<GK*0.79))
[HC,HD]=HE( ...
DM,...
1.0,1.16,...
EV,EZ,FB,...
CK,...
FX,GB,GD,...
FJ,FK,FL);
if (HD>AB)
AB=HD;
AA=HC;
end
HH=HH+1;
end
AA=AA - 4;
if (CK<272) && (fill<.96)*(AB<GK*0.775)
[HC,HD]=HJ(AD,rows,cols);
if (HD>AB)
AB=HD;
AA=HC;
end
end
end
function HK=GR(CK)
HM=2*(rand(4,1)-0.5);
switch ceil(CK/102.5)
case 1
HK=[1+0.1*HM(1) 0.05];
case 2
HK=[6.8 5 2.1 1+0.1*HM(2) 0.6+0.1*HM(2) 0.4762];
rand(750,1);
case 3
HK=[0.05 2.1 1+0.1*HM(3) 0.6+0.1*HM(3) 0.4+0.1*HM(3) 0.254];
case 5
HK=[0.05 2.1 0.6+0.1*HM(4) 0.18];
otherwise
HK=[0.05 2.1 1+0.1*HM(4) 0.592];
end
end
function [FJ,FK,FL]=FM(FB,EV,EZ)
HR=max([max(FB) max(EV) max(EZ)]);
HZ=zeros(HR,1);
IA=HZ;
IB=HZ;
FJ=zeros(HR,4);
FK=FJ;
FL=FJ;
for HH=1:numel(EV)
HZ(EV(HH))=HZ(EV(HH))+1;
FJ(EV(HH),HZ(EV(HH)))=HH;
IA(FB(HH))=IA(FB(HH))+1;
FK(FB(HH),IA(FB(HH)))=HH;
IB(EZ(HH))=IB(EZ(HH))+1;
FL(EZ(HH),IB(EZ(HH)))=HH;
end
end
function [AA,IP]=HJ(AD,rows,cols)
IQ=-ones(rows,cols);
IQ(3:end-2,3:end-2)=AD;
IT=nnz(IQ);
AA=zeros(IT,4);
IU=zeros(IT*4,1);
IV=IU;
IW=IU;
IX=IU;
IY=IU;
JB=0.1*mean(AD(AD>0));
JC=0;
JD=0;
AB=0;
JE=0;
IP=0;
depth=10;
JF=0;
JG=0;
[JH,JI,JJ]=JK(IQ);
while true
if isempty(JH)
break
end
JQ(IQ,JH,JJ,JI);
if (JF ~=0) && (JG>2)
for JS=1:JG-1
JH=[JH;IY(JS)];
JJ=[JJ;IY(JS+1)];
JI=[JI;JF];
DoMove(numel(JH));
end
else
[JW,JX]=sort(JI,'descend');
JI=JW;
JH=JH(JX);
JJ=JJ(JX);
for JS=1:min(depth,numel(JH))
[KD,newC,KE,KF]=...
KG(IQ,JS,JH,JJ,JI);
JQ(KD,newC,KE,KF);
JW(JS)=JW(JS)+JF;
end
[KH,JX]=max(JW);
DoMove(JX)
end
end
AA(JE+1:end,:)=[];
function DoMove(JX)
KK=JH(JX);
KM=JJ(JX);
JC=JC+1;
AA(JC,:)=[mod(KK-2,rows),ceil(KK/rows)-2,mod(KM-2,rows),ceil(KM/rows)-2];
KO=(KK+KM)/2;
AB=AB+IQ(KO);
if (KK ~=JD)
AB=AB - IQ(KK);
end
if (AB>IP)
JE=JC;
IP=AB;
end;
[IQ,JH,JJ,JI]=KG(IQ,JX,JH,JJ,JI);
JD=KM;
end
function JQ(IQ,JH,JJ,JI)
JF=0;
if ~isempty(JH)
KV=JJ(1:numel(JH));
KW=(~IQ(KV+2)&IQ(KV+1));
KW=(~IQ(KV-2)&IQ(KV-1))|KW;
KW=(~IQ(KV-2*rows)&IQ(KV-rows))|KW;
KW=(~IQ(KV+2*rows)&IQ(KV+rows))|KW;
KX=find(~KW);
if ~isempty(KX)
KY=JI(KX);[JF,KY]=max(KY);KY=KX(KY);
JG=2;IY(1)=JH(KY);IY(2)=JJ(KY);
end;
KX=find(KW)';
for KZ=KX
IX(1)=JH(KZ);
LA(IQ,JH(KZ),JJ(KZ),JI(KZ),2);
end;
end;
end
function LA(IQ,LB,KV,LC,JC)
IQ(KV)=IQ(LB);
IQ((LB+KV)/2)=0;
IQ(LB)=0;
IX(JC)=KV;
if ~IQ(KV+2) && IQ(KV+1)>0
LA(IQ,KV,KV+2,LC+IQ(KV+1),JC+1);
end
if ~IQ(KV-2) && IQ(KV-1)>0
LA(IQ,KV,KV-2,LC+IQ(KV-1),JC+1);
end
if ~IQ(KV+2*rows) && IQ(KV+rows)>0
LA(IQ,KV,KV+2*rows,LC+IQ(KV+rows),JC+1);
end
if ~IQ(KV-2*rows) && IQ(KV-rows)>0
LA(IQ,KV,KV-2*rows,LC+IQ(KV-rows),JC+1);
end
if LC>JF
JF=LC;
JG=JC;
IY(1:JC)=IX(1:JC);
end
end
function n=LE(IQ,LB,KV,n)
LF=IQ((LB+KV)*0.5);
if LF>0 && ~IQ(KV) && IQ(LB)>0
n=n+1;
if sum(IQ([KV+1 KV-1 KV+rows KV-rows])>0)==1
IV(n)=LF-IQ(LB)-JB;
else
IV(n)=LF-IQ(LB);
end
IU(n)=LB;
IW(n)=KV;
end
end
function n=LL(IQ,KV,LB,n)
LM=(LB+KV)/2;
if IQ(LM)>0 && IQ(LB)>0
n=n+1;
if sum(IQ([KV+1 KV-1 KV+rows KV-rows])>0)==1
IV(n)=IQ(LM)-IQ(LB)-JB;
else
IV(n)=IQ(LM)-IQ(LB);
end
IU(n)=LB;
IW(n)=KV;
end
end
function [LO,LP,LQ]=JK(IQ)
LR=find(IQ>0);
LS=find(~IQ);
n=0;
if numel(LS)<numel(LR)
for LU=1:numel(LS)
i=LS(LU);
n=LL(IQ,i,i-2,n);
n=LL(IQ,i,i+2,n);
n=LL(IQ,i,i-rows*2,n);
n=LL(IQ,i,i+rows*2,n);
end
else
for LU=1:numel(LR)
i=LR(LU);
n=LE(IQ,i,i-2,n);
n=LE(IQ,i,i+2,n);
n=LE(IQ,i,i-rows*2,n);
n=LE(IQ,i,i+rows*2,n);
end
end
LO=IU(1:n);
LP=IV(1:n);
LQ=IW(1:n);
end
function [IQ,JH,JJ,JI]=KG(IQ,JX,JH,JJ,JI)
LB=JH(JX);
KV=JJ(JX);
LM=(LB+KV)/2;
IQ(KV)=IQ(LB);
IQ(LM)=0;
IQ(LB)=0;
MA=LB-LM;
if (abs(MA)==1)
MB=rows;
else
MB=1;
end
JJ(logical(JJ==KV))=0;
JJ(logical(JH==LB))=0;
JJ(logical(JH==LM))=0;
MD=find(JH==LB-MB);
JJ(MD(JJ(MD)==LB+MB))=0;
MD=find(JH==LB+MB);
JJ(MD(JJ(MD)==LB-MB))=0;
MD=find(JH==LB-MB-MA);
JJ(MD(JJ(MD)==LB+MB-MA))=0;
MD=find(JH==LB+MB-MA);
JJ(MD(JJ(MD)==LB-MB-MA))=0;
[JJ,MF]=sort(JJ,'descend');
JH=JH(MF);
JI=JI(MF);
MG=find(~JJ,1,'first');
JH=JH(1:MG-1);
JI=JI(1:MG-1);
JJ=JJ(1:MG-1);
n=0;
n=LE(IQ,LB-3*MA,LB-MA,n);
n=LE(IQ,LB+2*MB-MA,LB-MA,n);
n=LE(IQ,LB+2*MB,LB,n);
n=LE(IQ,LB+2*MA,LB,n);
n=LE(IQ,LB-2*MB,LB,n);
n=LE(IQ,LB-2*MB-MA,LB-MA,n);
n=LE(IQ,KV,KV-2*MA,n);
n=LE(IQ,KV,KV-2*MB,n);
n=LE(IQ,KV,KV+2*MB,n);
clf=LB-MB-2*MA;
MK=LB+MB-2*MA;
if ~IQ(clf)
n=LE(IQ,MK,clf,n);
end
if ~IQ(MK)
n=LE(IQ,clf,MK,n);
end
if (n>0)
if (MG>1)
JH=[JH;IU(1:n)];
JJ=[JJ;IW(1:n)];
JI=[JI;IV(1:n)];
else
JH=IU(1:n);
JI=IV(1:n);
JJ=IW(1:n);
end
end
end
end
function [AA,MB]=HE( ...
AD,...
ML,...
MM,...
EV,EZ,FB,...
CK,...
FX,GB,GD,...
FJ,FK,FL)
MN=MM*rand(5000,1);
AA=zeros(CK-1,4);
MQ=zeros(CK-1,1);
MR=~AD;
MV=AD>0;
MX=max(AD,0);
MZ=(MV(EV) & MR(EZ) & MV(FB));
NA=find(MZ);
NB=AD(FB(NA))-AD(EV(NA));
if ML
CV=max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2);
else
CV=0;
end
[MB,HH]=max( (1+MN(1:length(NB))).*(NB+CV*ML) );
MQ(1)=NB(HH);
HH=NA(HH);
AA(1,:)=GD(HH,:);
ND=EZ(HH);
NE=EV(HH);
NF=FB(HH);
BN=2;
MX(ND)=AD(NE);
MX(NE)=0;
MX(NF)=0;
AD(ND)=AD(NE);
MR(ND)=false;
MV(ND)=true;
AD(NE)=0;
MR(NE)=true;
MV(NE)=false;
AD(NF)=0;
MV(NF)=false;
MR(NF)=true;
NI=[NE NF ND];
NJ=FJ(NI,:);
NJ=NJ(NJ>0);
NK=FK(NI,:);
NK=NK(NK>0);
NL=FL(NI,:);
NL=NL(NL>0);
NM=[NJ;NK;NL];
MZ(NM)=MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM));
NA=find(MZ);
while ~isempty(NA)
if (numel(NA)>1)
NO=find(EV(NA)==ND);
if ~isempty(NO)
NA=NA(NO);
NB=AD(FB(NA));
else
NB=AD(FB(NA))-AD(EV(NA));
end
if ML
CV=max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2);
else
CV=0;
end
[MB,HH]=max( (1+MN(1:length(NB))).*(NB+CV*ML) );
MQ(BN)=NB(HH);
HH=NA(HH);
else
HH=NA(1);
MQ(BN)=AD(FB(HH))-AD(EV(HH));
end
AA(BN,:)=GD(HH,:);
ND=EZ(HH);
NE=EV(HH);
NF=FB(HH);
BN=BN+1;
MX(ND)=AD(NE);
MX(NE)=0;
MX(NF)=0;
AD(ND)=AD(NE);
MR(ND)=false;
MV(ND)=true;
AD(NE)=0;
MR(NE)=true;
MV(NE)=false;
AD(NF)=0;
MV(NF)=false;
MR(NF)=true;
NI=[NE NF ND];
NJ=FJ(NI,:);
NJ=NJ(NJ>0);
NK=FK(NI,:);
NK=NK(NK>0);
NL=FL(NI,:);
NL=NL(NL>0);
NM=[NJ;NK;NL];
MZ(NM)=MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM));
NA=find(MZ);
end
MQ=cumsum(MQ);
[MB,BN]=max(MQ);
AA=AA(1:BN,:);
end
function [AA,MB]=GJ( ...
AD,...
EV,EZ,FB,...
CK,...
FX,GB,GD,GH,...
FJ,FK,FL)
AA=zeros(CK-1,4);
MQ=zeros(CK-1,1);
MR=~AD;
MV=AD>0;
MX=max(AD,0);
NX=(MV(EV) & MR(EZ) & MV(FB));
NA=find(NX);
NB=AD(FB(NA))-AD(EV(NA));
[CV,NY]=max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2);
[MB,HH]=max(NB+CV);
MQ(1)=NB(HH);
HH=NA(HH);
AA(1,:)=GD(HH,:);
NE=EV(HH);
BN=2;
ND=EZ(HH);
NI=[NE FB(HH) ND];
NF=FB(HH);
MX(ND)=AD(NE);MX(NE)=0;MX(NF)=0;
AD(ND)=AD(NE);
MR(ND)=false;
MV(ND)=true;
AD(NE)=0;
MR(NE)=true;
MV(NE)=false;
AD(NF)=0;
MV(NF)=false;
MR(NF)=true;
NJ=FJ(NI,:);
NJ=NJ(NJ>0);
NK=FK(NI,:);
NK=NK(NK>0);
NL=FL(NI,:);
NL=NL(NL>0);
NM=[NJ;NK;NL];
NX(NM)=MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM));
NA=find(NX);
while ~isempty(NA)
NO=find(EV(NA)==ND);
if ~isempty(NO)
NA=NA(NO);
NB=AD(FB(NA));
else
NB=AD(FB(NA))-AD(EV(NA));
end
[CV,NY]=max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2);
[MB,HH]=max(NB+CV);
MQ(BN)=NB(HH);
cv=CV(HH);NY=NY(HH);
HH=NA(HH);
AA(BN,:)=GD(HH,:);
NE=EV(HH);
BN=BN+1;
if ~cv
ND=EZ(HH);
NI=[NE FB(HH) ND];
else
ND=FX(HH,NY);
NF=GB(HH,NY);
AA(BN,:)=GH{NY}(HH,:);
NI=[NE FB(HH) NF ND];
MQ(BN)=cv;
AD(NF)=0;MR(NF)=true;MV(NF)=false;MX(NF)=0;
BN=BN+1;
end
NF=FB(HH);
MX(ND)=AD(NE);MX(NE)=0;MX(NF)=0;
AD(ND)=AD(NE);
MR(ND)=false;
MV(ND)=true;
AD(NE)=0;
MR(NE)=true;
MV(NE)=false;
AD(NF)=0;
MV(NF)=false;
MR(NF)=true;
NJ=FJ(NI,:);
NJ=NJ(NJ>0);
NK=FK(NI,:);
NK=NK(NK>0);
NL=FL(NI,:);
NL=NL(NL>0);
NM=[NJ;NK;NL];
NX(NM)=MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM));
NA=find(NX);
end
MQ=cumsum(MQ);
[MB,BN]=max(MQ);
AA=AA(1:BN,:);
end
|
