C++程序矩阵或网格中两个单元格之间的最短距离

给定一个N*M阶矩阵。查找从源单元格到目标单元格的最短距离，只遍历有限的单元格。另外，您只能向上，向下，向左和向右移动。如果找到则输出距离，否则输出-1。

s表示“源”

d表示’目的地’

*表示可以移动的单元格

0表示无法移动的单元格

这个问题只针对单个源和目的地。

示例：

Input : {'0', '*', '0', 's'},
        {'*', '0', '*', '*'},
        {'0', '*', '*', '*'},
        {'d', '*', '*', '*'}
Output : 6

Input :  {'0', '*', '0', 's'},
         {'*', '0', '*', '*'},
         {'0', '*', '*', '*'},
         {'d', '0', '0', '0'}
Output :  -1

思路是在矩阵单元格上进行BFS（广度优先搜索）。请注意，如果图是无权重的，则我们可以始终使用BFS查找最短路径。

将每个单元格作为具有其行、列值和与源单元格的距离的节点存储。
从源单元格开始BFS。
创建一个visited数组，所有数组都具有“假”值，除了无法遍历的“0”单元格，这些单元格被分配了“true”值。
在每个移动中更新从源值的距离。
当达到目标时返回距离，否则返回-1（源和目标之间不存在路径）。

// C++ 代码实现上述问题
#include <bits/stdc++.h>
using namespace std;
  
#define N 4
#define M 4
  
// QItem 的位置和源位置的距离
class QItem {
public:
    int row;
    int col;
    int dist;
    QItem(int x, int y, int w)
        : row(x), col(y), dist(w)
    {
    }
};
  
int minDistance(char grid[N][M])
{
    QItem source(0, 0, 0);
  
    // 记录已访问的 QItem，标记封锁单元格作为已访问。
    bool visited[N][M];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
        {
            if (grid[i][j] == '0')
                visited[i][j] = true;
            else
                visited[i][j] = false;
  
            // 寻找源位置
            if (grid[i][j] == 's')
            {
               source.row = i;
               source.col = j;
            }
        }
    }
  
    // 从源开始在矩阵单元格上应用 BFS
    queue<QItem> q;
    q.push(source);
    visited[source.row][source.col] = true;
    while (!q.empty()) {
        QItem p = q.front();
        q.pop();
  
        // 找到目标位置
        if (grid[p.row][p.col] == 'd')
            return p.dist;
  
        // 向上移动
        if (p.row - 1 >= 0 &&
            visited[p.row - 1][p.col] == false) {
            q.push(QItem(p.row - 1, p.col, p.dist + 1));
            visited[p.row - 1][p.col] = true;
        }
  
        // 向下移动
        if (p.row + 1 < N &&
            visited[p.row + 1][p.col] == false) {
            q.push(QItem(p.row + 1, p.col, p.dist + 1));
            visited[p.row + 1][p.col] = true;
        }
  
        // 向左移动
        if (p.col - 1 >= 0 &&
            visited[p.row][p.col - 1] == false) {
            q.push(QItem(p.row, p.col - 1, p.dist + 1));
            visited[p.row][p.col - 1] = true;
        }
  
         // 向右移动
        if (p.col + 1 < M &&
            visited[p.row][p.col + 1] == false) {
            q.push(QItem(p.row, p.col + 1, p.dist + 1));
            visited[p.row][p.col + 1] = true;
        }
    }
    return -1;
}
  
// 主函数
int main()
{
    char grid[N][M] = { { '0', '*', '0', 's' },
                        { '*', '0', '*', '*' },
                        { '0', '*', '*', '*' },
                        { 'd', '*', '*', '*' } };
  
    cout << minDistance(grid);
    return 0;
}

输出: