机器人活动区域

题目描述

现有一个机器人, 可放置于 M × N 的网格中任意位置, 每个网格包含一个非负整数编号, 当相邻网格的数字编号差值的绝对值小于等于 1 时, 机器人可以在网格间移动.

问题: 求机器人可活动的最大范围对应的网格点数目.

说明: 网格左上角坐标为 (0, 0), 右下角坐标为 (m−1, n−1), 机器人只能在相邻网格间上下左右移动.

输入描述

• 第 1 行输入为 M 和 N
  • M 表示网格的行数
  • N 表示网格的列数
• 之后 M 行表示网格数值, 每行 N 个数值 (数值大小用 k 表示), 数值间用单个空格分隔, 行首行尾无多余空格
  • M, N, k 均为整数
  • 1 ≤ M, N ≤ 150
  • 0 ≤ k ≤ 50

输出描述

输出 1 行, 包含 1 个数字, 表示最大活动区域的网格点数目, 行首行尾无多余空格.

示例1

输入:

4 4
1 2 5 2
2 4 4 5
3 5 7 1
4 6 2 4

输出:

6

说明: 如下图, 图中红色区域, 相邻网格差值绝对值都小于等于 1, 且为最大区域, 对应网格点数目为 6.

示例2

输入:

2 3
1 3 5
4 1 3

输出:

1

说明: 任意两个相邻网格的差值绝对值都大于1, 机器人不能在网格间移动, 只能在单个网格内活动, 对应网格点数目为1.

题解

使用 广度优先搜索 BFS 求得最大的连接节点数.

Python

import sys

def main():
    # 读取网格的行列值
    parts = input().split()
    rows = int(parts[0])
    columns = int(parts[1])
    assert 1 <= rows <= 150
    assert 1 <= columns <= 150
    # 读取网格中的数值
    grid = []
    for line in sys.stdin.readlines():
        grid.append(list(map(int, line.split())))
        assert len(grid[-1]) == columns
    assert len(grid) == rows
    print(grid)

    # 标记已经访问过了的节点
    visited = [[False] * columns for _row in range(rows)]

    # 四个移动的方向
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    def dfs(grid, visited, x, y):
        if visited[x][y]:
            return 0
        # 先标记当前节点已经访问过
        visited[x][y] = True

        move_range = 1

        # 遍历四个可能的移动方向
        for dx, dy in directions:
            x1 = x + dx
            y1 = y + dy
            # 判断新的节点是否满足条件
            # 1. 在矩形范围内移动
            # 2. 新的节点未被访问过
            # 3. 两个节点上的值相差小于等于1
            if 0 <= x1 < rows and 0 <= y1 < columns and \
                    not visited[x1][y1] and abs(grid[x][y] - grid[x1][y1]) <= 1:
                # 递归访问新的节点
                move_range += dfs(grid, visited, x1, y1)
                #print("move from:", x, y, ", to :", x1, y1)

        # 返回最大能访问的节点数
        return move_range

    # 遍历所有的格子, 找到最大的移动范围
    max_range = 0
    for i in range(rows):
        for j in range(columns):
            # 使用DFS方法, 尝试向四个方向移动
            move_range = dfs(grid, visited, i, j)
            max_range = max(max_range, move_range)

    print(max_range)

if __name__ == "__main__":
    main()

C++

#include <cassert>

#include <array>
#include <iostream>
#include <string>
#include <vector>

int dfs_visit(const std::vector<std::vector<int>>& grid,
              std::vector<std::vector<bool>>& visited,
              int x, int y, int rows, int columns) {
  if (visited[x][y]) {
    return 0;
  }
  // 先标记当前节点状态
  int move_range = 1;
  visited[x][y] = true;

  const std::array<std::array<int, 2>, 4> directions = 
    {std::array<int, 2>{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  // 开始准备向四个方向访问
  for (const auto dir : directions) {
    int x1 = x + dir[0];
    int y1 = y + dir[1];
    // 判断新的节点是否满足条件
    // 1. 在矩形范围内移动
    // 2. 新的节点未被访问过
    // 3. 两个节点上的值相差小于等于1

    if (0 <= x1 && x1 < rows && 0 <= y1 && y1 < columns && !visited[x1][y1] && 
        std::abs(grid[x][y] - grid[x1][y1]) <= 1) {
      // 递归访问新的节点
      move_range += dfs_visit(grid, visited, x1, y1, rows, columns);
    }
  }

  // 返回移动次数
  return move_range;
}

void solution() {
  // 读取行与列
  int rows = 0;
  int columns = 0;
  std::cin >> rows >> columns;
  assert(rows > 0 && columns > 0);
  // 换行符
  std::string line;
  std::getline(std::cin, line);

  // 读取二维数组
  std::vector<std::vector<int>> grid;
  for (int row = 0; row < rows; ++row) {
    std::vector<int> nums(columns);
    for (int& num : nums) {
      std::cin >> num;
    }
    grid.emplace_back(nums);
    // 换行符
    std::getline(std::cin, line);
  }

  // 标记已经访问过了的节点
  std::vector<std::vector<bool>> visited(rows, std::vector<bool>(columns, false));

  int max_move_range = 0;

  // 接下来遍历所有的节点, 找到最大的访问范围.
  for (int row = 0; row < rows; ++row) {
    for (int column = 0; column < columns; ++column) {
      // 如果该节点已经访问过, 就忽略
      if (!visited[row][column]) {
        const int move_range = dfs_visit(grid, visited, row, column, rows, columns);
        max_move_range = std::max(max_move_range, move_range);
      }
    }
  }

  // 打印结果
  std::cout << max_move_range << std::endl;
}

int main() {
  solution();
  return 0;
}