/* 3xn grid walks starting in the lower left corner.*/
/*
Chad Brewbaker
2-18-2003

Current output is:

1,3,8,17,38,78,164,333,680,1368,2768,5552,11204,22369

VS NJAS

1,3,8,17,38,78,164,332,680,1368,2768,5552,11168,22368

*/



#include <iostream>

#define UP '^'
#define RIGHT '>'
#define DOWN 'v'
#define LEFT '<'
#define EMPTY '#'

/*
SAMPLE GRID:
v < < < < < < < < v < v < 
> > > > > > > # ^ < ^ < ^ 
> > > > > > > > > > > > ^ 
*/





char GRID[3][20];
int COLS;
int PATH_NUM;



void printPath()
{   
  int i,j;
  cout <<"\n";
  for(i=2;i>=0;i--)
    {   
      cout <<"\n";
      for( j=0;j<COLS;j++)
	cout <<GRID[i][j]<<" ";
    }   
}

void pathSearch(int y,int x,int length)
{
  if(length==(COLS*3))
    {printPath();PATH_NUM++;return;}

  /*Do a depth first search on the grid going up, right, down, and left.*/

  //UP
  if(y<3)
    {
      if(GRID[y+1][x]==EMPTY)
	{
	  GRID[y][x]=UP;//Write to grid
	  pathSearch(y+1,x,length+1);
	  GRID[y][x]=EMPTY;//Clean up
	}
    }

  //RIGHT
  if(x<(COLS-1))
    {
      if(GRID[y][x+1]==EMPTY)
	{
	  GRID[y][x]=RIGHT;
	  pathSearch(y,x+1,length+1);
	  GRID[y][x]=EMPTY;
	}
    }
  //DOWN
  if(y>0) 
    {
      if(GRID[y-1][x]==EMPTY)
	{
	  GRID[y][x]=DOWN;
	  pathSearch(y-1,x,length+1);
	  GRID[y][x]=EMPTY;
	}
    }
  //LEFT
  if(x>0)
    {
      if(GRID[y][x-1]==EMPTY)
	{
	  GRID[y][x]=LEFT;
	  pathSearch(y,x-1,length+1);
	  GRID[y][x]=EMPTY;
	}
    }
  return;
}


int main()
{
  int i,j;
  cout << "\nHow many colums do you want?\n";
  cin >> COLS;
  if(COLS>20 || COLS<1)
    {
      cout << "\nNeed 1-20 for your column numbers\n";
      return 1;
    }
  for(i=0;i<3;i++)
    {
      for(j=0;j<COLS;j++)
        {
	  GRID[i][j]=EMPTY;
        }
    }
  PATH_NUM=0;
  //Start in the lower left hand corner....
  pathSearch(0,0,1);
  cout <<"\nThe number of paths found was:"<< PATH_NUM<<"\n";
  return 0;
}