思路：
与上题类似。
有两种走法，分别考虑代价：第一种花费的代价为0，第二种花费的代价为1.同时，第二种可以到达周围的点。
使用01 b f s来计算，每次将第一种花费放入队头，第二种花费放入队尾。
细节：
1.第二种可以到达的周围的点里，只能到达" . "的，也就是说原本就是可达的点。
2.对于每个点都有两种方案可以选择。
代码：
#include<bits/stdc++.h> using namespace std; int n,m,sx,sy,ex,ey; char mp[1100][1100]; int nx[]={0,0,1,-1}; int ny[]={1,-1,0,0}; bool vis[1100][1100]; struct node{ int x,y,step; }; int bfs(){ deque<node>q; q.push_front({sx,sy,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(t.x==ex&&t.y==ey) return t.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}); } } for(int i=-2;i<=2;i++) for(int j=-2;j<=2;j++){ int n_x=x+i,n_y=y+j; if(n_x>=1&&n_x<=n&&n_y>=1&&n_y<=m&&!vis[n_x][n_y]&&mp[n_x][n_y]=='.'){ q.push_back({n_x,n_y,step+1}); } } } return -1; } int main(){ cin>>n>>m>>sx>>sy>>ex>>ey; for(int i=1;i<=n;i++) cin>>mp[i]+1; cout<<bfs()<<endl; return 0; }
