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

时间:2024-02-11 23:27:35 标签:  华为  

题目描述

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

输入描述

  • 第一行输入两个整数 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];
来源:分享自作者个人站点/博客

智能推荐

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

标签:华为  

题目描述 给定一个包含 0 和 1 的二维矩阵。 给定一个初始位置和速度,一个物体从给定的初始位置出发,在给定的速度下进行移动,遇到矩阵的边缘则发生镜面发射。 无论物体经过 0 还是 1,都不影响其速度。 请计算并给出经过 t 时间单位后,物体经过 1 点的次数。 矩阵以左上角位置为 [0, 0](列(x),行(y)),例如下面A点坐标为 [2, 1](第二列,第一行)

标签:华为  

题目描述 给定一个有向图,图中可能包含有环,图使用二维矩阵表示,每一行的第一列表示起始节点,第二列表示终止节点,如 [0, 1] 表示从 0 到 1 的路径。 每个节点用正整数表示。 求这个数据的首节点与尾节点,题目给的用例会是一个首节点,但可能存在多个尾节点。同时图中可能含有环。如果图中含有环,返回 [-1]。 说明:入度为0是首节点,出度为0是尾节点。

标签:节点  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

题目背景 贫如洗的椎夫阿里巴巴在去砍柴的路上&#xff0c;无意中发现了强盗集团的藏宝地&#xff0c;藏宝地有编号从0-N的箱子&#xff0c;每个箱子上面有一人数字&#xff0c;箱子排列成一个环&#xff0c;编号最大的箱子的下一个是编号为0的箱子。请输出

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

1、题目描述 【日志首次上报最多积分】 日志采集是运维系统的的核心组件。日志是按行生成&#xff0c;每行记做一条&#xff0c;由采集系统分批上报。 如果上报太频繁&#xff0c;会对服务端造成

标签:华为  

华为OD2023(C&D卷)机试题库全覆盖,刷题指南点这里 园区参观路径 时间限制:1s&nbsp;空间限制:256MB&nbsp;限定语言:不限 题目描述: 园区某部门举办了Family Day,邀请员工及其家属参加;将公司园区视为一个矩形,起始园区设置在左上角,终点园区设置在右下角;家属参观园区时,只能向右和向下园区前进;求从起始园区到终点园区会有多少条不同的参观路径;

标签:华为  

OD统一考试 题解: Java / Python / C++

标签:华为  

OD统一考试 题解: Java / Python / C++

标签:华为  

OD统一考试 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:攀登者  

OD统一考试 分值: 200分 题解: Java / Python / C++

标签:攀登者  

OD统一考试 分值: 100分 题解: Java / Python / C++

标签:攀登者  

OD统一考试 分值: 200分 题解: Java / Python / C++

标签:攀登者  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

分割数组的最大差值 - 华为OD统一考试 OD统一考试 分值: 100分 题解: Java / Python / C++

标签:华为  

OD统一考试(B卷) 分值: 100分 题解: Java / Python / C++

标签:华为  

OD统一考试 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

猜你喜欢

OD统一考试(C卷) 分值: 100分 题解: Java / Python / C++

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试(C卷) 分值: 100分 题解: Java / Python / C++

标签:华为  

OD统一考试 分值: 200分 题解: Java / Python / C++

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试 分值: 100分 题解: Java / Python / C++

标签:华为  

OD统一考试 (C卷) 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试 题解: Java / Python / C++

标签:华为  

OD统一考试(B卷) 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试(C卷) 分值: 100分 题解: Java / Python / C++

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

SW1配置 vlan 10mac-vlan mac-address 5489-98c3-5611 #pc1 mac地址 mac-vlan mac-address 5489-98c3-5622 #pc2 mac地址 interface GigabitEthernet0/0/1undo port hybrid vlan 1 #禁用交换机默认的vlan 1&#xff0c;避免产生干扰port hybrid untagged vlan 10mac-vlan enableinterface GigabitEthernet0/0/2undo port hybrid vlan 1port hybrid untagged vlan 10mac

标签:华为  

组网需求 如 图 2-12 所示&#xff0c;用户主机 PC 的

标签:华为  

原贴地址&#xff1a;【上海】【深圳】【华为】软件测试工程师 招聘&#xff08;OD 岗&#xff09; · TesterHome ##【岗位职责】 1、参与产品需求分析&#xff0c;编写测试方案&#xff0c;设计测试用例&#xff0c;以及自动化脚本用例的编写和执行&#xff1b; 2、负责自动化测试代码编写、调试、执行和结果分析&#xff1b; 3、根据测试计划执行&#x

标签:华为  

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C&#43;&#43;

标签:华为  

OD统一考试(C卷) 分值: 100分 题解: Java / Python / C++

标签:字符串  

简介如果你不理解 Python 正则表达式,可以参考以下步骤:学习正则表达式的基本语法。正则表达式是一种描述字符串模式的语言,通过一些特殊字符和语法规则来描述字符串的组成和结构。可以在网上找一些正则表达式的教程进行学习,比如《正则表达式30分钟入门教程》。理解 Python 正则表达式的函数和参数。Python 中使用 re 模块来支持正则表达式的操作,其中常用的函数包括 re.match()

标签:地址  正则表达式  python  

一、题目 题目描述&#xff1a; 给定两个字符串str1和str2&#xff0c; str1进行排列组合只要有一个为str2的子串则认为str1是str2的关联子串&#xff0c; 请返回子串在str2的起始位置&#xff0c;若不是关联子串则返回-1。 二、示例 示例1 输入输出示例仅供调试&#xff0c;后台判题数据

标签:华为  

一、题目 题目描述&#xff1a; 篮球(5V5)比赛中&#xff0c;每个球员拥有一个战斗力&#xff0c;每个队伍的所有球员战斗力之和为该队伍的总体战斗力。 现有10个球员准备分为两队进行训练赛&#xff0c;教练希望2个队伍的战斗力差值能够尽可能的小&#xff0c;以达到最佳训练效果。 给出10个球员的战斗力&#xff0c;如果你是教练&#xff0c;你该如何分队&#xff0c;才能达到最佳训练效果?请说出该分队方案下的最小战斗力差值。

标签:华为  

相关问题

相关文章

热门文章

推荐文章

相关标签