#include <stdio.h>

#define TRUE 1
#define FALSE 0

int brukt[11][11];
int best_losning;
int h_dim, v_dim;
int start_h_dim,start_plass,slutt_plass,ant_rette,ant_sving;
int ant_brukt;


main()
{
 FILE *fp,*fp1;
 void dybde_foerst();
 int vegg;
 int i,j,k;
 int ant_rep;

 fp = fopen("infil.B","r");
 fp1 = fopen("utfil.B","w");

 fscanf(fp,"%d ",&ant_rep);

 for(k=1;k<=ant_rep;k++) {

   best_losning = 0;
   ant_brukt = 0;

   fscanf(fp,"%d %d",&h_dim,&v_dim);
   fscanf(fp,"%d %d",&start_plass,&slutt_plass);
   fscanf(fp,"%d %d",&ant_rette, &ant_sving);

/* Nummererer veggene 0-Opp 1-Høyre 2-Ned 3-Venstre */

/* Setter at ingen vegger er brukt */
   for(i=1;i<=h_dim;i++)
     for(j=1;j<=v_dim;j++)
       brukt[i][j] = FALSE;

/* Kaller opp rekursiv rutine som gjør dybde-først søk */

   vegg = 2;                           /*setter hvilken vegg vi kommer ifra */
   dybde_foerst(start_plass,1,vegg);

   fprintf(fp1,"Module %d: ",k);
   if (best_losning > 0)
     fprintf(fp1,"Longest railroad has %d rails.\n",best_losning);
   else
     fprintf(fp1,"No such railroad.\n");
 }
}

void dybde_foerst(rute_h,rute_v,vegg)
int rute_h,rute_v,vegg;
{
 int ny_vegg;
 int ny_h,ny_v;
 int kan_gaa_videre();
 int inn_vegg;
 int i,j;

 brukt[rute_h][rute_v] = TRUE;

/* Sjekker om vi kan gå rett frem */

 if (ant_rette > 0) {
   ant_rette--;
   ant_brukt++;

/*Regner ut hvilken vegg vi går ut igjennom */
   ny_vegg = (vegg + 2) % 4; 

   if (kan_gaa_videre(ny_vegg,rute_h,rute_v,&ny_h,&ny_v)) {

/* Hvis vi kunne gå videre må regner vi ut 
   hvilken vegg vi kommer inn gjennom i den nye ruten */

     inn_vegg = (ny_vegg + 2) % 4;
     dybde_foerst(ny_h,ny_v,inn_vegg); }
   else {

/* Sjekk om vi er fremme ved sluttpunktet */
     sjekk_maal(ny_vegg,rute_h,rute_v);
   }
   ant_rette++;
   ant_brukt--;
 }


/* Sjekker om vi kan gå til venstre */
 if (ant_sving > 0) {
   ant_sving--;
   ant_brukt++;
   ny_vegg = (vegg + 1) % 4;
   if (kan_gaa_videre(ny_vegg,rute_h,rute_v,&ny_h,&ny_v)) {
     inn_vegg = (ny_vegg + 2) % 4;
     dybde_foerst(ny_h,ny_v,inn_vegg);
   }
   else {
     sjekk_maal(ny_vegg,rute_h,rute_v);
   }
 
/* Sjekker om vi kan gå til høyre */

   ny_vegg = (vegg + 3) % 4;
   if (kan_gaa_videre(ny_vegg,rute_h,rute_v,&ny_h,&ny_v)) {
     inn_vegg = (ny_vegg + 2) % 4;
     dybde_foerst(ny_h,ny_v,inn_vegg); }
   else {
     sjekk_maal(ny_vegg,rute_h,rute_v);
   }
   ant_sving++;
   ant_brukt--;
 }

/* Nå er vi ferdig med ruten, sett den til ledig */
 brukt[rute_h][rute_v] = FALSE;

}

int kan_gaa_videre(ny_vegg,rute_h,rute_v,ny_h,ny_v)
int ny_vegg,rute_h,rute_v;
int *ny_h,*ny_v;
{
/* Vil gå ut gjennom vegg nr "ny_vegg", fra rute (rute_h,rute_v).
   Må sjekke at vi ikke går utenfor modulen og at neste rute ikke
   er i bruk. Regner også ut koordinatene til neste rute (ny_h,ny_v)
*/

/* Sjekker om vi kan gå oppover */
 if (ny_vegg == 0 && rute_v < v_dim)
 {
   *ny_v = rute_v+1;
   *ny_h = rute_h;
   if (brukt[*ny_h][*ny_v] == FALSE)
     return(TRUE);
   else
     return(FALSE);
 }

/* Sjekker om vi kan gå nedover */
 if (ny_vegg == 2 && rute_v > 1)
 {
   *ny_v = rute_v-1;
   *ny_h = rute_h;
   if (brukt[*ny_h][*ny_v] == FALSE)
     return(TRUE);
   else
     return(FALSE);
 }

/* Sjekker om vi kan gå til høyre */
 if (ny_vegg == 3 && rute_h > 1)
 {
   *ny_v = rute_v;
   *ny_h = rute_h-1;
   if (brukt[*ny_h][*ny_v] == FALSE)
     return(TRUE);
   else
     return(FALSE);
 }

/* Sjekker om vi kan gå til venstre */
 if (ny_vegg == 1 && rute_h < h_dim)
 {
   *ny_v = rute_v;
   *ny_h = rute_h+1;
   if (brukt[*ny_h][*ny_v] == FALSE)
     return(TRUE);
   else
     return(FALSE);
 }
 return(FALSE);
}


int sjekk_maal(vegg,rute_h,rute_v)
int vegg,rute_h,rute_v;
{
 if ((vegg == 0) && (rute_h == slutt_plass) && (rute_v == v_dim))
 { 
   if (ant_brukt > best_losning)
     best_losning = ant_brukt;
 }
}