BFS第一次扩展到终点时即可求得最短路

AcWing 1076. 迷宫问题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int bx[4] = {0,0,1,-1};
int by[4] = {1,-1,0,0};
int n;
struct node
{
    int px;
    int py;
}pre[1010][1010];
int a[1010][1010];
bool st[1010][1010];
void bfs(int x, int y)
{
    queue<pair<int, int>> q;
    q.push({x, y});
    st[x][y] = true;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int nowx = t.first, nowy = t.second;
        if(nowx == 1 && nowy == 1)break;
        for(int i = 0; i < 4; i ++ )
        {
            int nx = nowx + bx[i], ny = nowy + by[i];
            if(nx < 1 || ny < 1 || nx > n || ny > n)continue;
            if(a[nx][ny] || st[nx][ny])continue;
            q.push({nx,ny});
            pre[nx][ny].px = nowx, pre[nx][ny].py = nowy;
            st[nx][ny] = true;
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    for(int j = 1; j <= n; j ++ )
    {
        cin >> a[i][j];
    }
    bfs(n,n);
    int x = 1, y = 1;
    while(true)
    {
        printf("%d %d\n", x - 1, y - 1);
        if(x == n && y == n)break;
        auto t = pre[x][y];
        x = t.px, y = t.py;
    }
}

188. 武士风度的牛

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
char a[200][200];
int st[200][200];
int dis[200][200];
int n, m;
int bx[8] = {1,-1,1,-1,2,2,-2,-2};
int by[8] = {2,2,-2,-2,1,-1,1,-1};
int rx,ry,ex,ey;
int bfs(int x, int y)
{
    st[x][y] = true;
    queue<pair<int,int>> q;
    q.push({x,y});
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int nowx = t.first, nowy = t.second;
        if(nowx == ex && nowy == ey)break;
        for(int i = 0; i < 8; i ++ )
        {
            int nx = nowx + bx[i], ny = nowy + by[i];
            if(nx < 1 || ny < 1 || nx > n || ny > m)continue;
            if(st[nx][ny] || a[nx][ny] == '*')continue;
            q.push({nx, ny});
            dis[nx][ny] = dis[nowx][nowy] + 1;
            st[nx][ny] = true;
        }
    }
    return dis[ex][ey];
}
int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i ++ )
    for(int j = 1; j <= m; j ++ )
    {
        cin >> a[i][j];
        if(a[i][j] == 'K')
        {
            rx = i;
            ry = j;
        }
        if(a[i][j] == 'H')
        {
            ex = i;
            ey = j;
        }
    }
    cout << bfs(rx, ry);
}

1100. 抓住那头牛

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
bool st[200010];
int dis[200010];
int N,K;
int bfs(int x)
{
    queue<int> q;
    q.push(x);
    st[x] = true;
    while(!q.empty())
    {
        int now = q.front();
        if(now == K)break;
        q.pop();
        if(now + 1 < 2e5 && !st[now + 1])
        {
            q.push(now + 1);
            dis[now + 1] = dis[now] + 1;
            st[now + 1] = true;
        }
        
        if(now - 1 >= 0 && !st[now - 1])
        {
            q.push(now - 1);
            dis[now - 1] = dis[now] + 1;
            st[now - 1]  = true;
        }
        
        if(now * 2 < 2e5 && !st[now * 2])
        {
            q.push(now * 2);
            dis[now * 2] = dis[now] + 1;
            st[now * 2] = true;
        }
    }
    return dis[K];
}
int main()
{
    cin >> N >> K;
    cout << bfs(N);
}