华为OD机试 - 分配土地（ Python C C++ JavaGo JS PHP）

题目描述

从前有个村庄，村民们在各种田地上插上小旗子，每个旗子上都标识了一个数字。现在，村民们想要找出一个包含相同数字的最小矩形区域，并将这块土地分配给对村庄做出巨大贡献的村民。我们需要找出这个矩形区域的最大面积。

输入描述

  • 第一行输入两个整数 m 和 n，分别代表土地的长和宽。
  • 接下来 m 行，每行 n 个整数，代表地图上的具体标识。其中，旗子上的数字为 1-500，未插旗子的土地用 0 标识。

输出描述

输出一个整数，代表此次分配土地时，做出贡献的村民能分配到的最大面积。

示例

在这里插入图片描述

题目解析

这个问题可以通过遍历所有可能的矩形区域来解决。对于每个数字，我们需要找到包含该数字的所有矩形区域，并计算它们的面积。然后，从这些矩形中选择面积最小的一个，作为该数字对应的最小矩形区域。最后，从所有数字对应的最小矩形区域中选择面积最大的一个，作为最终的答案。

然而，这种方法的时间复杂度非常高，因为需要遍历所有可能的矩形区域。在实际应用中，我们可以使用一种更高效的方法来解决这个问题。

观察题目，我们可以发现，对于每个数字，我们只需要找到包含该数字的所有连通区域，并计算它们的面积。然后，从这些连通区域中选择面积最小的一个，作为该数字对应的最小矩形区域。这样，我们就可以将问题转化为寻找连通区域的问题。

为了找到包含某个数字的所有连通区域，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法。从每个包含该数字的点开始搜索，直到找到所有与该点连通的点。然后，计算这些点的最小矩形区域，并更新该数字对应的最小矩形区域。

最后，从所有数字对应的最小矩形区域中选择面积最大的一个作为最终的答案。

  1. 创建一个二维数组来存储地图上的标识。
  2. 对于每个数字（1-500），使用 DFS 或 BFS 找到包含该数字的所有连通区域，并计算它们的面积。可以使用一个辅助数组来标记已经访问过的点。
  3. 对于每个连通区域，计算其最小矩形区域的面积。可以通过找到连通区域中所有点的最小和最大坐标来实现。
  4. 更新该数字对应的最小矩形区域的面积。可以使用一个哈希表来存储每个数字对应的最小矩形区域的面积。
  5. 从哈希表中选择面积最大的值作为最终的答案。
  6. 输出答案。

Python代码实现

def dfs(grid, row, col, num, visited):# 检查边界条件和访问状态if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or visited[row][col] or grid[row][col] != num:return 0# 标记当前位置为已访问visited[row][col] = True# 向四个方向递归搜索，并计算连通区域的面积area = 1directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]for dx, dy in directions:area += dfs(grid, row + dx, col + dy, num, visited)return areadef find_min_rectangle_area(grid):if not grid or not grid[0]:return 0m, n = len(grid), len(grid[0])visited = [[False] * n for _ in range(m)]min_area = float('inf')  # 初始化为无穷大# 遍历所有数字和对应的位置for i in range(m):for j in range(n):if not visited[i][j] and grid[i][j] != 0:num = grid[i][j]area = dfs(grid, i, j, num, visited)# 找到最小矩形面积min_area = min(min_area, area)# 如果没有找到有效的矩形区域，返回0return min_area if min_area != float('inf') else 0# 示例输入
m, n = 4, 4
grid = [[1, 1, 1, 1],[1, 0, 0, 1],[1, 0, 1, 1],[1, 1, 1, 1]
]# 计算并输出最小矩形面积
print(find_min_rectangle_area(grid))  # 输出应为4，因为最小矩形区域是2x2的

C++代码实现

