营救
- 分析：根据题意，BFS具有求最短路径的特点，就是套用BFS的模板，在if语句判断时不越界，没被标记，是海洋（船只能走海洋），还有就是每走一步步数增加1，从营救船所在的位置开始，到遇难船所在的位置结束。
-
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,x1,y1,x2,y2;
char a[1001][1001];
bool b[1001][1001];//标记数组
int ans[1001][1001];//ans记录步数
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct node
{
int x,y;
}now;
void bfs(int x,int y)
{
ans[x][y]=0;//步数一开始是0
queue<node> q;
q.push({x,y});
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=now.x+dx[i];
int yy=now.y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&b[xx][yy]==0&&a[xx][yy]=='0')
{//没超范围 没被标记 是海洋
b[xx][yy]=1;//标记
ans[xx][yy]=ans[now.x][now.y]+1;//步数加1
q.push({xx,yy});
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
cin>>x1>>y1>>x2>>y2;
bfs(x1,y1);
cout<<ans[x2][y2];
return 0;
}