AcWing 844. 走迷宫(《算法笔记》结构体写法)
原题链接
简单
作者:
小猫咪横扫世界
,
2024-07-25 19:00:11
,
所有人可见
,
阅读 1
结构体写法
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int n, m;
int matrix[maxn][maxn];
bool inq[maxn][maxn];
struct Node{
int x;
int y;
int step;
}S,top,node;
int X[4]={0,0,-1,1};
int Y[4]={1,-1,0,0};
void BFS(){
queue<Node> q;
q.push(S);
inq[0][0]=true;
while(!q.empty()){
top = q.front();
q.pop();
if(top.x==n-1&&top.y==m-1){
cout<<top.step;
break;
}
for(int i=0;i<4;i++){
int x = top.x + X[i];
int y = top.y + Y[i];
if(x>=0 && x<n && y>=0 && y<m && inq[x][y]==false && matrix[x][y]== 0){
node.x=x;
node.y=y;
node.step=top.step+1;
q.push(node);
inq[x][y]=true;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>matrix[i][j];
inq[i][j]=false;
}
}
S.x=0;
S.y=0;
BFS();
return 0;
}