// Hareesh Nagarajan // // 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 #include #include #include #include #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 &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 neighbors; vector::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; }