AcWing 188. 武士风度的牛（内附提醒，我调了一个小时才发现）    原题链接    简单

作者： 作者的头像   CCCkk ,  2021-08-03 16:51:51 ,  所有人可见 ,  阅读 812

5


1

### 题目描述

注意： 输入的数是 $m,n$ 而不是 $n,m$ !!!

样例

略

C++ 代码

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;

int n,m;
char g[200][200];
int  d[200][200];

int Bfs(PII a,PII b){
    queue<PII> q;
    q.push({a});

    memset(d,-1,sizeof d);
    d[a.first][a.second] = 0;
    int dy[8]={2,1,-1,-2,-2,-1,1,2},dx[8]={1,2,2,1,-1,-2,-2,-1};
    while(!q.empty()){
        PII t=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            int x=t.first+dx[i],y=t.second+dy[i]; 
            if(x >= 0 && y >= 0 && x < n && y < m && d[x][y] == -1 && g[x][y] != '*'){
                d[x][y]=d[t.first][t.second]+1;
                if(make_pair(x,y)==b) return d[x][y];
                q.push({x,y});
            }
        }

    }
    return -1;
}
int main(){
    PII start;
    PII end;
    cin>>m>>n;

    for(int i = 0;i < n; i++ ){
        for(int j = 0;j < m; j++ ){
            cin>>g[i][j];
            if(g[i][j] == 'K') start = { i ,j };
            if(g[i][j] == 'H') end = { i ,j };
        }
    }

    cout<<Bfs(start,end);
}

9 评论

用户头像
rookie.   8个月前         踩      回复

vocal,我tm也调了一个小时，还好看到你了😭😭😭

用户头像
Zzint   2022-10-25 20:01         踩      回复

大佬 这代码过不了

用户头像
CCCkk   2022-10-25 20:08         踩      回复

可以看下面评论哦

用户头像
CCCkk   2022-10-25 20:08    回复了 CCCkk 的评论         踩      回复

这是提醒大家的应该是cin>>m>>n;

用户头像
Link_Cut_Y   2021-08-26 12:47         踩      回复

我七年级

用户头像
Link_Cut_Y   2021-08-26 10:51         踩      回复

应该是cin>>m>>n;吧

用户头像
Link_Cut_Y   2021-08-26 10:49         踩      回复

这是不用STL的

用户头像
Link_Cut_Y   2021-08-26 10:48         踩      回复 
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int N=1010;
const int M=N*N;
typedef pair<int,int> PII;
PII q[M];
int g[N][N];
PII path[N][N];
int n;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int hh,tt;

inline void bfs(int sx,int sy)
{
    q[0]={sx,sy};
    hh=0;
    tt=0;
    memset(path,-1,sizeof path);
    path[sx][sy]={0,0};
    while(hh<=tt)
    {
        PII t=q[hh++];
        for(int i=0;i<4;i++)
        {
            int ex=t.x+dx[i];
            int ey=t.y+dy[i];
            if(ex<0 || ey<0 || ex>=n || ey>=n)
            {
                continue;
            }
            if(path[ex][ey].x!=-1)
            {
                continue;
            }
            if(g[ex][ey])
            {
                continue;
            }
            q[++tt]={ex,ey};
            path[ex][ey]=t;
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&g[i][j]);
        }
    }
    bfs(n-1,n-1);
    PII end(0,0);
    while(true)
    {
        printf("%d %d\n",end.x,end.y);
        if(end.x ==n-1 && end.y==n-1) break;
        end=path[end.x][end.y];
    }
    return 0;
}
用户头像
AutomaticAC   28天前         踩      回复

pair也是STL