#include <iostream>  
#include <vector>  
#include <algorithm>  using namespace std;  // 方向数组，用于DFS中的四个方向移动  
const int dx[] = {-1, 1, 0, 0};  
const int dy[] = {0, 0, -1, 1};  // DFS函数，计算以(row, col)为起点的连通区域面积  
int dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int row, int col, int num) {  if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() ||  visited[row][col] || grid[row][col] != num) {  return 0;  }  visited[row][col] = true;  int area = 1;  for (int i = 0; i < 4; ++i) {  area += dfs(grid, visited, row + dx[i], col + dy[i], num);  }  return area;  
}  // 主函数，寻找最小矩形区域的面积  
int findMinRectangleArea(vector<vector<int>>& grid) {  if (grid.empty() || grid[0].empty()) return 0;  int m = grid.size();  int n = grid[0].size();  int minArea = INT_MAX;  // 对每个非零数字进行遍历  for (int i = 0; i < m; ++i) {  for (int j = 0; j < n; ++j) {  if (grid[i][j] != 0) {  vector<vector<bool>> visited(m, vector<bool>(n, false));  int num = grid[i][j];  int area = dfs(grid, visited, i, j, num);  minArea = min(minArea, area);  }  }  }  // 如果没有找到有效的矩形区域，返回0  return (minArea == INT_MAX) ? 0 : minArea;  
}  int main() {  int m, n;  cin >> m >> n;  vector<vector<int>> grid(m, vector<int>(n));  for (int i = 0; i < m; ++i) {  for (int j = 0; j < n; ++j) {  cin >> grid[i][j];  }  }  int result = findMinRectangleArea(grid);  cout << "The minimum rectangle area is: " << result << endl;  return 0;  
}

C代码实现

#include <stdio.h>
#include <stdlib.h>using namespace std;const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};int dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int row, int col, int num) {if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() ||visited[row][col] || grid[row][col] != num) {return 0;}visited[row][col] = true;int area = 1;for (int i = 0; i < 4; ++i) {area += dfs(grid, visited, row + dx[i], col + dy[i], num);}return area;
}int findMinRectangleArea(vector<vector<int>>& grid) {if (grid.empty() || grid[0].empty()) return 0;int m = grid.size();int n = grid[0].size();int minArea = INT_MAX;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] != 0) {vector<vector<bool>> visited(m, vector<bool>(n, false));int num = grid[i][j];int area = dfs(grid, visited, i, j, num);minArea = min(minArea, area);}}}return (minArea == INT_MAX) ? 0 : minArea;
}int main() {int m, n;scanf("%d %d", &m, &n);vector<vector<int>> grid(m, vector<int>(n));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {scanf("%d", &grid[i][j]);}}int result = findMinRectangleArea(grid);printf("The minimum rectangle area is: %d\n", result);return 0;
}

Java代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("Enter the number of rows and columns:");int m = scanner.nextInt();int n = scanner.nextInt();int[][] grid = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {grid[i][j] = scanner.nextInt();}}int result = findMinRectangleArea(grid);System.out.println("The minimum rectangle area is: " + result);}public static int findMinRectangleArea(int[][] grid) {if (grid.length == 0 || grid[0].length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int minArea = Integer.MAX_VALUE;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] != 0) {boolean[][] visited = new boolean[m][n];int num = grid[i][j];int area = dfs(grid, visited, i, j, num);minArea = Math.min(minArea, area);}}}return minArea == Integer.MAX_VALUE ? 0 : minArea;}public static int dfs(int[][] grid, boolean[][] visited, int row, int col, int num) {if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length ||visited[row][col] || grid[row][col] != num) {return 0;}visited[row][col] = true;int area = 1;for (int i = 0; i < 4; i++) {area += dfs(grid, visited, row + dx[i], col + dy[i], num);}return area;}private static int[] dx = {-1, 1, 0, 0};private static int[] dy = {0, 0, -1, 1};
}

Go代码实现

package mainimport ("container/heap""fmt""math/rand""strconv""time"
)const (dx = [4]int{-1, 1, 0, 0}dy = [4]int{0, 0, -1, 1}
)func dfs(grid [][]int, visited [][]bool, row, col, num int) int {if row < 0 || row >= len(grid) || col < 0 || col >= len(grid[0]) ||visited[row][col] || grid[row][col] != num {return 0}visited[row][col] = truearea := 1for i := 0; i < 4; i++ {area += dfs(grid, visited, row+dx[i], col+dy[i], num)}return area
}func findMinRectangleArea(grid [][]int) int {m, n := len(grid), len(grid[0])minArea := 0for i := 0; i < m; i++ {for j := 0; j < n; j++ {if grid[i][j] != 0 {visited := make([][]bool, m)for k := range visited {visited[k] = make([]bool, n)}num := grid[i][j]area := dfs(grid, visited, i, j, num)if minArea == 0 || area < minArea {minArea = area}}}}if minArea == 0 {return 0}return minArea
}func main() {var m, n intfmt.Scan(&m, &n)grid := make([][]int, m)for i := range grid {grid[i] = make([]int, n)}for i := 0; i < m; i++ {for j := 0; j < n; j++ {fmt.Scan(&grid[i][j])}}result := findMinRectangleArea(grid)fmt.Println("The minimum rectangle area is:", result)
}

