//Dennis for SER2014 - Knight Moves #include #include using namespace std; const int MAXINT = 2147483647; const int MAZESIZE = 100; const int WALL = -1; int maze[MAZESIZE][MAZESIZE]; pair start, finish; void getMaze(int maze[][MAZESIZE], int rows, int cols) { string str; for (int r = 0; r> str; for (int c = 0; c < cols; c++) { maze[r][c] = MAXINT; if (str[c] == '#') maze[r][c] = WALL; else if (str[c] == 'K') start = make_pair(r, c); else if (str[c] == 'X') finish = make_pair(r, c); } } } //next step int goMaze(int maze[][MAZESIZE], int rows, int cols, int path = 0, int rowstart = 0, int colstart = 0, int minpath = MAXINT) { if (colstart >= cols || rowstart >= rows || colstart<0 || rowstart<0 || //out of bounds maze[rowstart][colstart] == WALL || //wall path >= minpath || //a shorter path already found path >= maze[rowstart][colstart]) return minpath; //a shorter path was already found for this location, back away! if (rowstart == finish.first && colstart == finish.second) //reached the end of maze { if (path= 2500) return path; //must not be more than that really.. preventing stack overflow, plus can't have more than that I presume minpath = goMaze(maze, rows, cols, path + 1, rowstart + 1, colstart + 2, minpath); minpath = goMaze(maze, rows, cols, path + 1, rowstart + 1, colstart - 2, minpath); minpath = goMaze(maze, rows, cols, path + 1, rowstart - 1, colstart - 2, minpath); minpath = goMaze(maze, rows, cols, path + 1, rowstart - 1, colstart + 2, minpath); minpath = goMaze(maze, rows, cols, path + 1, rowstart + 2, colstart + 1, minpath); minpath = goMaze(maze, rows, cols, path + 1, rowstart + 2, colstart - 1, minpath); minpath = goMaze(maze, rows, cols, path + 1, rowstart - 2, colstart + 1, minpath); minpath = goMaze(maze, rows, cols, path + 1, rowstart - 2, colstart - 1, minpath); //cout << rowstart << " " << colstart << endl; return minpath; } int main() { int row, col; cin >> row >> col; getMaze(maze, row, col); int ret = goMaze(maze, row, col, 0, start.first, start.second); if (ret == MAXINT || ret == 2500) ret = -1; cout << ret << endl; return 0; } /* 4 7 K...... #...... #.#.... #.....X 5 4 K... .... .#.. .#.. ...X */ //How: simple recursion with some bounding.