E卷100分题 - 机器人活动区域

题目描述

现有一个机器人,可放置于 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
12345

输出

6
1

说明

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

image-20240825200737270

示例2

输入

2 3
1 3 5
4 1 3
123

输出

1
1

说明

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

image-20240825201116450

解题思路

使用BFS求最大连通分量,规则:当相邻网格的数字编号差值的绝对值小于等于 1 时

Java

import java.util.Scanner;

class Main {
    // 定义四个方向,上下左右
    private static final int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) {
        // 输入处理
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(); // 行数
        int n = in.nextInt(); // 列数
        int[][] matrix = new int[m][n]; // 定义矩阵
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = in.nextInt(); // 读入矩阵中的值
            }
        }

        // 遍历每个点作为起点,求最大活动范围
        int maxRange = 0; // 定义最大活动范围
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean[][] visited = new boolean[m][n]; // 定义是否访问过
                int range = dfs(matrix, visited, i, j); // 深度优先搜索
                maxRange = Math.max(maxRange, range); // 更新最大活动范围
            }
        }

        System.out.println(maxRange); // 输出最大活动范围
    }

    public static int dfs(int[][] matrix, boolean[][] visited, int x, int y) {
        visited[x][y] = true; // 标记当前点已经访问过
        int range = 1; // 定义活动范围
        for (int[] direction : directions) { // 遍历四个方向
            int newX = x + direction[0]; // 新的横坐标
            int newY = y + direction[1]; // 新的纵坐标
            if (newX >= 0 && newX < matrix.length && newY >= 0 && newY < matrix[0].length
                    && !visited[newX][newY] && Math.abs(matrix[newX][newY] - matrix[x][y]) <= 1) { // 判断是否越界、是否访问过、是否符合条件
                range += dfs(matrix, visited, newX, newY); // 更新活动范围
            }
        }
        return range; // 返回活动范围
    }
}

12345678910111213141516171819202122232425262728293031323334353637383940414243444546

Python

import sys

# 定义四个可能的移动方向:右,左,下,上
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

# 使用深度优先搜索(DFS)来探索网格
def dfs(matrix, visited, x, y):
    # 标记当前网格点为已访问
    visited[x][y] = True
    # 初始化当前网格点的范围计数为1
    range = 1
    # 遍历所有可能的移动方向
    for direction in directions:
        newX = x + direction[0]  # 计算新的行坐标
        newY = y + direction[1]  # 计算新的列坐标
        # 检查新坐标是否在网格内部,且未访问过,并且满足编号差值绝对值小于等于1的条件
        if newX >= 0 and newX < len(matrix) and newY >= 0 and newY < len(matrix[0]) \
            and not visited[newX][newY] and abs(matrix[newX][newY] - matrix[x][y]) <= 1:
            # 递归地继续探索并累加可活动的网格点数目
            range += dfs(matrix, visited, newX, newY)
    # 返回从当前网格点出发可活动的最大网格点数目
    return range

# 读取输入数据
m, n = 0, 0  # 初始化网格的行数和列数
matrix = []  # 初始化网格矩阵

# 逐行读取输入
for line in sys.stdin:
    if not m and not n:
        m, n = map(int, line.split())  # 读取网格的行数和列数
    else:
        matrix.append(list(map(int, line.split())))  # 读取网格中的数值
        if len(matrix) == m:  # 如果已经读取完所有行,结束读取
            break

# 寻找机器人可以活动的最大范围
maxRange = 0
for i in range(m):
    for j in range(n):
        visited = [[False] * n for _ in range(m)]  # 初始化访问标记数组
        ranges = dfs(matrix, visited, i, j)  # 对每个网格点执行DFS
        maxRange = max(maxRange, ranges)  # 更新最大活动范围

# 输出机器人可以活动的最大范围对应的网格点数目
print(maxRange)

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647

JavaScript

// 导入readline模块以读取和处理输入数据
const readline = require('readline');

// 创建readline接口,配置输入来自标准输入,输出到标准输出
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

// 定义四个可能的移动方向:右,左,下,上
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

// 使用深度优先搜索(DFS)来探索网格
function dfs(matrix, visited, x, y) {
  visited[x][y] = true;  // 标记当前网格点为已访问
  let range = 1;  // 初始化当前网格点的范围计数为1
  // 遍历所有可能的移动方向
  for (let direction of directions) {
    let newX = x + direction[0];  // 计算新的行坐标
    let newY = y + direction[1];  // 计算新的列坐标
    // 检查新坐标是否在网格内部,且未访问过,并且满足编号差值绝对值小于等于1的条件
    if (newX >= 0 && newX < matrix.length && newY >= 0 && newY < matrix[0].length
        && !visited[newX][newY] && Math.abs(matrix[newX][newY] - matrix[x][y]) <= 1) {
      range += dfs(matrix, visited, newX, newY);  // 递归地继续探索并累加可活动的网格点数目
    }
  }
  return range;  // 返回从当前网格点出发可活动的最大网格点数目
}

let m, n;  // 声明变量m和n来存储网格的行数和列数
let matrix = [];  // 初始化网格矩阵

// 处理每行输入
rl.on('line', (line) => {
  if (!m && !n) {
    [m, n] = line.split(' ').map(Number);  // 解析输入的行数和列数
    return;
  }
  matrix.push(line.split(' ').map(Number));  // 读取网格中的数值
  if (matrix.length === m) {  // 如果已经读取完所有行,关闭输入流
    rl.close();
  }
});

