搜索(6)

例1 蓝桥杯——穿越雷区

 题目大意是在一个nxn的方阵地图上,每一个方格都标记+号或者-号,要从A点到B点。题目要求移动路线要+-交替,问怎么移动从A到B才是最短路径?  同样的,这道题也是一道2D网格图上的最短路径问题。我们仍然采用相同的思路来解决它  相较于上一讲的问题,本题主要有以下两个个不同之处:

  • 起始点不在固定,而是通过字符地图给出。在这道题目中起点为A,终点为B
  • 在移动的过程中,需要满足正负能量交错,即只能从+格子移动到-格子或从-格子移动到+格子

 第一个限制条件在读入数据时,顺便将A,B两点的坐标进行记录即可。该题目的主要问题在第二个限制条件,在移动过程中需要满足正负能量交错  BFS扩展节点的过程实际上就是在模拟移动的过程,换句话说,需要在扩展的过程中满足当前节点与扩展节点的属性相反。我们可以通过在if语句中添加条件来实现,这里给出实现代码:

#include <iostream>
#include <string>
using namespace std;
int n,x_A,y_A,x_B,y_B;
char map[100][100];
const int dr[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int head = 0,tail = 0;
int que[10000][2],steps[100][100];
bool inq[100][100] = {false};
bool inMap(int x,int y)
{
    return x >= 0 && x < n && y >= 0 && y < n;
}
void bfs()
{
    que[tail][0] = x_A;
    que[tail][1] = y_A;
    tail++;
    steps[x_A][y_A] = 0;
    inq[x_A][y_A] = true;
    while(head < tail)
    {
        int x = que[head][0];
        int y = que[head][1];
        head++;
        for(int d = 0;d < 4;++d)
        {
            int nx = x + dr[d][0];
            int ny = y + dr[d][1];
            if(inMap(nx,ny) && !inq[nx][ny] && 
               map[x][y] != map[nx][ny])
            {
                   steps[nx][ny] = steps[x][y] + 1;
                   inq[nx][ny] = true;
                   que[tail][0] = nx;
                   que[tail][1] = ny;
                   tail++;
            }    
        }
        
    }
}
int main()
{
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            cin >> map[i][j];
            if(map[i][j] == 'A')
            {
                x_A = i;
                y_A = j;
            }
            if(map[i][j] == 'B')
            {
                x_B = i;
                y_B = j;
            }
        }    
    }
    bfs();
    if(!inq[x_B][y_B])
        cout << -1 << endl;
    else
        cout << steps[x_B][y_B] << endl;
    return 0;
}

 首先看一下定义的变量,(x_A, y_A)是起点坐标,(x_B, y_B)是终点坐标。que[]数组是BFS队列,head和tail是头尾指针  二维数组steps[][]记录了到每一个位置的最短路径长度。二维数组inq[][]记录了每个位置是不是已经在队列里了  第10~13行InMap函数是判断坐标(x, y)是不是在地图上  然后我们先来看一下第43~69行的主函数。主函数的逻辑非常简单,首先读入地图,找出起点和终点;然后BFS;BFS结束后如果(x_B, y_B)没进过队列,说明到达不了,输出-1;否则直接输出stepsx_B  第13~33行是BFS宽搜的过程。基本框架已经说明过了。具体可以看一下第31行,在扩展时,比较mapx和map_x的字符是否不同来决定能否移动过去  在宽搜中用inq[][]保证每个位置最多进队列出队列一次,而每次处理队首元素的复杂度是O(1)的,所以程序整体的复杂度是O(n^2)  至此这道题目也就完美的解决了,看下一道题目hihoCoder的1092题,《Have Lunch Together》。这道题是微软的一道笔试题

