先把起点入队。从队首向上下左右拓展节点，如果拓展出的某个节点在边界内未曾访问且是海洋则将这个节点入队，将其标记为已访问，用队首节点更新新节点到起点路程，拓展完后将队首出队：不断对队列执行这个动作，直到遇到终点。
设置位移数组dx，dy表示在拓展节点时在两个方向上的位移，应用位移数组拓展节点。
新节点到起点的距离是当前节点到起点的路程加一。
1 #include<iostream>
2 #include<queue>
3 #include<cstring>
4 #include<iterator>
5 int dis[1000][1000];//若dis[x][y]是-1则节点(x,y)未访问，否则dis[x][y]是(x,y)到起点的路程
6 bool map[1000][1000];//若map[x][y]是1则(x,y)是陆地，否则(x,y)是海洋
7 int dx[]={-1, 1, 0, 0};
8 int dy[]={ 0, 0,-1, 1};
9 bool bound(int x,int y,int n)
10 {
11 return x>0&&y>0&&x<=n&&y<=n;
12 }
13 void search(int x,int y,int a,int b,int n)
14 {
15 std::queue<std::pair<int,int>> Q;
16 dis[x][y]=0;
17 Q.push({x,y});
18 while(!Q.empty())
19 {
20 std::pair<int,int> u=Q.front();
21 Q.pop();
22 if(u.first==a&&u.second==b)
23 break;
24 for(int i=0;i<4;i++)
25 {
26 std::pair<int,int> v(u.first+dx[i],u.second+dy[i]);
27 if(bound(v.first,v.second,n)&&dis[v.first][v.second]==-1&&!map[v.first][v.second])//如果dis[v.first][v.second]是-1则节点v未访问（第5行）
28 {
29 Q.push(v);
30 dis[v.first][v.second]=dis[u.first][u.second]+1;
31 }
32 }
33 }
34 }
35 int main()
36 {
37 memset(dis,0xff,sizeof dis);//开始时将dis填成-1
38 int n;
39 std::cin>>n;
40 for(int i=1;i<=n;i++)
41 for(int j=1;j<=n;j++)
42 map[i][j]=((*std::istream_iterator<char>(std::cin))=='1');
43 int x,y,a,b;
44 std::cin>>x>>y>>a>>b;
45 search(x,y,a,b,n);
46 std::cout<<dis[a][b];
47 }
标签：std,int,second,dis,营救,节点,first From： https://www.cnblogs.com/daigemingzi/p/16621325.html