#include <bits/stdc++.h>

using namespace std;

#define LOG_PATH 1;
#define ARRAY_BASED_CONSTANT_GRID 1;

struct Cell {
	int x,y;
};

const int HORIZONTAL_DIRECTION = 0, VERTICAL_DIRECTION = 1;

long long validPathCount, recursiveCallCount, visitedCellCount, currentDirection;

#ifdef ARRAY_BASED_CONSTANT_GRID
	const int DIMENSION = 7;
	bool grid[DIMENSION][DIMENSION];
#else
	int DIMENSION;
	vector<vector<bool>> grid;
#endif



/* *-*-*-*-*-*-*-*- UTILITY FUNCTIONS -*-*-*-*-*-*-*-*-*-*-*-*-*-* */
bool hasPathCompleted(Cell);
bool isPathValid();
void validPathCheckAndUpdate();

void setState(Cell);
void resetState(Cell);

void updateAndLogPathCounter();
void backtrackPathSearching(Cell);
void moveAlongTheGrid(Cell);
bool isOccupied(Cell);

bool canMoveRight(Cell);
bool canMoveLeft(Cell);
bool canMoveUp(Cell);
bool canMoveDown(Cell);

bool isRightBorder(Cell);
bool isLeftBorder(Cell);
bool isUpBorder(Cell);
bool isDownBorder(Cell);

Cell generateRight(Cell);
Cell generateLeft(Cell);
Cell generateUp(Cell);
Cell generateDown(Cell);

bool isThereHorizontalPartition();
bool isThereVerticalPartition();

void printGrid();
/* *-*-*-*-*-*-*-*- UTILITY FUNCTIONS -*-*-*-*-*-*-*-*-*-*-*-*-*-* */

Cell generateRight(Cell position) { 
	currentDirection = HORIZONTAL_DIRECTION;
	return {position.x, position.y + 1};
}
Cell generateLeft(Cell position) { 
	currentDirection = HORIZONTAL_DIRECTION;
	return {position.x, position.y - 1};
}
Cell generateUp(Cell position) { 
	currentDirection = VERTICAL_DIRECTION;
	return {position.x - 1, position.y};
}
Cell generateDown(Cell position) { 
	currentDirection = VERTICAL_DIRECTION;
	return {position.x + 1, position.y};
}

bool isRightBorder(Cell position) { return position.y == DIMENSION - 1; }
bool isLeftBorder(Cell position) { return position.y == 0; }
bool isUpBorder(Cell position) { return position.x == 0; }
bool isDownBorder(Cell position) { return position.x == DIMENSION - 1; }

bool isOccupied(Cell position) { return grid[position.x][position.y]; }

bool canMoveRight(Cell position) { return !isRightBorder(position) && !isOccupied(generateRight(position)); }
bool canMoveLeft(Cell position) { return !isLeftBorder(position) && !isOccupied(generateLeft(position)); }
bool canMoveUp(Cell position) { return !isUpBorder(position) && !isOccupied(generateUp(position)); }
bool canMoveDown(Cell position) { return !isDownBorder(position) && !isOccupied(generateDown(position)); }

bool hasPathCompleted(Cell position) { return position.x == DIMENSION - 1 && position.y == DIMENSION - 1; }

bool isPathValid() { return visitedCellCount == DIMENSION * DIMENSION; }

void validPathCheckAndUpdate() {
	if (isPathValid()) { updateAndLogPathCounter(); }
}

void updateAndLogPathCounter() {
	validPathCount++;
	#ifdef LOG_PATH
	cout << "\rFound " << validPathCount << " paths";
	cout.flush();
	#endif
}

void setState(Cell position) {
	recursiveCallCount++;
	visitedCellCount++;
	grid[position.x][position.y] = true;
}

void resetState(Cell position) {
	visitedCellCount--;
	grid[position.x][position.y] = false;
}

void printGrid() {
	cout << "-------------------------------" << endl;
	for (int i = 0; i < DIMENSION; i++) {
		for (int j = 0; j < DIMENSION; j++) {
			cout << grid[i][j] << " ";
		}
		cout << endl;
	}
}

void moveAlongTheGrid(Cell position) {
	if (canMoveRight(position)) {
		backtrackPathSearching(generateRight(position));
	}

	if (canMoveLeft(position)) {
		backtrackPathSearching(generateLeft(position));
	}

	if (canMoveUp(position)) {
		backtrackPathSearching(generateUp(position));
	}

	if (canMoveDown(position)) {
		backtrackPathSearching(generateDown(position));
	}
}

bool isThereHorizontalPartition(Cell position) {
	if (currentDirection == VERTICAL_DIRECTION) {
		if (!canMoveUp(position) && !canMoveDown(position)) {
			if (canMoveLeft(position) && canMoveRight(position)) {
				return true;
			}
		}
	}
	return false;
}

bool isThereVerticalPartition(Cell position) {
	if (currentDirection == HORIZONTAL_DIRECTION) {
		if (!canMoveLeft(position) && !canMoveRight(position)) {
			if (canMoveUp(position) && canMoveDown(position)) {
				return true;
			}
		}
	}
	return false;
}

// OPTIMIZATION : 4 > Direction awareness
// Optimization 3 followed border awareness but this concept can be generalized 
// and we can make the grid aware of its direction
// If path can't go forward in current direction but either can turn into both cross axis path
// then there is partition
void backtrackPathSearching(Cell position) {	
	setState(position);

	// printGrid();
	// cout << "x : " << position.x << " y : " << position.y << endl;
	// cout << "validPathCount : " << validPathCount << endl;
	// string s;
	// getline(cin, s);

	if (hasPathCompleted(position)) {
		validPathCheckAndUpdate();
	}
	else if (!isThereHorizontalPartition(position) && !isThereVerticalPartition(position)) {
		moveAlongTheGrid(position);
	}

	resetState(position);
}

#ifndef ARRAY_BASED_CONSTANT_GRID
	void inputFromUser() {
		cout << "Give Dimension of box grid : ";
		cin >> DIMENSION;

		for (int i = 0; i < DIMENSION; i++) grid.push_back(vector<bool>(DIMENSION, false));
	}
#endif

int main() {
	#ifndef ARRAY_BASED_CONSTANT_GRID
		inputFromUser();
	#endif

	validPathCount = recursiveCallCount = 0;
	visitedCellCount = 1;
	grid[0][0] = 1;
	currentDirection = VERTICAL_DIRECTION;

	backtrackPathSearching({1, 0});

	cout << endl;
	cout << "Paths : " << validPathCount * 2 << endl;
	cout << "Calls : " << recursiveCallCount << endl;
	return 0;
}

/*
Paths : 111712
Calls : 26790463

real	0m0.281s
user	0m0.281s
sys	0m0.000s
*/