C++解决生活中的算法：走迷宫

本文介绍: 给出一个矩阵（表示迷宫），由n行m列组成，每个元素只能是0或者1，0表示死路，1表示通路，求出一条从左上角走到右下角的可能的路线，并输出其长度。

一、问题

给出一个矩阵（表示迷宫），由n行m列组成，每个元素只能是0或者1，0表示死路，1表示通路，求出一条从左上角走到右下角的可能的路线，并输出其长度。

例如：

已知迷宫图1，可以行走的路线为图2。

$begin{bmatrix} 1 & 1 & 1 \ 0 & 1 & 0 \ 0 & 1 & 1 \ end{bmatrix}$ $begin{bmatrix} textcolor{red}{mathbf{1}} & textcolor{red}{mathbf{1}} & 1 \ 0 & textcolor{red}{mathbf{1}} & 0 \ 0 & textcolor{red}{mathbf{1}} & textcolor{red}{mathbf{1}} \ end{bmatrix}$

图1 图2

二、实现

首先，我们先将框架搭建好。

#include <iostream>
using namespace std;

int n, m;
int maze[105][105];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> maze[i][j];
        }
    }
    printMinLength(n, m, maze);
    return 0;
}

然后，我们拼接出函数。

#include <iostream>
using namespace std;

int n, m;
int maze[105][105];

bool isRoad(int x, int y); // 是不是通路
bool go(int &x, int &y); // 向前试探1步
void printMinLength(int n, int m, int maze[][105]); // 输出最短路径长度

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> maze[i][j];
        }
    }
    printMinLength(n, m, maze);
    return 0;
}

bool isRoad(int x, int y)
{
    // 情况1: 越界
    if (x < 1 || y < 1) return false;
    if (x > n || y > m) return false;

    // 情况2: 在矩阵内死路
    if (maze[x][y] == 0) return false;

    // 情况3: 在矩阵内通路
    return true;
}

bool go(int &x, int &y)
{
    if (isRoad(x + 1, y)) // 向下走是通路
    {
        x++;
        return true;
    }
    else if (isRoad(x, y + 1)) // 向右走是通路
    {
        y++;
        return true;
    }
    else if (isRoad(x - 1, y)) // 向上是通路
    {
        x--; // 回溯到上一步
        return true;
    }
    else if (isRoad(x, y - 1)) // 向左是通路
    {
        y--;
        return true;
    }
    else
    {
        return false; // 四个方向都不通，迷宫无解
    }
}

void printMinLength(int n, int m, int maze[][105])
{
    int x = 1, y = 1;
    while (true)
    {
        cout << x << "," << y << " -> ";
        if (!go(x, y))
        {
            cout << "迷宫无解" << endl;
            break;
        }
        if (x == n && y == m)
        {
            cout << n << "," << m << endl << "抵达终点! ";
            break;
        }
    }
}

最后，我们来运行一下。

INPUT
5 5
1 1 1 1 1
0 0 0 0 1
0 1 0 0 1
0 1 0 1 1
0 1 0 0 1

CORRECT OUTPUT
1,1 -> 1,2 -> 1,3 -> 1,4 -> 1,5 -> 2,5 -> 3,5 -> 4,5 -> 5,5
抵达终点! 

MY OUTPUT
1,1 -> 1,2 -> 1,3 -> 1,4 -> 1,5 -> 2,5 -> 3,5 -> 4,5 -> 5,5
抵达终点!

但是无解的时候，就会开始反复横跳……

不过，只要不是无解，这个程序就可以啦！

原文地址:https://blog.csdn.net/joe_g12345/article/details/136054660

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_68267.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。