例2 题目链接:hihoCoder1092

 这道题目的大意是给定一幅字符表示的地图,大小为n*m。地图中包含有 1 个起点'H',若干个座位'S',墙壁'#'和行人'P'。其中墙壁'#'和行人'P'是不可通过的区域。座位'S'只可到达,不可通过  假设在地图中,只能沿着上下左右移动,且每移动一个单元格为1步。两个人从起点'H'出发,是否能够到达两个相邻的座位'S',且需要移动的总步数最少是多少  通过题意,我们可以发现本题主要有以下两个限制条件:

  • 在该题目中,目标是从H字符出发,最后到达S字符。因此在本问题中移动不再是从左上角到右下角,而是通过字符画的形式给出起点和终点。 同时由于地图中可能出现多个不同位置的S,也就存在了多个不同的终点。
  • 在该题目中,目标不仅仅是寻找一条从起点到终点的路径。而是需要找到两个相邻的终点,并且使得从H到这两个点的最短路径之和最小

 对于本题来说,解决的思路分为两步:

  1. 查询所有可以到达的终点S。
  2. 枚举相邻的S,并从中找出距离和最小的答案

 第一步的解决过程显然就是最基础的2D网格地图最短路径问题,我们可以直接利用宽度优先搜索进行求解。将H点所在的位置作为初始搜索节点进行扩展,记录到达每一个S的最短步数  在搜索过程中我们可能会遇到一些S节点无法到达的情况,比如:

 对于这样的S节点我们需要进行标记,将其设置为不可到达状态。一个简单的处理办法是将不可达位置的最短路径长度设置成一个负数,比如-1;或者也可以设置为一个足够大的数,比如99999999。这里我们推荐使用99999999的方式,这样可以简化我们第二部分的代码。  这道题完整的代码如下:

#include <iostream>
#include <cstdio>
using namespace std;
const int dr[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
const int INF = 999999;
int N,M,sX,sY;
char map[102][102];
int steps[102][102],que[10002][2];
int head = 0,tail = 0;
bool isValid(int x,int y)
{
    return x >= 1 && x <= N && y >= 1 && y <= M && 
          (map[x][y] == '.' || map[x][y] == 'S');  
}
void bfs(int startX,int startY)
{
    steps[startX][startY] = 0;//将起点标为走过
    //起点入队
    que[tail][0] = startX; 
    que[tail][1] = startY;
    
    tail++;
    while(head < tail)
    {
        int x = que[head][0];//当前队首元素的横坐标
        int y = que[head][1];//当前队首元素的纵坐标
        for(int d = 0;d < 4;++d)//枚举四个方向
        {
            int nx = x + dr[d][0];//新的横坐标 
            int ny = y + dr[d][1];//新的纵坐标 
            if(isValid(nx,ny) && steps[nx][ny] == INF)//isValid判断是否能走
            //steps判断是否走过,没走过值就是INF 
            {
                steps[nx][ny] = steps[x][y] + 1;
                if(map[nx][ny] != 'S')//如果新的坐标位置不是S 
                {
                    que[tail][0] = nx;//横坐标入队
                    que[tail][1] = ny;//纵坐标入队
                    tail++;//队尾指针加1
                }
            }
        }
        ++head;//枚举完四个方向,队首元素出队 
    }
}
int main()
{
    cin >> N >> M;
    sX = sY = 0;
    for(int i = 1;i <= N;i++)
    {
        scanf("%s",map[i] + 1);
        for(int j = 1;j <= M;j++)
        {
            steps[i][j] = INF;
            if(map[i][j] == 'H')//找到起始点 
            {
                sX = i;//保存起点横坐标 
                sY = j;//保存起点纵坐标 
            }
        }
    }     
    bfs(sX,sY);//从起点开始bfs 
    int ans = INF;
    for(int i = 1;i <= N;++i)
    {
        for(int j = 1;j <= M;++j)
        {
            if(map[i][j] == 'S')
            {
                if(map[i - 1][j] == 'S' && 
                   ans > steps[i][j] + steps[i - 1][j])
                    ans = steps[i][j] + steps[i - 1][j];
                if(map[i][j - 1] == 'S' && 
                   ans > steps[i][j] + steps[i][j - 1])
                    ans = steps[i][j] + steps[i][j - 1];
                /*if(map[i + 1][j] == 'S' &&
                   ans > steps[i][j] + steps[i + 1][j])
                       ans = steps[i][j] + steps[i + 1][j];
                if(map[i][j + 1] == 'S' && 
                   ans > steps[i][j] + steps[i][j + 1])
                       ans = steps[i][j] + steps[i][j + 1];*/
            }
        }
    }
    if(ans == INF)
        cout << "Hi and Ho will not have lunch." << endl;
    else
        cout << ans << endl;
    return 0;
}

 首先我们看第46-92行的main函数。第50~62行是在读入地图,并且找出起点H的坐标,同时把每个位置的最短路径距离设置成INF,也就是之前提到的很大的数999999  然后就是第63行BFS,我们知道BFS执行过程中会遍历能从起点到达的所有位置,并且求出来到达这些位置的最短路径长度,保存在steps[][]里  第65-85行是找到所有相邻的一对S 节点,求出这一对节点的最短路径之和。如果比当前最优的解ans更少,就更新ans。有一个小的细节是S字符之间的相邻方向是相对的,如果(x1,y1)在(x2,y2)上方,那么也同样有(x2,y2)在(x1,y1)下方。因此我们只需要判定2个方向即可,比如下方和右方  注意我们之前给steps[][]赋值的初始值是INF=999999。所以不可达的S字符的steps值将是999999。这样若(x1,y1)或(x2,y2)中有一个不可到达时,最短路之和结果一定会大于999999,就一定会大于ans,自然就被排除了。若设置为-1的话,则需要通过if语句手动判定一次  在这里也有一个小陷阱,这个足够大的数INF不能够设置为INT_MAX,否则两个INT_MAX相加会有溢出的风险  第10~14的isValid()函数用来判断能不能访问(x, y)这个位置。能访问的条件除了(x, y)在地图范围内,还需要满足(x, y)只能是空地或者座位  最后是第42~60行的BFS。这个BFS和之前几道题目的BFS函数基本一致。稍微有一点区别的就是我们用stepsnX是不是等于INF来判断(nX, nY)是不是访问过了。另外一点区别就是根据题目要求,我们只在当前节点是空地的时候才能扩展当前节点的邻居节点,如果是座位则不会扩展;具体可以看第35行的if语句

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端黑板报

一个数字截取引发的精度问题(四)

这篇是精度问题的最后一篇,要是想看前面的,请看微信历史记录。 做前端的都感觉JS这语言巨坑无比,兼容性让你摸不到头脑,甚至还会让你脱发。一些初学者遇到: 0.1...

257100
来自专栏机器之心

入门 | 数据科学初学者必知的NumPy基础知识

选自TowardsDataScience 作者:Ehi Aigiomawu 机器之心编译 参与:李诗萌、路 本文介绍了一些 NumPy 基础知识,适合数据科学初...

28630
来自专栏不止思考

算法的时间与空间复杂度(一看就懂)

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有...

11720
来自专栏数据结构与算法

洛谷P3391 【模板】文艺平衡树(Splay)(FHQ Treap)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

32950
来自专栏人工智能

如何为机器学习索引,切片,调整 NumPy 数组

具体在 Python 中,数据几乎被都被表示为 NumPy 数组。

76370
来自专栏简书专栏

基于Python装饰器的向量化计算速度对比

timer是一个装饰器,功能是给被装饰的函数计时。如果要进一步了解装饰器的使用,点击此链接Python闭包函数和装饰器 sumOfLoop函数是常规的使用fo...

11920
来自专栏数据结构与算法

P3382 【模板】三分法

题目描述 如题,给出一个N次函数,保证在范围[l,r]内存在一点x,使得[l,x]上单调增,[x,r]上单调减。试求出x的值。 输入输出格式 输入格式: 第一行...

35690
来自专栏Python小屋

Python花式编程案例锦集(3)

严格来说,本文的2个代码不算花式编程,在Python中就应该是这样写。 1、生成包含20个随机数的列表,然后删除其中的所有奇数。 from random imp...

373130
来自专栏CDA数据分析师

入门 | 数据科学初学者必知的NumPy基础知识

NumPy(Numerical Python)是 Python 中的一个线性代数库。对每一个数据科学或机器学习 Python 包而言,这都是一个非常重要的库,S...

14020
来自专栏抠抠空间

逻辑运算

一、逻辑运算符的种类及优先级 ▷逻辑运算符包括 not and or  ▷他们的优先级是 () > not > and > or 二、普通逻辑运算 ▷A and...

29090

扫码关注云+社区

领取腾讯云代金券