/* 
 Задание: Вычислить маршрут кубика nxn из начального положения A[1][1] в конечное положение A[1][n]. 
          Кубик не должен вставать на запрещенную сторону. Начально положение запрещенной стороны сверху. 
		  Кубик должен пройти все клетки матрицы, ступая на них только один раз. */

#include <stdio.h>
#include <conio.h>
#include <stdlib.h> 
#include <time.h>

void Rec(int i, int j, int s);
int n,c, a[101][101];


void main(void)
{
int i,j,k; 
clock_t start, end; float time;
printf("Enter n: \n");
scanf("%d",&n);
 for(j=0; j<n; j++)
	 for(k=0;k<n; k++)
		 a[j][k]=0;

  for (i=0; i<=n+1; i++)
      {
		  a[i][0] = -1;
		  a[i][n+1] = -1;
		  a[0][i] = -1;
		  a[n+1][i] = -1;
      }
	  c = 0; 
	    start = clock();
	    Rec(1, 1, 0);	
		end = clock(); 
        time=(end-start)/CLK_TCK;
        printf("No solution for n = %d \n", n);
		printf("\nTime is - %f",time);
	    getch();
}

void Rec(int i, int j, int s)
{ 
	clock_t start, end; float time;
	if (a[i][j] != 0) return;  
 c=c+1; //можно записать как ++c
 a[i][j]=c; // a[i][j] = 0 если еще не походили, либо равно номеру хода 
  
    if((i==1) && (j==n) && (c == n*n)) 
	  { 
		  for(i=1; i<=n; i++)
		  { 
			  for(j=1; j<=n; j++) printf( " %3d ",a[i][j]);
			  printf("\n");
		  }
          end = clock();
		  time=(end-start)/CLK_TCK;
		  printf("\n");
          printf("\nTime is - %f",time);
          getch();
		  exit(0);
	  } 

	
	  switch(s) { // s - положение запрещенной стороны 
		  case 0: // запрещенная сторона наверху  
			  Rec(i-1,j,1);
			  Rec(i,j-1,2);
			  Rec(i+1,j,3);
			  Rec(i,j+1,4);
			  break;
		  case 1: //запрещенная сторона сбоку сзади 
			  Rec(i+1,j,0); 
			  Rec(i,j-1,1);
			  Rec(i,j+1,1);
			  break;
		  case 2: //запрещенная сторона сбоку слева
			  Rec(i,j+1,0);
			  Rec(i-1,j,2);
			  Rec(i+1,j,2);
			  break;
		  case 3: // запрещенная сторона спереди 
			  Rec(i-1,j,0);
			  Rec(i,j-1,3);
			  Rec(i,j+1,3);
			  break;
		  case 4: // запрещенная сторона сбоку справа 
			  Rec(i,j-1,0);
			  Rec(i-1,j,4);
			  Rec(i+1,j,4);
			  break;
	  }
c=c-1; //можно написать --c
a[i][j]=0;

}