最短路模型

介绍

1. 基本作用：求最短路径以及最短距离
2. 基本方法：BFS
3. 适用题目：需要求点到点的最短距离或最短路径，并且边权都为1。（第一次修正：边权大于0并且相等即可）

代码思路

1. 用一个函数寻找最短路径（距离）。
2. 初始化距离（路径）数组。
3. 建立队列存放距离（路径）。
4. 将函数形参放入队列，并改变该坐标的距离（路径）数组。
5. 循环：队列中有元素则一直循环。
6. 遍历周围坐标，遇到不符合的坐标就略过。
7. 不符合的坐标包括：越界、已被访问过（距离（路径）数组已被改变的）、不符合题目条件的。
8. 对于符合条件的坐标，加入队列，并且根据前一个坐标改变它的（距离（路径）数组。

题目应用

1076. 迷宫问题(算法提高课)

1076. 迷宫问题

思路：

该题是要求从(0, 0)点到(n - 1, n - 1)点的最短路径，我们可以用一个pair数组来存放每个点的前一个坐标即可。
由于题目要求从(0, 0)开始，我们的数组又是记录的前一个坐标，所以我们可以从终点开始遍历，求出终点到起点最短路径。
再从(0, 0)点开始输出，依次输出前一个坐标即可达到题目要求。

代码：

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n;
int g[N][N];
PII pre[N][N];

void bfs(int x, int y)
{
    memset(pre, -1, sizeof pre);

    queue<PII> q;
    q.push({x, y});
    pre[x][y] = {0, 0};

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    while(q.size())
    {
        PII tmp = q.front();
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int nx = tmp.x + dx[i], ny = tmp.y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(g[nx][ny]) continue;
            if(pre[nx][ny].x != -1) continue;

            q.push({nx, ny});
            pre[nx][ny] = tmp;
        }

    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> g[i][j];

    bfs(n - 1, n - 1);

    PII end = {0, 0};

   while(true)
   {
       cout << end.x << " " << end.y << endl;
       if(end.x == n - 1 && end.y == n - 1) break;
       end = pre[end.x][end.y];
   }


    return 0;
}

188. 武士风度的牛(算法提高课)

188. 武士风度的牛

思路：

该题是求最短距离的，我们就是用距离数组来存放起点到该点的距离即可。对于满足条件的点使用dist[nx][ny]=distp[x][y] + 1更新。注意这里的走一步是类似于象棋中‘马’的走法，我们用位移数组操作即可。有个坑点是题目是先输入列在输入行。

代码：

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 155;

int n, m;
char g[N][N];
int dist[N][N];

int bfs(int x, int y)
{
    memset(dist, -1, sizeof dist);

    queue<PII> q;
    q.push({x, y});
    dist[x][y] = 0;

    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

    while(q.size())
    {
        PII tmp = q.front();
        q.pop();

        if(g[tmp.x][tmp.y] == 'H') return dist[tmp.x][tmp.y];

        for(int i = 0; i < 8; i++)
        {
            int nx = tmp.x + dx[i], ny = tmp.y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(g[nx][ny] == '*' || dist[nx][ny] != -1) continue;

            q.push({nx, ny});
            dist[nx][ny] = dist[tmp.x][tmp.y] + 1;
        }   
    }


}

int main()
{
    cin >> m >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> g[i][j];

    int ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(g[i][j] == 'K')
                ans = bfs(i, j);

    cout << ans << endl;

    return 0;

}

1100. 抓住那头牛(算法提高课)

1100. 抓住那头牛

思路：

该题是在一维条件下找起点到终点的最短距离，和二维类似。注意一下范围就可以、

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, k;
int dist[N];

int bfs()
{
    memset(dist, -1, sizeof dist);

      queue<int> q;
      q.push(n);
      dist[n] = 0;

      while(q.size())
      {
          int x = q.front();
          q.pop();

          if(x == k) return dist[x];

          for(int i = 0; i < 3; i++)
          {
              int nx;
              if(i == 0) nx = x - 1;
              else if(i == 1) nx = x + 1;
              else nx = 2 * x;

              if(nx < 0 || nx >= N ||dist[nx] != -1) continue;

              q.push(nx);
              dist[nx] = dist[x] + 1;


          }

      }

}

int main()
{
    cin >> n >> k;

    int ans = bfs();

    cout << ans << endl;

    return 0;

}