自動車給油走行問題(car)

program car;

const
 maxn=100;
 maxoil=12;

var
 n,go,cost,gocost,build:longint;
 map:array [0..maxn,0..maxn] of longint;{map[i,j]         。}
 work:array [0..maxn,0..maxn,0..maxoil] of longint;{}
 s:array [0..4,0..3] of longint;{s     ，           ，               。}

procedure init;
var
 i,j:longint;
begin
 readln(n,go,cost,gocost,build);
 for i:=0 to n-1 do
  begin
   for j:=0 to n-1 do read(map[i,j]);
   readln;
  end;
 s[0,0]:=-1;
 s[0,1]:=0;
 s[0,2]:=0;
 s[1,0]:=0;
 s[1,1]:=-1;
 s[1,2]:=0;
 s[2,0]:=1;
 s[2,1]:=0;
 s[2,2]:=gocost;
 s[3,0]:=0;
 s[3,1]:=1;
 s[3,2]:=gocost;
end;

procedure main;
var
 i,y,j,p,q,min,x:longint;
begin
 fillchar(work,sizeof(work),100);{          。}
 for i:=0 to go do work[0,0,i]:=0;
 y:=1;
 while y<>0 do
  begin
   y:=0;
   for i:=0 to n-1 do
    begin
     for j:=0 to n-1 do
      begin
       if (i<>0) or (j<>0) then{     。}
        begin
         for p:=0 to go do{       。}
          begin
           min:=1000000;{      。}
           for q:=0 to 3 do
            begin
 	     {        。}
             if (i=0) and (q=0) then continue;
             if (j=0) and (q=1) then continue;
             if (i=n-1) and (q=2) then continue;
             if (j=n-1) and (q=3) then continue;
             if work[i+s[q,0],j+s[q,1],p+1]+s[q,2]min+cost*map[i,j] then inc(y);
             work[i,j,p]:=min;
             if map[i,j]=1 then
              begin
               inc(work[i,j,0],cost);
               for x:=1 to go do work[i,j,x]:=work[i,j,0];
               break;
              end;
            end
           else
            begin
             work[i,j,p]:=work[i,j,0]+cost+build;
             for x:=p+1 to go do work[i,j,x]:=work[i,j,p];
             break;
            end;
          end;
        end;
      end;
    end;
  end;
end;

begin
 assign(input,'car.in'); reset(input);
 assign(output,'car.out'); rewrite(output);

 init;
 main;
 writeln(work[n-1,n-1,0]);

 close(input); close(output);
end.