【BFS】海上救援任务

简介: 【BFS】海上救援任务(c++基础算法)

本专栏上一篇:【BFS】魔板(c++基础算法)_静渊隐者的博客-CSDN博客


目录

一.读题

①题面

②题意

三.做题

四.AC代码

最后


一.读题

①题面

【宽搜(难度:4)】海上救援任务

【题意】

广阔的大海地图可以由矩形阵列表示。

矩阵的元素由数字0和1组成。0表示海水。数字1代表军舰。

同一舰队的定义为沿军舰数字上下左右还是军舰数字1则为同一舰队。

求给定矩形阵列的舰队个数。如:矩阵

0111100011

1011110100

1011100111

0000000011

有4个舰队。

其中有艘军舰发生故障,负责救援的人员从固定的救援军舰赶往故障处。处于安全考虑,救援人员只能通过舰队内部到达故障点。

【输入格式】

第一行两个整数n,m (1 < = n,m< = 100)

下来是n×m矩阵

下来一行K(1 < = K < =2000) ,代表下来K行有K个询问。每行为X1,Y1,X2,Y2代表两艘军舰的海上坐标。

【输出格式】

如果两艘军舰属于同一舰队那么输出它们之间最短的内部距离,若两艘军舰不属于同一舰队,那么请输出"Impossible".

注意: 舰队由军舰构成。^_^

【样例输入】

4 10

0111100011

1011110100

1011100111

0000000011

2

1 3 2 6

1 3 4 10

【样例输出】

4

Impossible

②题意

若存在xs,ys在不经过零的情况下到达xe,ye的路线,则输出最短路径;否则,输出Impossible


三.做题

可以说,这道题是百年不遇的水题,因此就不解释了。

唯一值得注意的是,存入地图的操作。

因为输入的地图不含空格,因此必须以字符形式输入。输入后,可依托ASCII码进行运算,将其转换为int类型的数组。

for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=m;j++)
    {
      char ch;
      cin>>ch;
      a[i][j]=ch-'0';
    } 
  }

image.gif


四.AC代码

不写注释啦!

#include<bits/stdc++.h>
using namespace std;
struct node{
  int x,y,ans;
};
queue<node>q;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int a[105][105];
int n,m,t,bo[105][105];
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=m;j++)
    {
      char ch;
      cin>>ch;
      a[i][j]=ch-'0';
    } 
  }
  scanf("%d",&t);
  while(t--)
  {
    memset(bo,0,sizeof(bo));
    node xs,xe;
    bool flag=false;
    xs.ans=0;
    scanf("%d%d%d%d",&xs.x,&xs.y,&xe.x,&xe.y);
    q.push(xs);
    while(!q.empty())
    {
      for(int i=0;i<4;i++)
      {
        node ne;
        ne.x=q.front().x+dx[i],ne.y=q.front().y+dy[i];
        if(bo[ne.x][ne.y]==0&&ne.x>=0&&ne.y>=0&&ne.x<=n&&ne.y<=m&&a[ne.x][ne.y]==1)
        {
          ne.ans=q.front().ans+1;
          bo[ne.x][ne.y]=1;
          q.push(ne);
          if(ne.x==xe.x&&ne.y==xe.y)
          {
            flag=true;
            printf("%d\n",q.back().ans);
            break;
          }
        }
      }
      if(flag) break;
      q.pop(); 
    }
    if(!flag) printf("Impossible\n");
  }
}

image.gif


最后

没什么要说的,不过说一句话:普及组训练营暂时停更 暂时停更。

目录
打赏
0
0
0
0
3
分享
相关文章
|
9月前
|
每日一题——地下迷宫(迷宫问题II)
每日一题——地下迷宫(迷宫问题II)
|
9月前
|
leetcode-675:为高尔夫比赛砍树 (最短路径算法bfs,dijkstra,A*)
leetcode-675:为高尔夫比赛砍树 (最短路径算法bfs,dijkstra,A*)
69 0
【BFS】魔板(c++基础算法)
【BFS】魔板(c++基础算法)
157 0
【BFS】八数码问题(c++基础算法)
【BFS】八数码问题(c++基础算法)
298 0
LeetCode 双周赛 102,模拟 / BFS / Dijkstra / Floyd
昨晚是 LeetCode 双周赛第 102 场,你参加了吗?这场比赛比较简单,拼的是板子手速,继上周掉大分后算是回了一口血 😁。
122 0
Codeforces987D(逆向思维多源BFS)
Codeforces987D(逆向思维多源BFS)
149 0
杭电1728bfs逃离迷宫java实现
给定一个m × n (m行, n列)的迷宫,迷宫中有两个位置,gloria想从迷宫的一个位置走到另外一个位置,当然迷宫中有些地方是空地,gloria可以穿越,有些地方是障碍,她必须绕行,从迷宫的一个位置,只能走到与它相邻的4个位置中,当然在行走过程中,gloria不能走到迷宫外面去。令人头痛的是,gloria是个没什么方向感的人,因此,她在行走过程中,不能转太多弯了,否则她会晕倒的。我们假定给定的两个位置都是空地,初始时,gloria所面向的方向未定,她可以选择4个方向的任何一个出发,而不算成一次转弯。gloria能从一个位置走到另外一个位置吗?
123 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等