PHP代码实现

<?phpfunction findMinRectangleArea($grid) {$m = count($grid);$n = count($grid[0]);$minArea = INT_MAX;for ($i = 0; $i < $m; $i++) {for ($j = 0; $j < $n; $j++) {if ($grid[$i][$j] != 0) {$visited = array_fill(0, $m, array_fill(0, $n, false));$num = $grid[$i][$j];$area = $this->dfs($grid, $visited, $i, $j, $num);$minArea = min($minArea, $area);}}}return $minArea == INT_MAX ? 0 : $minArea;
}private function dfs($grid, $visited, $row, $col, $num) {if ($row < 0 || $row >= count($grid) || $col < 0 || $col >= count($grid[0]) ||$visited[$row][$col] || $grid[$row][$col] != $num) {return 0;}$visited[$row][$col] = true;$area = 1;for ($i = 0; $i < 4; $i++) {$area += $this->dfs($grid, $visited, $row + $this->dx[$i], $col + $this->dy[$i], $num);}return $area;
}private $dx = array(-1, 1, 0, 0);
private $dy = array(0, 0, -1, 1);$grid = array(// 示例数据array(1, 1, 1, 0, 0),array(1, 1, 1, 0, 0),array(1, 1, 1, 0, 0),array(0, 0, 0, 0, 0),array(0, 0, 0, 0, 0)
);echo "Enter the number of rows and columns:" . PHP_EOL;
$m = intval(fgets(STDIN));
$n = intval(fgets(STDIN));
$grid = array_fill(0, $m, array_fill(0, $n, 0));
for ($i = 0; $i < $m; $i++) {for ($j = 0; $j < $n; $j++) {$grid[$i][$j] = intval(fgets(STDIN));}
}$result = findMinRectangleArea($grid);
echo "The minimum rectangle area is: " . $result . PHP_EOL;

JS代码实现

const { Your_function } = require(‘Your_script’);function main() {const scanner = require('scanner');console.log('Enter the number of rows and columns:');const m = scanner.nextInt();const n = scanner.nextInt();const grid = new Array(m).fill(0).map(() => new Array(n).fill(0));for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {grid[i][j] = scanner.nextInt();}}const result = findMinRectangleArea(grid);console.log('The minimum rectangle area is: ' + result);
}function findMinRectangleArea(grid) {if (grid.length === 0 || grid[0].length === 0) {return 0;}const m = grid.length;const n = grid[0].length;let minArea = Infinity;for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (grid[i][j] !== 0) {const visited = new Array(m).fill(0).map(() => new Array(n).fill(false));const num = grid[i][j];const area = dfs(grid, visited, i, j, num);minArea = Math.min(minArea, area);}}}return minArea === Infinity ? 0 : minArea;
}function dfs(grid, visited, row, col, num) {if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length ||visited[row][col] || grid[row][col] !== num) {return 0;}visited[row][col] = true;let area = 1;for (let i = 0; i < 4; i++) {area += dfs(grid, visited, row + dx[i], col + dy[i], num);}return area;
}const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/257351.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

修改npm 的运行命令详解

修改npm 的运行命令详解

在Node.js和npm中&#xff0c;你可以通过修改package.json文件中的scripts部分来定义和运行自定义的npm脚本。这些脚本可以是任何你希望在项目中运行的命令&#xff0c;包括启动服务器、运行测试、构建项目等。下面是一些修改npm运行命令的详解和代码示例。 修改npm运行命令的…
阅读更多...
python 基础知识点（蓝桥杯python科目个人复习计划41）

python 基础知识点（蓝桥杯python科目个人复习计划41）

今日复习内容&#xff1a;动态规划&#xff08;基础&#xff09; 动态规划是一种解决多阶段决策过程中最优化问题的数学方法和算法思想。它通常用于解决具有重叠子问题和最优子结构性质的问题&#xff0c;通常将问题划分为相互重叠的子问题&#xff0c;利用子问题的解来求解原…
阅读更多...
Git分支和迭代流程

