- 编程
寻宝游戏
-
wangkezhen1
LV 6
@
2025-4-8 19:31:09
题目大纲：
Betty小学的同学们要到白泉实践学校实践基地去实践，有一个游戏叫“寻宝游戏”。其中，你玩得最不亦乐乎。这些格子中，'@'表示你所在的位置，'#'表示障碍物，'.'表示空地，'$'表示宝藏。如果宝藏的数量不止一个，就挑选路程最短的宝藏。若宝藏找不到，则输出-1。
你可以走，可以往东、南、西、北、东北、东南、西北、西南八个方向走（这张地图按照上北下南左西右东制）。
当然，你也可以跳，但每次只能跳一格，只能往前跳，“前”定义为你刚刚跳的方向。如你刚刚往西北走，那你不能往东、南、西、北、东北、东南、西南跳，也不能往西北跳两格以上，只能跳一格。
特别地，你在原来的位置的时候，只能走，不能往任何方向跳。
如图所示（此图为12*12的寻宝地图中的截图）：
跳之前：
$.##
.###
###.
##@.
跳之后：
$.##
@###
###.
###.
值得一提的是，你走过或跳过的地方会留下一个障碍物，所以无法原路返回。
输入格式：
第一行两个整数n和m，分别表示白泉实践学校的长度和宽度。
接下来n行，每行m个字符，表示每一格土地的属性。
输出格式：
若找得到宝藏，第一行若干次，每次两个整数，中间用逗号隔离，两边用圆括号隔离，若非最后一个，后面有箭头“->”，表示小A的寻宝路线（确保小A方向感很好，走的路线一定是最短的）。
第二行（若找不到宝藏，仍要换行），一个整数，表示拿到宝藏的最短路程。
样例输入#1：
7 7
..@.#.$
.####.#
.#.$#..
.##...#
..###.#
#..#..#
##...##
样例输出#1：
(1,3)->(1,2)->(2,1)->(3,1)->(5,1)->(6,2)->(7,3)->(7,4)->(6,5)->(5,6)->(4,5)->(3,4)
11
样例输入#2：
4 4
@..#
.###
##..
.#..
样例输出#2
-1
数据范围：
对于100%的数据，确保1<=n,m<=50。
注意！！！
为了公平起见，所有路线的路程均不相等。
@所有算法课在读的小学生。
#已纠正题目中可能存在的错误
1 条评论
-
wangkezhen1 LV 6 @ 2025-5-18 16:40:48
AI代码： #include #include #include #include #include using namespace std;
const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; // 8个方向：北、东北、东、东南、南、西南、西、西北 const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
struct State { int x, y; int steps; int last_dir; // -1表示初始状态，0-7表示8个方向 vector<pair<int, int>> path; };
int main() { int n, m; cin >> n >> m; vector grid(n); int start_x = -1, start_y = -1;
for (int i = 0; i < n; ++i) { cin >> grid[i]; for (int j = 0; j < m; ++j) { if (grid[i][j] == '@') { start_x = i; start_y = j; } } } queue<State> q; q.push({start_x, start_y, 0, -1, {{start_x, start_y}}}); vector<vector<vector<int>>> visited(n, vector<vector<int>>(m, vector<int>(9, false))); visited[start_x][start_y][8] = true; // 8表示初始状态 bool found = false; State result; while (!q.empty()) { State current = q.front(); q.pop(); if (grid[current.x][current.y] == '$') { found = true; result = current; break; } // 处理移动（8个方向） for (int dir = 0; dir < 8; ++dir) { int nx = current.x + dx[dir]; int ny = current.y + dy[dir]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '#') { if (!visited[nx][ny][dir]) { visited[nx][ny][dir] = true; State next = current; next.x = nx; next.y = ny; next.steps++; next.last_dir = dir; next.path.emplace_back(nx, ny); q.push(next); } } } // 处理跳跃（必须与上次移动方向相同） if (current.last_dir != -1) { int nx = current.x + dx[current.last_dir]; int ny = current.y + dy[current.last_dir]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '#') { if (!visited[nx][ny][current.last_dir]) { visited[nx][ny][current.last_dir] = true; State next = current; next.x = nx; next.y = ny; next.steps++; next.path.emplace_back(nx, ny); q.push(next); } } } } if (found) { for (int i = 0; i < result.path.size(); ++i) { cout << "(" << result.path[i].first + 1 << "," << result.path[i].second + 1 << ")"; if (i != result.path.size() - 1) { cout << "->"; } } cout << endl; cout << result.steps << endl; } else { cout << -1 << endl; } return 0;}
- 1