PROGRAM count_hamilton_paths;

{ straight counting algorithme,
  plain + optimizing on double ends.
  CONST trace = 'showing current board or not'
}

USES crt;

CONST
  trace = TRUE;
  size  = 30;
  sqsize = 900;
  sqsizem1 = 899;
  left  =  -1;
  right =   1;
  down  =  30;
  up    = -30;

TYPE t_field = ARRAY[0..sqsizem1] OF boolean;

VAR field  ,
    border : t_field;
    neighbour : ARRAY[0..sqsizem1] OF byte;
{   path   : ARRAY[0..sqsize] OF char; }
    gn,gm,maxdepth : integer;
    count ,
    total : longint;
    depth : integer;
    depth_count : ARRAY[1..sqsize] OF longint;
    result_file : TEXT;

PROCEDURE initialize_field(n,m : byte);
VAR i,j,c : word;
BEGIN
  FOR i := 0 TO sqsizem1
  DO BEGIN
       field[i] := FALSE;
       neighbour[i] := 0
     END;
  FOR i := 1 TO n
  DO FOR j := 1 TO m
     DO BEGIN
          field[i + size*j] := TRUE;
          c := 4;
          IF  i=1  THEN dec(c);
          IF  i=n  THEN dec(c);
          IF  j=1  THEN dec(c);
          IF  j=m  THEN dec(c);
          neighbour[i + size*j] := c
        END;
{ FOR i := 0 TO sqsizem1
  DO path[i] := ' '; }
  FOR i := 0 TO sqsizem1
  DO border[i] := FALSE;
  FOR i := 1 TO n
  DO BEGIN
       border[size+i] := TRUE;
       border[size*m+i] := TRUE
     END;
  FOR i := 1 TO m
  DO BEGIN
       border[1+i*size] := TRUE;
       border[n+i*size] := TRUE
     END;
END;

PROCEDURE show_field(x,y,pos: byte);
VAR i,j,p : integer;
    ch : char;
BEGIN
  FOR i := 0 TO gn+1
  DO FOR j := 0 TO gm+1
     DO BEGIN
          gotoxy(x+i SHL 2,y+j);
          p := i + size*j;
          IF   field[p]
          THEN write('.')
          ELSE write(' ');
          write(neighbour[p]);
          IF   pos = p
          THEN write('#')
          ELSE write(' ')
        END;
  gotoxy(1,20);
END;

PROCEDURE show_depth_count;
VAR i1,j1 : byte;
BEGIN
  gotoxy(1,1);
  writeln;
  FOR i1 := 1 TO gn
  DO BEGIN
       FOR j1 := 1 TO gm
       DO write(depth_count[i1 + size*j1]:8);
       writeln
     END;
  write(count);
END;


VAR no_border : boolean;
    bow : boolean;

PROCEDURE seek(pos : word; dir : integer);
VAR left_turn,right_turn : integer;
    ch : char;

  PROCEDURE check2(left_pos, left_dir, right_pos, right_dir : integer);
  BEGIN
{    gotoxy(1,21);
    clreol;
    write('check2 ',left_pos:3, left_dir:3, right_pos:3, right_dir : 3); }
    dec(neighbour[right_pos]);
    dec(neighbour[left_pos]);
{    show_field(2,2,pos);     }
    IF   bow
    THEN IF   neighbour[left_pos] = 1
         THEN IF   neighbour[right_pos] = 1
              THEN (* blocking *)
              ELSE seek(left_pos, left_dir)
         ELSE BEGIN
                seek(right_pos, right_dir);
                IF   neighbour[right_pos] > 1
                THEN seek(left_pos, left_dir)
              END
    ELSE BEGIN
           bow := neighbour[left_pos] = 1;
           seek(right_pos, right_dir);
           bow := neighbour[right_pos] = 1;
           seek(left_pos, left_dir);
           bow := FALSE;
         END;
    inc(neighbour[right_pos]);
    inc(neighbour[left_pos])
  END;

  PROCEDURE check3(pos_left_turn, pos_dir, pos_right_turn : word);
  BEGIN
{    gotoxy(1,21);
    clreol;
    write('check3 ',pos_left_turn:3, pos_dir:3, pos_right_turn:3);  }
    dec(neighbour[pos_right_turn]);
    dec(neighbour[pos_dir]);
    dec(neighbour[pos_left_turn]);
{    show_field(2,2,pos); }
    IF   bow
    THEN IF   neighbour[pos_left_turn] = 1
         THEN IF   neighbour[pos_right_turn] = 1
              THEN (* blocking *)
              ELSE BEGIN
                     seek(pos_dir, dir);
                     seek(pos_left_turn, left_turn);
                   END
         ELSE BEGIN
                seek(pos_right_turn, right_turn);
                IF   neighbour[pos_right_turn] > 1
                THEN BEGIN
                       seek(pos_dir, dir);
                       seek(pos_left_turn, left_turn);
                     END
              END
    ELSE IF   neighbour[pos_left_turn] = 1
         THEN IF   neighbour[pos_right_turn] = 1
              THEN BEGIN
                     bow := TRUE;
                     seek(pos_right_turn, right_turn);
                     seek(pos_left_turn, left_turn);
                     bow := FALSE
                   END
              ELSE BEGIN
                     bow := TRUE;
                     seek(pos_right_turn, right_turn);
                     seek(pos_dir, dir);
                     bow := FALSE;
                     seek(pos_left_turn, left_turn)
                   END
         ELSE IF   neighbour[pos_right_turn] = 1
              THEN BEGIN
                     seek(pos_right_turn, right_turn);
                     bow := TRUE;
                     seek(pos_dir, dir);
                     seek(pos_left_turn, left_turn);
                     bow := FALSE;
                   END
              ELSE BEGIN
                     seek(pos_right_turn, right_turn);
                     seek(pos_dir, dir);
                     seek(pos_left_turn, left_turn)
                   END;
    inc(neighbour[pos_right_turn]);
    inc(neighbour[pos_dir]);
    inc(neighbour[pos_left_turn])
  END;

