- 国贸周五19:30摸底赛 II
F题示例代码(01BFS模板)
- @ 2026-5-3 17:15:07
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
};
int n,m,sx=1,sy=1;//sx,sy作为起点坐标
char a[1005][1005]; //用于存储地图
int step[1005][1005]; //step[x][y]代表从起点走到(x,y)最少要花几步
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};//上下左右四个方向预先处理
void bfs(){
deque<node> dq;
//用双端队列,如果走到.上则优先插入到队首进行优先扩散
//走到 * 上则插入到队尾,最后处理
dq.push_front({sx,sy});
memset(step,0x3f,sizeof(step));
step[1][1]=0;
//0x3f3f3f3f
while(!dq.empty()){
int x = dq.front().x;
int y = dq.front().y;
dq.pop_front();
for(int i=0;i<4;i++){
int tx = x+dx[i];
int ty = y+dy[i];//vis
if(tx>=1 && tx<=n && ty>=1 && ty<=m && step[tx][ty]==0x3f3f3f3f){
int cost = (a[tx][ty]=='*') ;
//满足条件则证明该点没来过
step[tx][ty] = step[x][y] + cost;
if(cost==0) dq.push_front({tx,ty});
else dq.push_back({tx,ty});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
bfs();
cout << step[n][m];
return 0;
}
0 条评论
目前还没有评论...