// Hareesh Nagarajan <hareesh AT symonds.net>
//
// In this variation, you cannot reuse a node that you've already picked
// E.g.
// {"AA",
// "AA"}
// Path: "AAAA"
// 4*3*2*1 = 24 and not 4*3*3*3 = 108

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cassert>
#define ROW_MAX		50
#define COL_MAX		50
#define PATH_STR_MAX 	(1<<10)
#define INF		100000
using namespace std;

typedef struct { int i, j; } point;

static inline void reset_visited(bool visited[ROW_MAX][COL_MAX], int rows, int cols)
{
	int i, j;
	for(i = 0; i < rows; i++) {
		for(j = 0; j < cols; j++) {
			visited[i][j] = false;
		}
	}
}

void get_neighbors(const char grid[ROW_MAX][COL_MAX], const int i, const int j,
		   const int rows, const int cols, vector<point> &vp)
{
	point p;
	bool i_minus_1 = false, i_plus_1 = false;
	bool j_minus_1 = false, j_plus_1 = false;
	
	if(i - 1 >= 0) i_minus_1 = true;
	if(i + 1 < rows) i_plus_1 = true;
	
	if(j - 1 >= 0) j_minus_1 = true;
	if(j + 1 < cols) j_plus_1 = true;

	if(i_minus_1) {
		p.i = i - 1; p.j = j; vp.push_back(p); 				//i-1, j
		if(j_minus_1) { p.i = i - 1; p.j = j - 1; vp.push_back(p); } 	//i-1, j-1
		if(j_plus_1) { p.i = i - 1; p.j = j + 1; vp.push_back(p); } 	//i-1, j+1
	}
	
	if(i_plus_1) {
		p.i = i + 1; p.j = j; vp.push_back(p); 				//i+1, j
		if(j_minus_1) { p.i = i + 1; p.j = j - 1; vp.push_back(p); } 	//i+1, j-1
		if(j_plus_1) { p.i = i + 1; p.j = j + 1; vp.push_back(p); } 	//i+1, j+1
	}
	
	if(j_minus_1) { p.i = i; p.j = j - 1; vp.push_back(p); } 		//i, j-1
	if(j_plus_1) { p.i = i; p.j = j + 1; vp.push_back(p); } 		//i, j+1
}

	

int compute(const char grid[ROW_MAX][COL_MAX], const char path[PATH_STR_MAX],
	    bool visited[ROW_MAX][COL_MAX], int &count,
	    int i, int j, int rows, int cols, int path_iter, const int path_sz)
{
	vector<point> neighbors;
	vector<point>::iterator iter;
	point p;
	
	if(path_iter >= path_sz) { count++; return 0; }
	if(count > INF) return 0;
	get_neighbors(grid, i, j, rows, cols, neighbors);

	for(iter = neighbors.begin(); iter < neighbors.end(); iter++) {
		p.i = iter->i;
		p.j = iter->j;
		if(grid[p.i][p.j] == path[path_iter]) {
			if(!visited[p.i][p.j]) {
				visited[p.i][p.j] = true;
				compute(grid, path, visited, count, p.i, p.j, rows, cols,
					path_iter + 1, path_sz);
				visited[p.i][p.j] = false;
			}
			
		}
	}

	return 0;
}


int search_paths(const char grid[ROW_MAX][COL_MAX], const char path[PATH_STR_MAX],
		 int rows, int cols, const int path_sz)
{
	int i, j, count;
	bool visited[ROW_MAX][COL_MAX];
 
	count = 0;

	for(i = 0; i < rows; i++) {
		for(j = 0; j < cols; j++) {
			if(grid[i][j] == path[0]) {
				reset_visited(visited, rows, cols);
				visited[i][j] = true;
				compute(grid, path, visited, count, i, j, rows, cols, 1, path_sz);
				if(count > INF)
					return -1;
			}
		}
	}
	return count;
}

main()
{
	char path[PATH_STR_MAX];
	int rows, cols, path_sz;

	char grid[ROW_MAX][COL_MAX] = {
		{'A', 'A'},
		{'A', 'A'}
	};
	strcpy(path, "AAAA");

	rows = 2;
	cols = 2;
	path_sz = strlen(path);

	assert(rows < ROW_MAX);
	assert(cols < COL_MAX);
	assert(path_sz < PATH_STR_MAX);

	cout << search_paths(grid, path, rows, cols, path_sz) << endl;
}