BEGIN
  IF   keypressed
  THEN BEGIN
         ch := readkey;
         show_depth_count;
         IF   ch = 'Q'
         THEN BEGIN
                close(result_file);
                halt
              END
         ELSE IF  ch = 'C'
              THEN BEGIN
                     clrscr
                   END;
       END;
  IF   depth = maxdepth
  THEN BEGIN
         inc(count);
         inc(depth_count[pos]);
       END
  ELSE BEGIN
         inc(depth);
         field[pos] := FALSE;
         CASE dir OF
         right : BEGIN
                 {  path[pos-dir] := '>'; }
                   left_turn := up;
                   right_turn := down
                 END;
         left  : BEGIN
                 {  path[pos-dir] := '<';  }
                   left_turn := down;
                   right_turn := up
                 END;
         down  : BEGIN
                 {  path[pos-dir] := 'v';  }
                   left_turn := right;
                   right_turn := left
                 END;
         up    : BEGIN
                 {  path[pos-dir] := '^';  }
                   left_turn := left;
                   right_turn := right
                 END
         END;
         IF   no_border AND border[pos]
         THEN BEGIN
                no_border := FALSE;
                IF  field[pos + right] THEN dec(neighbour[pos + right]);
                IF  field[pos + left ] THEN dec(neighbour[pos + left ]);
                IF  field[pos + down ] THEN dec(neighbour[pos + down ]);
                IF  field[pos + up   ] THEN dec(neighbour[pos + up   ]);
                IF   field[pos + down ] THEN seek(pos + down , down );
                IF   field[pos + left ] THEN seek(pos + left , left );
                IF   field[pos + right] THEN seek(pos + right, right);
                IF   field[pos + up   ] THEN seek(pos + up   , up   );
                IF  field[pos + right] THEN inc(neighbour[pos + right]);
                IF  field[pos + left ] THEN inc(neighbour[pos + left ]);
                IF  field[pos + down ] THEN inc(neighbour[pos + down ]);
                IF  field[pos + up   ] THEN inc(neighbour[pos + up   ]);
                no_border :=  TRUE
              END
         ELSE
         IF   field[pos + dir]
         THEN IF   field[pos + right_turn]
              THEN IF   field[pos + left_turn]
                   THEN IF   field[pos + right_turn + dir]
                         AND field[pos + left_turn  + dir]
                        THEN check3(pos + left_turn, pos + dir,
                                    pos + right_turn)
                        ELSE (* blocking right/left ahead *)
                   ELSE IF   field[pos + right_turn + dir]
                        THEN check2(pos + right_turn, right_turn,
                                    pos + dir, dir)
                        ELSE (* blokking right ahead *)
              ELSE IF   field[pos + left_turn]
                   THEN IF   field[pos + left_turn + dir]
                        THEN check2(pos + left_turn, left_turn,
                                    pos + dir, dir)
                        ELSE (* blokking left ahead *)
                   ELSE seek(pos + dir, dir)
         ELSE IF   field[pos + right_turn]
              THEN IF   field[pos + left_turn]
                   THEN (* blokking straight *)
                   ELSE seek(pos + right_turn, right_turn)
              ELSE IF   field[pos + left_turn]
                   THEN seek(pos + left_turn, left_turn)
                   ELSE (* dead end *);
         field[pos] := TRUE;
         { path[pos-dir] := ' ';}
         dec(depth);
       END;