Git分支和迭代流程

Git分支 feature分支&#xff1a;功能分支 dev分支&#xff1a;开发分支 test分支&#xff1a;测试分支 master分支&#xff1a;生产环境分支 hotfix分支&#xff1a;bug修复分支。从master拉取&#xff0c;修复并测试完成merge回master和dev。 某些团队可能还会有 reale…
阅读更多...
移动机器人激光SLAM导航（五）：Cartographer SLAM 篇

移动机器人激光SLAM导航（五）：Cartographer SLAM 篇

参考 Cartographer 官方文档Cartographer 从入门到精通 1. Cartographer 安装 1.1 前置条件 推荐在刚装好的 Ubuntu 16.04 或 Ubuntu 18.04 上进行编译ROS 安装&#xff1a;ROS学习1&#xff1a;ROS概述与环境搭建 1.2 依赖库安装 资源下载完解压并执行以下指令 https://pa…
阅读更多...
Vue项目创建和nodejs使用

Vue项目创建和nodejs使用

Vue项目创建和nodejs使用 一、环境准备1.1.安装 node.js【下载历史版本node-v14.21.3-x64】1.2.安装1.3.检查是否安装成功&#xff1a;1.4.在Node下新建两个文件夹 node_global和node_cache并设置权限1.5.配置npm在安装全局模块时的路径和缓存cache的路径1.6.配置系统变量&…
阅读更多...
Linux多线程[二]

Linux多线程[二]

引入知识 进程在线程内部执行是OS的系统调度单位。 内核中针对地址空间&#xff0c;有一种特殊的结构&#xff0c;VM_area_struct。这个用来控制虚拟内存中每个malloc等申请的空间&#xff0c;来区别每个malloc的是对应的堆区哪一段。OS可以做到资源的精细度划分。 对于磁盘…
阅读更多...
C#调用WechatOCR.exe实现本地OCR文字识别

C#调用WechatOCR.exe实现本地OCR文字识别

最近遇到一个需求&#xff1a;有大量的扫描件需要还原为可编辑的文本&#xff0c;很显然需要用到图片OCR识别为文字技术。本来以为这个技术很普遍的&#xff0c;结果用了几个开源库&#xff0c;效果不理想。后来&#xff0c;用了取巧的方法&#xff0c;直接使用了WX的OCR识别模…
阅读更多...
算法与数据结构

算法与数据结构

算法与数据结构 前言 什么是算法和数据结构&#xff1f; 你可能会在一些教材上看到这句话&#xff1a; 程序 算法 数据结构 算法&#xff08;Algorithm&#xff09;&#xff1a;是指解题方案的准确而完整的描述&#xff0c;是一系列解决问题的清晰指令&#xff0c;算法代…
阅读更多...
【Tomcat】:One or more listeners failed to start.报错解决方案

【Tomcat】:One or more listeners failed to start.报错解决方案

报错信息:One or more listeners failed to start. Full details will be found in the appropriate container log file. 具体就是web.xml此配置报错: 服务器启动错误Tomcat:One or more listeners failed to start.报错解决方案 IDEA:在使用IDEA运行SSM项目的时候 , Tomcat运…
阅读更多...
ChatGpt报错:We ran into an issue while authenticating you解决办法

ChatGpt报错:We ran into an issue while authenticating you解决办法

在登录ChatGpt时报错&#xff1a;Oops&#xff01;,We ran into an issue while authenticating you.(我们在验证您时遇到问题)&#xff0c;记录一下解决过程。 完整报错&#xff1a; We ran into an issue while authenticating you. If this issue persists, please contact…
阅读更多...
怎么使用ChatGPT提高工作效率？

怎么使用ChatGPT提高工作效率？

怎么使用ChatGPT提高工作效率&#xff0c;这是一个有趣的话题。 相信不同的人有不同的观点&#xff0c;大家的知识背景和从事的工作都不完全相同&#xff0c;所以最终ChatGPT能起到的作用也不一样。 在编程过程中&#xff0c;如果我们要找一个库&#xff0c;我们最先做的肯定…
阅读更多...
[缓存] - 2.分布式缓存重磅中间件 Redis

