- 国贸周五19:30摸底赛 II
E题示例代码 (BFS模板题)
- @ 2026-5-3 17:13:08
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
};
int n,m,sx=1,sy=1;//sx,sy作为起点坐标
int a[1005][1005]; //用于存储地图
int step[1005][1005]; //step[x][y]代表从起点走到(x,y)最少要花几步
int vis[1005][1005]; //用于检测(x,y)点是否走过,如果走过设为1
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};//上下左右四个方向预先处理
void bfs(){
queue<node> q;
q.push({sx,sy});
vis[sx][sy]=1;//起点先入队,作为第一个被处理的点
while(!q.empty()){
//处理队首元素
int x = q.front().x;
int y = q.front().y;
//我们要处理的点是(x,y),我们要对其进行扩散
q.pop();//该点处理完毕后出队,免得死循环
for(int i=0;i<4;i++){
int tx = x+dx[i]*a[x][y];
int ty = y+dy[i]*a[x][y];//(tx,ty)是即将被扩散的点
if(tx>=1 && tx<=n && ty>=1 && ty<=m && a[tx][ty]!='#' && vis[tx][ty]==0){//边界判断,每个点只需要走到一次
q.push({tx,ty});//下一层元素入队
vis[tx][ty]=1;//标记
step[tx][ty] = step[x][y]+1;//记录步数
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
bfs();//广搜处理step数组
if(step[n][m]==0) cout << "No Solution";
else cout << step[n][m];
return 0;
}
0 条评论
目前还没有评论...