AcWing 188. 武士风度的牛

蔚落 2024-04-08 13:14 70阅读 0赞

## 188. 武士风度的牛 ##

### 原题链接 ###

[188. 武士风度的牛][188.]

### 算法标签 ###

搜索 广度优先搜索 BFS

### 代码 ###

#include <cstring>
    #include <iostream>
    #include <algorithm>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 155, M = N * N;
    
    int n, m;
    char g[N][N];
    PII q[M];
    int dist[N][N];
    
    int bfs()
    {
        int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
        int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    
        int sx, sy;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == 'K')
                    sx = i, sy = j;
    
        int hh = 0, tt = 0;
        q[0] = {sx, sy};
    
        memset(dist, -1, sizeof dist);
        dist[sx][sy] = 0;
    
        while (hh <= tt)
        {
            auto t = q[hh ++ ];
    
            for (int i = 0; i < 8; i ++ )
            {
                int a = t.x + dx[i], b = t.y + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m) continue;
                if (g[a][b] == '*') continue;
                if (dist[a][b] != -1) continue;
                if (g[a][b] == 'H') return dist[t.x][t.y] + 1;
    
                dist[a][b] = dist[t.x][t.y] + 1;
                q[ ++ tt] = {a, b};
            }
        }
    
        return -1;
    }
    
    int main()
    {
        cin >> m >> n;
    
        for (int i = 0; i < n; i ++ ) cin >> g[i];
    
        cout << bfs() << endl;
    
        return 0;
    }

参考文献  
[AcWing 188. 武士风度的牛y总视频][AcWing 188. _y]

[AcWing 188. 武士风度的牛y总代码][AcWing 188. _y 1]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[188.]: https://www.acwing.com/problem/content/190/
[AcWing 188. _y]: https://www.acwing.com/video/1383/
[AcWing 188. _y 1]: https://www.acwing.com/activity/content/code/content/130867/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/b929b2c7460c47269185e8405d38dfd0.png