思路：
很容易想到b f的思路，实际上边权只有两种：
1.如果下一个点可以走，则边权为0
2.如果下一个点不可以走，则边权为1，同时周围的点也可以以同样的代价到达。
所以就考虑01 b f s，每当有边权为0的就插入队头，有边权为1的就插入队尾，这样可以保证每次取出的都是最小的，保证队列的单调性跟算法的正确性。
细节的地方为选择一个不能走的点时，周围的同样代价的点如何确定。
最后，题解里推荐了个同类型的题目。
代码：
struct node{ int x,y,step; }; char mp[510][510]; int n,m,vis[510][510]; int nx[]={1, 0, -1, 0}; int ny[]={0, 1, 0, -1}; int bfs(){ deque<node>q; q.push_front({1,1,0}); while(!q.empty()){ node t=q.front();q.pop_front(); int x=t.x,y=t.y,step=t.step; if(vis[x][y]) continue; vis[x][y]=1; if(x==n&&y==m) return step; for(int k=0;k<4;k++){ int xx=x+nx[k],yy=y+ny[k]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){ if(mp[xx][yy]=='.') q.push_front({xx,yy,step}); else{ for(int i=-1;i<=1;i++){ for(int j=-1;j<=1;j++){ int n_x=xx+i,n_y=yy+j; if(n_x>=1&&n_x<=n&&n_y>=1&&n_y<=m&&!vis[n_x][n_y]){ q.push_back({n_x,n_y,step+1}); } } } } } } } return -1; } int main(){ n=read,m=read; rep(i,1,n) cin>>mp[i]+1; cout<<bfs()<<endl; return 0; }