[缓存] - 2.分布式缓存重磅中间件 Redis

1. 高性能 尽量使用短key 不要存过大的数据 避免使用keys *&#xff1a;使用SCAN,来代替 在存到Redis之前压缩数据 设置 key 有效期 选择回收策略(maxmemory-policy) 减少不必要的连接 限制redis的内存大小&#xff08;防止swap&#xff0c;OOM&#xff09; slowLog …
阅读更多...
C语言第二十三弹---指针(七)

C语言第二十三弹---指针(七)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 指针 1、sizeof和strlen的对比 1.1、sizeof 1.2、strlen 1.3、sizeof 和 strlen的对比 2、数组和指针笔试题解析 2.1、⼀维数组 2.2、二维数组 总结 1、si…
阅读更多...
每日五道java面试题之java基础篇（八）

每日五道java面试题之java基础篇（八）

第一题.CopyOnWriteArrayList的底层原理是怎样的 ⾸先CopyOnWriteArrayList内部也是⽤过数组来实现的&#xff0c;在向CopyOnWriteArrayList添加元素时&#xff0c;会复制⼀个新的数组&#xff0c;写操作在新数组上进⾏&#xff0c;读操作在原数组上进⾏并且&#xff0c;写操作…
阅读更多...
OpenGL-ES 学习(1)---- AlphaBlend

OpenGL-ES 学习(1)---- AlphaBlend

AlphaBlend OpenGL-ES 混合本质上是将 2 个片元的颜色进行调和(一般是求和操作)&#xff0c;产生一个新的颜色 OpenGL ES 混合发生在片元通过各项测试之后&#xff0c;准备进入帧缓冲区的片元和原有的片元按照特定比例加权计算出最终片元的颜色值&#xff0c;不再是新&#xf…
阅读更多...
Prometheus服务器、Prometheus被监控端、Grafana、监控MySQL数据库、自动发现概述、配置自动发现、Alertmanager

Prometheus服务器、Prometheus被监控端、Grafana、监控MySQL数据库、自动发现概述、配置自动发现、Alertmanager

目录 Prometheus概述 部署Prometheus服务器 环境说明&#xff1a; 配置时间 安装Prometheus服务器 添加被监控端 部署通用的监控exporter Grafana 概述 部署Grafana 展示node1的监控信息 监控MySQL数据库 配置MySQL 配置mysql exporter 配置mysql exporter 配置…
阅读更多...
算法沉淀——字符串（leetcode真题剖析）

算法沉淀——字符串（leetcode真题剖析）

算法沉淀——字符串 01.最长公共前缀02.最长回文子串03.二进制求和04.字符串相乘 01.最长公共前缀 题目链接&#xff1a;https://leetcode.cn/problems/longest-common-prefix/ 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀&#xff0c;返回空字符串…
阅读更多...
VS Code之Java代码重构和源代码操作

VS Code之Java代码重构和源代码操作

文章目录 支持的代码操作列表调用重构分配变量字段和局部变量的差别Assign statement to new local variable在有参构造函数中将参数指定成一个新的字段 将匿名类转换为嵌套类什么是匿名类&#xff1f;匿名类转换为嵌套类的完整演示 转换为Lambda表达式Lambda 表达式是什么?转…
阅读更多...
【51单片机】串口（江科大）

【51单片机】串口（江科大）

8.1串口通信 1.串口介绍 2.硬件电路 3.电平标准 电平标准是数据1和数据0的表达方式,是传输线缆中人为规定的电压与数据的对应关系,串口常用的电平标准有如下三种: 电平标准是数据1和数据O的表达方式,是传输线缆中人为规定的电 压与数据的对应关系,串口常用的电平标准有如下…
阅读更多...
C++类和对象-C++运算符重载-＞加号运算符重载、左移运算符重载、递增运算符重载、赋值运算符重载、关系运算符重载、函数调用运算符重载

C++类和对象-C++运算符重载-＞加号运算符重载、左移运算符重载、递增运算符重载、赋值运算符重载、关系运算符重载、函数调用运算符重载

#include<iostream> using namespace std; //加号运算符重载 class Person { public: Person() {}; Person(int a, int b) { this->m_A a; this->m_B b; } //1.成员函数实现 号运算符重载 Person operator(const Per…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023