hiho一下第66周《Have Lunch Together》题目分析

6
3

题意分析

给定一幅字符表示的地图,其中包含有 1 个起点'H',若干个座位'S',墙壁'#'和行人'P'

其中墙壁'#'和行人'P'是不可通过的区域。

假设在地图中,只能沿着上下左右移动,且每移动一个单元格为 1 步。

询问从'H'点出发,是否能够到达两个相邻的'S',且需要移动的步数最少是多少。

算法分析

从题目当中,我们就可以知道本题需要做什么:

  1. 读取字符地图,并找到起点的位置。

  2. 从起点开始,遍历该地图,记录到达每一个'S'的距离。

  3. 判断是否有两个相邻的'S'都可达,若存在多个解,则需要找到最小的值。

那么我们就按照这三个步骤来解决这道题目。


首先是数据的读入,由于输入数据中已经明确的告诉了我们地图为 NM 列,所以我们只需要一行一行读入字符串,并使用char map[N][M]保存该地图。

map[i][j]表示原地图的第i行第j列的信息。

之后再对整个map[i][j]进行一次 O(mn) 的遍历,找出起点的位置,并记录下来。

我们用startX, startY 来记录起点的坐标。

startX = startY = 0;
// 读入地图
for (int i = 1; i <= N; i++) 
    scanf("%s", map[i] + 1);
// 查找起点H
for (int i = 1; i <= N; i++) 
    for (int j = 1; j <= M; ++j)
        if (map[i][j] == 'H') {
            startX = i, startY = j;
            break;
        }


第二步,寻找从起点(startX, startY)分别到每个'S'的最短路径。这一步我们直接使用BFS对整个图进行一次遍历。

首先建立数组int step[N][M]step[i][j]表示从起点到(i,j)的最少步数。

初始化为step[i][j] = INT_MAX,默认为任何点都无法到达。

开始遍历时,将step[ startX ][ startY ]设定为0,并以(startX, startY)开始BFS整个地图。

在遍历整个地图的过程中我们需要注意:

  • map[i][j] = '#'map[i][j] = 'P'时,step[i][j]直接等于INT_MAX,并且不扩展新的节点。

  • map[i][j] = 'S'时,我们需要更新当前节点的step[i][j]信息,但是由于当小Hi和小Ho走到位置后就不会再进行移动,所以也不扩展新的节点。

最后当没有新的节点可以到达时,退出BFS,得到整个地图的step[N][M]

bool inMap(int x, int y) {
    // 在地图内 && 不为墙壁同时也不为行人
    return (1 <= x && x <= N && 1 <= y && y <= M) && (map[x][y] == '.' || map[x][y] == 'S');
}

const int dir[4][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} }; // 方向数组
vector< pair<int, int> > seq;    // 用一个vector来存储BFS的队列

void BFS(int startX, int startY) {
    // 将起点存入队列
    step[ startX ][ startY ] = 0;
    seq.push_back( make_pair(startX, startY) );

    int i = 0;
    while (i < (int) seq.size()) {
        for (int dr = 0; dr < 4; ++dr) {
            // 扩展新的节点
            int tempX = seq[i].first  + dir[dr][0];
            int tempY = seq[i].second + dir[dr][1];

            if (inMap(tempX, tempY) && step[tempX][tempY] == INT_MAX) {
                step[tempX][tempY] = step[ seq[i].first ][ seq[i].second ] + 1;
                // 当发现是座位时,不再进行扩展
                if (map[tempX][tempY] != 'S') seq.push_back( make_pair(tempX, tempY) );
            }
        }
        ++i;
    }

    return ;
}


最后一步判断是否有两个连续的'S'都可达。

此时我们仍然遍历整个地图,因为只是检查是否有相邻的'S',不需要考虑顺序,所以我们按照i = 1..n, j = 1..m的顺序就可以。

当我们扫描到一个'S'时,首先判定其周围是否还有其他'S'。由于对称性,我们只需要检查两个方向即可。

若存在,则表示这两个'S'相邻,此时我们检查这两个位置的step值。

如果两个位置的step值都不等于INT_MAX,则说明这两个位置都是可以到达的。我们根据这两个位置的step和更新最优解。

当遍历完整个地图后,也就找到了我们所需要寻找的最优值。

int ret = INT_MAX;
for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= M; ++j)
        // 当前位置为S,且可以到达
        if (map[i][j] == 'S' && step[i][j] != 0) {
            // 检查下边是否有相邻S
            if (map[i - 1][j] == 'S' && step[i - 1][j] != 0 && ret > step[i][j] + step[i - 1][j])
                ret = step[i][j] + step[i - 1][j];
            // 检查右边是否有相邻S
            if (map[i][j - 1] == 'S' && step[i][j - 1] != 0 && ret > step[i][j] + step[i][j - 1])
                ret = step[i][j] + step[i][j - 1];
        }

结果分析

本题在这次比赛中是相对简单的一道题目,通过率也是三道题最高的。

本题本质就是一个裸的宽度优先搜索,唯一需要注意的只有当搜索到'S'时,不扩展新的节点。

  • 这个题目有个地方没说到,一个人占据一个位置后,另一个人不能从他这个位置通过,也就是说一旦一个人坐下了,这个位置就可以认为是P不可通过了。

  • S应该是可达到但不可通过的地方

  • 楼主不鸟咱

  • 这里设置最大值为INT_MAX会导致溢出,因为结果涉及到两个值的加法。 可自己设定一个很大的值

  • s必须是可达但是无法穿过的 不然样例就错了~~ 有时候可以从样例中分析出更具体的信息

  • 添加评论
  • reply

3 answer(s)

2

70分是怎么回事?有什么其他需要注意的地方吗?

  • 同样的结果。发现了告诉请告知下,谢!

  • 是输出的问题,找不到的话输出那个字符串

  • 添加评论
  • reply
0

最后一个代码块的ans和ret……

  • ret和ans是同一个变量,该处为笔误。请将ans视为ret。

  • corrected

  • 添加评论
  • reply
0

90/100 WA。。。迷茫

write answer 切换为英文 切换为中文


转发分享