博客
关于我
迷宫寻路 (20 分)
阅读量:670 次
发布时间:2019-03-15

本文共 3186 字,大约阅读时间需要 10 分钟。

为了解决这个问题,我们需要找到从迷宫左上角(1,1)到右下角(5,8)的最短路径。迷宫中使用0表示通路,1表示障碍物。我们可以使用广度优先搜索(BFS)来确保找到最短路径。

方法思路

  • 输入处理:读取迷宫的行数和列数,然后读取迷宫的具体结构。
  • 检查起点:确保起点(1,1)是通路,否则直接输出“NO FOUND”。
  • BFS初始化:使用队列进行BFS,记录当前路径,避免重复访问同一个点。
  • 路径记录:每次访问一个点时,记录路径,并将未访问的邻居加入队列。
  • 终点检查:如果在BFS过程中找到终点(5,8),输出路径;否则,输出“NO FOUND”。
  • 解决代码

    #include 
    #include
    #include
    #include
    using namespace std;// 定义常量const int N = 110;const int INF = 0x3f3f3f3f;int dist[N][2], path[N][2];int m, n;bool visited[N+1][N+1];// 四个方向:上下左右int dx[] = {0, 1, 0, -1};int dy[] = {1, 0, -1, 0};void bfs() { queue
    > q; vector
    step; q.push(make_pair(1, 1)); step.clear(); dist[0][0] = 1; path[0][0] = make_pair(1, 1); if (1 == m && 1 == n) { // 起点就是终点 dist[0][0] = 0; path[0][0] = make_pair(1, 1); return; } int found = 0; while (!q.empty()) { auto current = q.front(); q.pop(); int x = current.first, y = current.second; step.push_back(current); if (x == m && y == n) { found = 1; break; } for (int i = 0; i < 4; ++i) { int tx = x + dx[i]; int ty = y + dy[i]; if (tx >= 1 && tx <= n && ty >= 1 && ty <= m) { if (!visited[tx][ty] && g[tx][ty] == 0) { visited[tx][ty] = 1; dist[step.size() - 1][0] = tx; dist[step.size() - 1][1] = ty; path[step.size() - 1][0] = tx; path[step.size() - 1][1] = ty; q.push(make_pair(tx, ty)); } } } } if (found) { for (int i = 0; i < step.size(); ++i) { int x = path[i].first; int y = path[i].second; // 转换为题目要求的1-based索引 cout << x << ","; cout << y << endl; } } else { cout << "NO FOUND" << endl; }}int main() { while (true) { cin >> n >> m; if (m == -1) { break; } // 读取迷宫数据 vector
    > g(m + 1, vector
    (n + 1, 0)); for (int i = 1; i <= m; ++i) { string line; while (line.empty()) { getline(cin, line); } vector
    row; istringstream iss(line); while (row.size() < n) { int num; iss >> num; row.push_back(num); } for (int j = 1; j <= n; ++j) { g[i][j] = row[j - 1]; } } // 检查起点是否是通路 if (g[1][1] != 0) { cout << "NO FOUND" << endl; continue; } // 初始化BFS visited = {{false}}; vector
    steps; queue
    > q; q.push(make_pair(1, 1)); visited[1][1] = true; if (1 == m && 1 == n) { cout << "1,1" << endl; continue; } bool success = false; // BFS过程 while (!q.empty()) { auto current = q.front(); q.pop(); int x = current.first, y = current.second; for (int i = 0; i < 4; ++i) { int tx = x + dx[i]; int ty = y + dy[i]; if (tx >= 1 && tx <= n && ty >= 1 && ty <= m) { if (!visited[tx][ty] && g[tx][ty] == 0) { visited[tx][ty] = true; if (tx == m && ty == n) { success = true; break; } // 记录路径 if (steps.empty()) { dist[0][0] = tx; dist[0][1] = ty; path[0][0] = make_pair(tx, ty); steps.push_back(0); } else { dist[steps.size()][0] = tx; dist[steps.size()][1] = ty; path[steps.size()][0] = make_pair(tx, ty); steps.push_back(steps.size()); } q.push(make_pair(tx, ty)); } } } if (success) { break; } } if (success) { for (int i = 0; i < steps.size(); ++i) { int x = path[i].first; int y = path[i].second; // 转换为题目要求的1-based索引 cout << x << ","; cout << y << endl; } } else { cout << "NO FOUND" << endl; } } return 0;}

    代码解释

  • 读取输入:程序读取迷宫的行数和列数,接着读取每行的迷宫数据。
  • BFS初始化:检查起点是否为通路,初始化队列和路径记录数组。
  • BFS执行:从起点开始,逐层扩展,检查四个方向的邻居是否为通路且未访问过。
  • 路径记录:每次访问一个点时,记录路径,并将邻居加入队列。
  • 终点检查:如果找到终点,输出路径;否则,输出“NO FOUND”。
  • 转载地址:http://pvzqz.baihongyu.com/

    你可能感兴趣的文章
    NodeJS API简介
    查看>>
    Nodejs express 获取url参数,post参数的三种方式
    查看>>
    nodejs http小爬虫
    查看>>
    nodejs libararies
    查看>>
    nodejs npm常用命令
    查看>>
    nodejs npm常用命令
    查看>>
    Nodejs process.nextTick() 使用详解
    查看>>
    NodeJS yarn 或 npm如何切换淘宝或国外镜像源
    查看>>
    nodejs 中间件理解
    查看>>
    nodejs 创建HTTP服务器详解
    查看>>
    nodejs 发起 GET 请求示例和 POST 请求示例
    查看>>
    NodeJS 导入导出模块的方法( 代码演示 )
    查看>>
    nodejs 开发websocket 笔记
    查看>>
    nodejs 的 Buffer 详解
    查看>>
    NodeJS 的环境变量: 开发环境vs生产环境
    查看>>
    nodejs 读取xlsx文件内容
    查看>>
    nodejs 运行CMD命令
    查看>>
    Nodejs+Express+Mysql实现简单用户管理增删改查
    查看>>
    nodejs+nginx获取真实ip
    查看>>
    nodejs-mime类型
    查看>>