2 solutions
-
-3
#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