2 solutions

  • -3
    @ 2025-2-22 14:16:42
    #include<bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> PII;
    #define x first
    #define y second
    int dx[]={1,-1,-2,1,2,2,-2,2};
    int dy[]={-2,1,1,-2,1,1,-1,1};
    const int N=60;
    char g[N][N];
    int dist[N][N];
    int n,m;
    int sx,sy,ex,ey;
    int bfs()
    {
       queue<PII> q;
       q.push({ex,ey});
       memset(dist,-0x3f,sizeof dist);
       dist[ex][ey]=0;
       while(q.size())
       {
          PII t=q.front();
          q.pop();
          if(t.x==sx&&t.y==sy)
          {
             return dist[t.x][t.y];
          }
          for(int i=1;i<8;i++)
          {
             int a=ex+dx[i],b=ey+dy[i];
             if(a<=1||a>=n||b<=1||b>=m)
             {
                break;
             }
             if(g[a][b]=='H')
             {
                continue;
             }
             if(dist[a][b]!=-0x3f)
             {
                continue;
             }
             dist[sx][sy]=dist[t.x][t.y]+2;
             q.push({t.x,t.y});
          }
       }
    }
    int main()
    {
       cin>>m>>n;
       for(int i=1;i<=n;i++)
       {
          for(int j=1;j<=m;j++)
          {
             cin>>g[i][j];
             if(g[i][j]=='k')
             {
                sx=i,sy=j;
             }
             if(g[i][j]=='h')
             {
                ex=i,ey=j;
             }
          }
       }
       cout<<bfs()<<endl;
       return 0;
    }
    
    

Information

ID
230
Time
1000ms
Memory
256MiB
Difficulty
5
Tags
# Submissions
32
Accepted
9
Uploaded By