Help:=proc():  print(`W(a,b), Wt(HorizA,VertA,,DiagA,w)`):
print(`BPb(HorizA,VertA,DiagA,a,b), `):
print(`BP1(HorizA,VertA,DiagA, a,b) `):
print(`BP(L1,L2,L3, a,b)`):
end:

#W(a,b): The set of walks from [0,0] to [a,b]
#that a forward-moving Chess King can go from
#[0,0] to [a,b]
W:=proc(a,b) local S1,S2,S3,i:
option remember:

if a=0 then
 RETURN({ [seq([0,i],i=0..b) ]}):
elif b=0 then
RETURN({ [seq([i,0],i=0..a) ]}):
fi:

S1:=W(a,b-1):
S2:=W(a-1,b):
S3:=W(a-1,b-1):


 {seq([op(S1[i]),[a,b]],i=1..nops(S1)),
seq([op(S2[i]),[a,b]],i=1..nops(S2)),
seq([op(S3[i]),[a,b]],i=1..nops(S3))
}:



end:



#Wt(HorizA,VertB,DiagA,w): Given the Horiz. and Vertical 
#and Diagonal attraction
#tables (given as lists of lists, 
#where HorizA[i][j] is
#the number of attractions between [i-1,j-1] to [i-1,j]
#where VertA[i][j] is
#the number of attractions between [i-1,j-1] to [i,j-1]
#and DiagA[i][j] is the number of attractions along
#the diagonal from [i-1,j-1] to [i,j]
Wt:=proc(HorizA,VertA,DiagA,w) local c,i,w1,pt1,pt2:

if w=[[0,0]] then
 RETURN(0):
fi:

w1:=[op(1..nops(w)-1,w)]:
c:=Wt(HorizA,VertA,DiagA,w1):


pt1:=w[nops(w)-1]:
pt2:=w[nops(w)]:

if pt1[2]=pt2[2] then
 RETURN(c+ HorizA[pt1[1]+1][pt1[2]+1]):
elif pt1[1]=pt2[1] then
RETURN(c+ VertA[pt1[1]+1][pt1[2]+1]):


elif pt2[1]-pt1[1]=1 and pt2[2]-pt1[2]=1 then
  RETURN(c+ DiagA[pt1[1]+1][pt1[2]+1]):
   
  
fi:
end:

 #BPb(HorizA,VertA,DiagA,a,b): The best path from [0,0] to [a,b]
#given the Attraction Lists HorizA, VertA
BPb:=proc(HorizA,VertA,DiagA,a,b)
local S,champ,rec,i,wt1,cand :
S:=W(a,b):

champ:=S[1]:
rec:=Wt(HorizA,VertA,DiagA, S[1]):

for i from 2 to nops(S) do

cand:=S[i]:
wt1:=Wt(HorizA,VertA,DiagA,S[i]):

if wt1>rec then
  rec:=wt1:
  champ:=cand:
fi:
od:

RETURN(champ,rec):
end:

#BP1(L1,L2,L3,a,b): Best (highest weight) path from
#[0,0] to [a,b] (with unit steps, horiz.,vert.,
#and diag.) with weights given
#by L1 (number of attractions in the horiz. direction)
# and L2("            vert. ")
#and L3 (" diag. ")
#followed by its score

BP1:=proc(L1,L2,L3,a,b) local Lchamp, Dchamp,
Dichamp,Direc,Lrec, Drec,tem,champ,rec:

option remember:

if a=0 then 
RETURN(W(0,b)[1],Wt(L1,L2,L3,W(0,b)[1])):
elif b=0 then
  
RETURN(W(a,0)[1],Wt(L1,L2,L3,W(a,0)[1])):
fi:

 tem:=BP1(L1,L2,L3,a-1,b):
 Lchamp:=tem[1]: Lrec:=tem[2]:
 Lchamp:=[op(Lchamp),[a,b]]:
 Lrec:=Lrec+L1[a][b+1]:


tem:=BP1(L1,L2,L3,a,b-1):
 Dchamp:=tem[1]: Drec:=tem[2]:
 Dchamp:=[op(Dchamp),[a,b]]:
 Drec:=Drec+L2[a+1][b]:

 if Drec>Lrec then
  champ:=Dchamp:
  rec:=Drec:
 else
   champ:=Lchamp:
   rec:=Lrec:
 fi:

tem:=BP1(L1,L2,L3,a-1,b-1):
 Dichamp:=tem[1]: Direc:=tem[2]:
 Dichamp:=[op(Dichamp),[a,b]]:
 Direc:=Direc+L3[a][b]:
 if Direc>rec then
   rec:=Direc:
   champ:=Dichamp:
 fi:


 champ,rec: 

end:




   BP:=proc(L1,L2,a,b)
     local i,j:
      for i from 0 to a do
       for j from 0 to b do
         BP1(L1,L2,i,j):
       od:
       od:
BP1(L1,L2,a,b):

end: