注意: 输入的数是 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);
}
vocal,我tm也调了一个小时,还好看到你了😭😭😭
大佬 这代码过不了
可以看下面评论哦
这是提醒大家的应该是
cin>>m>>n;
我七年级
应该是
cin>>m>>n;
吧这是不用STL的
#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; }
pair也是STL