bfs

``` #include<bits/stdc++.h> using namespace std; queue<pair<int,int> >q; int dis[101][101]; int vis[101][101]; int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; int n,m; int a[101][101]; void work() { q.push(make_pair(1,1)); dis[1][1]=0; while(!q.empty()) { int x=q.front().first; int y=q.front().second; q.pop(); if(x==n&&y==m)return; for(int i=0;i<4;i++) { int w=dis[x][y]; x+=dx[i],y+=dy[i]; if(x>=1&&x<=n&&y>=1&&y<=m) if(a[x][y]) if(!vis[x][y]) { vis[x][y]=1; dis[x][y]=w+1; q.push(make_pair(x,y)); } x-=dx[i],y-=dy[i]; } } } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { char c; scanf("\n"); for(int j=1;j<=m;j++) { scanf("%c",&c); a[i][j]=c-'0'; } } work(); printf("%d",dis[n][m]); } void bfs() { 把起点放⼊队列当中并且标记⼀下 while(队列⾮空） { 取出队列中的第⼀个点 if(这个点是终点) bfs结束退出 for(这个点下⼀步能⾛到的点） if(这个点没有被标记） { 标记这个点并把它加⼊到队列尾部 到这个点的步数=⾛到上⼀个点的步数+1 } } } ```