首页 › 题库 › C/C++编程考级 › 5 最短路算法

C/C++编程七级 题库

共 2 道题 · 按题型筛选,点「查看答案」核对解析
章节 5 最短路算法 清除
1 单选题 适中 C/C++编程考级 ·C/C++编程七级 · 5 最短路算法

Dijkstra算法用于求解以下哪个问题?( )

A
单源最短路径
B
多源最短路径
C
最小生成树
D
拓扑排序
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
2 简答题 偏难 C/C++编程考级 ·C/C++编程七级 · 5 最短路算法

迷宫问题(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;
}

题目详情