AcWing 188. 武士风度的牛 BFS 水题

题目描述 农民John有很多牛，他想交易其中一头被Don称为The Knight的牛。

这头牛有一个独一无二的超能力，在农场里像Knight一样地跳（就是我们熟悉的象棋中马的走法）。

虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个x，y的坐标图来表示。

这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了The Knight的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。

现在你的任务是，确定The Knight要想吃到草，至少需要跳多少次。

The Knight的位置用’K’来标记，障碍的位置用’*’来标记，草的位置用’H’来标记。

这里有一个地图的例子：

11 | . . . . . . . . . . 10 | . . . . * . . . . . 9 | . . . . . . . . . . 8 | . . . * . * . . . . 7 | . . . . . . . * . . 6 | . . * . . * . . . H 5 | * . . . . . . . . . 4 | . . . * . . . * . . 3 | . K . . . . . . . . 2 | . . . * . . . . . * 1 | . . * . . . . * . . 0 ---------------------- 1 0 1 2 3 4 5 6 7 8 9 0 The Knight 可以按照下图中的A,B,C,D…这条路径用5次跳到草的地方（有可能其它路线的长度也是5）：

11 | . . . . . . . . . . 10 | . . . . * . . . . . 9 | . . . . . . . . . . 8 | . . . * . * . . . . 7 | . . . . . . . * . . 6 | . . * . . * . . . F< 5 | * . B . . . . . . . 4 | . . . * C . . * E . 3 | .>A . . . . D . . . 2 | . . . * . . . . . * 1 | . . * . . . . * . . 0 ---------------------- 1 0 1 2 3 4 5 6 7 8 9 0 注意： 数据保证一定有解。

样例 输入样例： 10 11 .......... ....*..... .......... ...*.*.... .......*.. ..*..*...H *......... ...*...*.. .K........ ...*.....* ..*....*..

输出样例： 5 一道广搜的”版版”题. 只需用最原始的广搜，改一下方向即可.

时间复杂度 O(n*m),最坏情况全图搜，当然肯定达不到

#include<bits/stdc++.h>
using namespace std;
const int N=160;
#define x first
#define y second
typedef pair<int,int> pii;
int n,dis[N][N],m;
char g[N][N],vis[N][N];
pii pre[N][N];
void bfs(int x,int y){
    queue<pii>q;
    int nx[8]={1,1,-1,-1,2,2,-2,-2},ny[8]={2,-2,2,-2,1,-1,1,-1};
    memset(dis,0x3f,sizeof dis);
    q.push({x,y});
    dis[x][y]=0;
    vis[x][y]=1;
    while(!q.empty()){
        auto now=q.front();
        q.pop();
        if(g[now.x][now.y]=='H'){
            cout<<dis[now.x][now.y]<<endl;
            break;
        }
        //cout<<now.x<<" "<<now.y<<endl;
        for(int i=0;i<8;i++){
            int a=now.x+nx[i],b=now.y+ny[i];
            if(a<0||b<0||a>m-1||b>n-1)continue;
            if(g[a][b]=='*'||vis[a][b])continue;
            q.push({a,b});
            vis[a][b]=1;
            dis[a][b]=min(dis[a][b],dis[now.x][now.y]+1);
            if(g[a][b]=='H'){
                cout<<dis[a][b]<<endl;
                return;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>g[i];
    }
    int a,b;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(g[i][j]=='K'){
                bfs(i,j);
                return 0;
            }
        }
    }
    return 0;
    
}