// 输入流关闭后开始处理数据
rl.on('close', () => {
  let maxRange = 0;  // 初始化最大活动范围
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      let visited = Array.from({length: m}, () => Array(n).fill(false));  // 初始化访问标记数组
      let range = dfs(matrix, visited, i, j);  // 对每个网格点执行DFS
      maxRange = Math.max(maxRange, range);  // 更新最大活动范围
    }
  }
  console.log(maxRange);  // 输出机器人可以活动的最大范围对应的网格点数目
});

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657

C++

#include <iostream>
#include <vector>
using namespace std;

// 定义四个方向,上下左右
const vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int x, int y) {
    visited[x][y] = true; // 标记当前点已经访问过
    int range = 1; // 定义活动范围
    for (vector<int> direction : directions) { // 遍历四个方向
        int newX = x + direction[0]; // 新的横坐标
        int newY = y + direction[1]; // 新的纵坐标
        if (newX >= 0 && newX < matrix.size() && newY >= 0 && newY < matrix[0].size()
                && !visited[newX][newY] && abs(matrix[newX][newY] - matrix[x][y]) <= 1) { // 判断是否越界、是否访问过、是否符合条件
            range += dfs(matrix, visited, newX, newY); // 更新活动范围
        }
    }
    return range; // 返回活动范围
}

int main() {
    // 输入处理
    int m, n;
    cin >> m >> n;
    vector<vector<int>> matrix(m, vector<int>(n)); // 定义矩阵
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j]; // 读入矩阵中的值
        }
    }

    // 遍历每个点作为起点,求最大活动范围
    int maxRange = 0; // 定义最大活动范围
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            vector<vector<bool>> visited(m, vector<bool>(n, false)); // 定义是否访问过
            int range = dfs(matrix, visited, i, j); // 深度优先搜索
            maxRange = max(maxRange, range); // 更新最大活动范围
        }
    }

    cout << maxRange << endl; // 输出最大活动范围

    return 0;
}

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647

C语言

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定义四个方向,上下左右
int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

// 深度优先搜索函数
int dfs(int **matrix, bool **visited, int x, int y, int m, int n) {
    visited[x][y] = true; // 标记当前点已经访问过
    int range = 1; // 定义活动范围
    for (int i = 0; i < 4; i++) { // 遍历四个方向
        int newX = x + directions[i][0]; // 新的横坐标
        int newY = y + directions[i][1]; // 新的纵坐标
        // 判断是否越界、是否访问过、是否符合条件
        if (newX >= 0 && newX < m && newY >= 0 && newY < n &&
            !visited[newX][newY] && abs(matrix[newX][newY] - matrix[x][y]) <= 1) {
            range += dfs(matrix, visited, newX, newY, m, n); // 更新活动范围
        }
    }
    return range; // 返回活动范围
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n); // 输入行数和列数

    // 动态分配矩阵空间
    int **matrix = (int **)malloc(m * sizeof(int *));
    for (int i = 0; i < m; i++) {
        matrix[i] = (int *)malloc(n * sizeof(int));
    }

    // 动态分配访问标记数组空间
    bool **visited = (bool **)malloc(m * sizeof(bool *));
    for (int i = 0; i < m; i++) {
        visited[i] = (bool *)malloc(n * sizeof(bool));
    }

    // 读入矩阵中的值
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    int maxRange = 0; // 定义最大活动范围
    // 遍历每个点作为起点,求最大活动范围
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 初始化访问标记数组为未访问
            for (int a = 0; a < m; a++) {
                for (int b = 0; b < n; b++) {
                    visited[a][b] = false;
                }
            }
            int range = dfs(matrix, visited, i, j, m, n); // 深度优先搜索
            if (range > maxRange) {
                maxRange = range; // 更新最大活动范围
            }
        }
    }

    printf("%d\n", maxRange); // 输出最大活动范围

    // 释放分配的内存
    for (int i = 0; i < m; i++) {
        free(matrix[i]);
        free(visited[i]);
    }
    free(matrix);
    free(visited);

    return 0;
}

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
#牛客创作赏金赛#

主要记录自己的刷题日常,学而时习之。

全部评论
A卷的没有吗
点赞 回复 分享
发布于 2024-11-14 13:07 广东

相关推荐

2024-12-24 15:50
华北理工大学 后端
&nbsp;&nbsp;&nbsp;&nbsp;个人背景:机试253,双非一本&nbsp;&nbsp;&nbsp;&nbsp;时间线:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2024年4月22日,机试(滑动窗口100,进制转换100,动态规划跳格子53)&nbsp;hr告诉我必须发邮件当天答完,所以加完班晚上十点多答的,脑袋昏昏沉沉答完,然后hr就消失了&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2024年10月5日,性格测试(正上班,忽然有od&nbsp;hr联系我说有没有空面试,恰好不忙就答应了)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2024年11月25日,资面(hr的常问问题,稳定性,加班看法,期望薪资等)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2024年11月28日,技术一面(回溯&nbsp;手撕全排列,十分钟写出后面试结束)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2024年11月30日,技术二面(动态规划&nbsp;手撕最大子数组的和&nbsp;十分钟解出,面试官升级问题难度“要求打印出有最大和的那个最大子数字组”,只写出了暴力解,让我继续优化,此时连八股再手撕已经超90分钟,心力交瘁,没有写出最优解,遂二面挂)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2024年12月28日,技术三面(贪心&nbsp;加油站问题&nbsp;三十分钟解出暴力解)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;和我沟通的HR说全部部门卡C,这是什么说法?&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;流程到此已经没有推进了,HR和我说大概率是没有机会入职了,但是可以重新机试,再来一轮面试流程(excuse&nbsp;me?&nbsp;wtf?&nbsp;为啥面试都通过了还能给我挂了呢)#华为od##od##面试等了一周没回复,还有戏吗##社招##双非本科的出路是什么?##ai智能作图#
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务