C/C++编程七级 题库
共 2 道题
· 按题型筛选,点「查看答案」核对解析
2
简答题
偏难
迷宫问题(2024-3-7级)
定义一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫, 其中的 1 表示墙壁, 0 表示可以走的路, 只能横着走或竖着走, 不能斜着走, 要求编程序找出从左上角到右下角的最短路线。
时间限制: 1000
内存限制: 65536
输入
一个 5 × 5 的二维数组, 表示一个迷宫。 数据保证有唯一解。
输出
左上角到右下角的最短路径, 格式如样例所示。
样例输入
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
样例输出
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
答案与解析
参考答案
/*#include <iostream>*/
#include <bits/stdc++.h>
using namespace std;
const int idata = 50 + 5;
int maps[idata][idata];
bool judge[idata][idata];
int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int nx, ny;
int x[idata], y[idata];
int show[30];
bool flag;
void print(int tail) {
if (show[tail])
print(show[tail]);
cout << "(" << x[tail] << ", " << y[tail] << ")" << endl;
}
int main() {
int head, tail;
register int i, j;
for (i = 0; i < 5; i++) {
for (j = 0; j < 5; j++) {
cin >> maps[i][j];
if (maps[i][j] == 1)
judge[i][j] = 1;
}
}
head = 0;
tail = 1;
judge[0][0] = 1;
show[tail] = head;
while (tail > head) {
head++;
for (i = 0; i < 4; i++) {
nx = x[head] + change[i][0];
ny = y[head] + change[i][1];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !judge[nx][ny]) {
tail++;
x[tail] = nx;
y[tail] = ny;
judge[nx][ny] = 1;
show[tail] = head;
if (nx == 4 && ny == 4) {
flag = 1;
print(tail);
break;
}
}
}
if (flag)
break;
}
return 0;
}