END;


PROCEDURE init_depth_count;
VAR i : word;
BEGIN
  FOR i := 1 TO sqsize DO depth_count[i] := 0;
END;

PROCEDURE print_depth_count(n,m,i,j : byte);
VAR i1,j1 : byte;
    c : byte;
    ch : char;
BEGIN
  IF  count > 0
  THEN BEGIN
         IF   n = m
         THEN IF   i = j
              THEN IF   2*i = n+1
                   THEN c := 1
                   ELSE c := 4
              ELSE IF   2*j = m+1
                   THEN c := 4
                   ELSE c := 8
         ELSE IF   2*i = n+1
              THEN IF   2*j = m+1
                   THEN c := 1
                   ELSE c := 2
              ELSE IF   2*j = m+1
                   THEN c := 2
                   ELSE c := 4;
         writeln(result_file, n:4,m:4,i:4,j:4,count:12,' * ',c,' = ',count*c);
         total := total + count * c;
         FOR i1 := 1 TO n
         DO BEGIN
              FOR j1 := 1 TO m
              DO write(result_file, depth_count[i1 + size*j1]:8);
              writeln(result_file)
            END;
         writeln(result_file)
       END;
END;

PROCEDURE seek_from_pos(n,m,i,j : byte);
VAR pos : word;
BEGIN
  gn := n;
  gm := m;
  clrscr;
  gotoxy(1,1);
  writeln('seek from ',n:3,m:3,i:3,j:3);
  count := 0;
  no_border := border[pos];
  init_depth_count;
  pos := i + size*j;
  no_border := NOT border[pos];
  field[pos] := FALSE;
  bow := FALSE;
  IF  field[pos + right] THEN dec(neighbour[pos + right]);
  IF  field[pos + left ] THEN dec(neighbour[pos + left ]);
  IF  field[pos + down ] THEN dec(neighbour[pos + down ]);
  IF  field[pos + up   ] THEN dec(neighbour[pos + up   ]);
  IF  i < n THEN seek(pos + right,right);
  IF  j < m THEN seek(pos + down ,down );
  IF  i > 1 THEN seek(pos + left ,left );
  IF  j > 1 THEN seek(pos + up   , up  );
  field[pos] := TRUE;
  IF  field[pos + right] THEN inc(neighbour[pos + right]);
  IF  field[pos + left ] THEN inc(neighbour[pos + left ]);
  IF  field[pos + down ] THEN inc(neighbour[pos + down ]);
  IF  field[pos + up   ] THEN inc(neighbour[pos + up   ]);
  print_depth_count(n,m,i,j);
END;

PROCEDURE count_for(n,m, si,sj : byte);
VAR i,j : byte;
    tn,tm : byte;
    not_both_odd : boolean;
BEGIN
  total := 0;
  maxdepth := n * m;
  initialize_field(n,m);
  count := 0;
  depth := 2;
  not_both_odd := NOT(odd(n) AND odd(m));
  tn := (n+1) DIV 2;
  tm := (m+1) DIV 2;
  IF  n = m
  THEN FOR i := 1 TO tn
       DO FOR j := i TO tm
          DO IF   ((i > si) OR ((i = si) AND (j >= sj)))
              AND (not_both_odd OR NOT odd(i+j))
             THEN seek_from_pos(n,m,i,j)
             ELSE
  ELSE FOR i := 1 TO tn
       DO FOR j := 1 TO tm
          DO IF   ((i > si) OR ((i = si) AND (j >= sj)))
             THEN seek_from_pos(n,m,i,j);
  writeln(result_file, 'total =', total DIV 2);
  writeln(result_file);
  writeln(result_file)
END;

VAR i : integer;
BEGIN
  clrscr;
  assign(result_file, 'result.dat');
  rewrite(result_file);
  count_for(4,11,1,1);
  count_for(4,12,1,1);
  count_for(4,13,1,1);
  count_for(4,15,1,1);
  count_for(4,16,1,1);
  count_for(4,17,1,1);
  count_for(4,18,1,1);
  count_for(6,9,1,1);  {54}
  count_for(7,8,1,1);  {56}
  count_for(6,10,1,1); {60}
  count_for(7,9,1,1);  {63}
  count_for(8,8,1,1);  {64}
  count_for(7,10,1,1); {70}
  count_for(8,9,1,1);  {72}
  count_for(8,10,1,1); {80}
  close(result_file)
END.