/* 
   3xn grid walks starting in the lower left corner.
   Chad Brewbaker
   Febuary 27, 2003

*/
#include <iostream.h>

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



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



void printPath()
{   
    cout <<"\n";
    for(i=0;i<3;i++)
        {   
        cout <<"\n";
        for( j=0;j<COLS;j++)
            cout <<" PATH[i][j]";
        }   
}

pathSearch(int x,int y,int length)
{
if(length==(COLS*3))
    printPath();
//UP
if(y<3)
{
    if(GRID[x][y+1]==NULL)
       {
        GRID[x][y]=UP;
        pathSearch(x,y+1,length+1)
        GRID[x][y]=NULL;
    }
}

//RIGHT
if(x<(COLS-1))
{
    if(GRID[x+1][y]==NULL)
    {
        GRID[x][y]=RIGHT;
        pathSearch(x+1,y,length+1)
        GRID[x][y]=NULL;
    }
}

//DOWN
if(y>0) 
{
    if(GRID[y-1][x]==NULL)
    {
        GRID[x][y]=DOWN;
        pathSearch(x,y-1,length+1)
        GRID[x][y]=NULL;
    }
}

//LEFT
if(x>0)
{
    if(GRID[x-1][y]==NULL)
    {
        GRID[x][y]=LEFT;
        pathSearch(x-1,y,length+1);
        GRID[x][y]=NULL;
    }
}

return;
}







int main()
{
int i,j,k;


cout << "\nHow many colums do you want?\n"

cin >> COLS;
if(COLS>20 || COLS<1)
    {
        cout << "\nNeed 1-20 for your column numbers\n"
        exit(1);
    }
for(i=0;i<3;i++)
    {
        for(j=0;j<COLS;j++)
        {
            GRID[i][j]=NULL;
        }
    }

PATH_NUM=0;
pathSearch(legnth);
cout <<"\nThe number of paths found was:"<< PATH_NUM<<"\n";
return 0;
}