8.23华为OD机试真题 新系统【抗洪救灾】

抗洪救灾(Java/Py/C/C++/Js/Go)

华为OD机试真题 新系统 华为OD上机考试真题新系统 8月23号 200分题型

华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解

题目内容

某地区发生特大洪水，水位高达

X

X

X，该地区被划分成了

m

×

n

m \\times n

m×n 个区块，各区块海拔高度不同。 被洪水淹没区域的群众已经自发转移到附近的高地，消防官兵需要快速获取未被淹没的高地数量，并派出救援队将群众转移。请你快速帮助消防官兵统计出未被淹没的高地数量，方便消防官兵组织救援。 未淹没的连续区块被识别为同一区域，连续方式包含水平、垂直、斜线方向（8 连通）。

输入描述

• 参数 1：整数 $X$
• 参数 2：整数 $m$
• 参数 3：整数 $n$
• 参数 4：二维数组（$m\times n$

输出描述

一个整数，表示未被淹没的高地区域数量。

样例1

输入

5 3 3
0 0 0
0 9 0
0 0 0

输出

1

说明 只有一个区块高度（9），大于洪水高度（5），因此返回 1！

样例2

输入

3 5 5
2 2 2 2 2
2 9 9 9 2
2 9 9 9 2
2 9 9 9 2
2 2 2 2 2

输出

1

说明 如下矩阵，只有一个中间连续区块高度（9）大于洪水高度 5，因此返回 1。

22222

22222

22222

29992

29992

29992

29992

29992

29992

29992

29992

29992

22222

22222

22222

题解

思路：DFS

• 深度优先的逻辑:
• 将当前区域标记为以防问。
• 判断相邻八个方向是否为未访问并且高度大于X(同时注意边界)， 如果是递归访问对应相邻位置。

C++

#include<bits/stdc++.h>
#include <vector>
using namespace std;

void DFS(vector<vector<int>>& grid,vector<vector<bool>>& vis, int x, int y, int n, int m, int X) {
// 8个方向
int direct[8][2] = {{–1, 0}, {1, 0}, {0, –1}, {0, 1}, {–1, –1}, {1, 1}, {–1, 1}, {1, –1}};
// 防止重复访问
vis[x][y] = true;
for (int i = 0; i < 8; i++) {
int newX = x + direct[i][0];
int newY = y + direct[i][1];
// 超出格子范围
if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] <= X || vis[newX][newY]) {
continue;
}
// 递归访问
DFS(grid, vis, newX, newY, n, m, X);
}
}

int solve(int X, int n, int m, vector<vector<int>>& grid) {
int res = 0;
vector<vector<bool>> vis(m, vector<bool>(m, false));

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 区域数量 + 1 标记连通高地为已访问
if (grid[i][j] > X && !vis[i][j]) {
res++;
DFS(grid, vis, i, j, n, m, X);
}
}
}
return res;
}

int main() {
int X,m, n;
cin >> X >> 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];
}
}
cout << solve(X, n, m, grid);
return 0;

}

JAVA

import java.io.*;
import java.util.*;

public class Main {

static void DFS(int[][] grid, boolean[][] vis, int x, int y, int n, int m, int X) {
// 8个方向
int[][] direct = {
{–1, 0}, {1, 0}, {0, –1}, {0, 1},
{–1, –1}, {1, 1}, {–1, 1}, {1, –1}
};

// 防止重复访问
vis[x][y] = true;

for (int i = 0; i < 8; i++) {
int newX = x + direct[i][0];
int newY = y + direct[i][1];

// 超出格子范围
if (newX < 0 || newX >= m || newY < 0 || newY >= n
|| grid[newX][newY] <= X || vis[newX][newY]) {
continue;
}

// 递归访问
DFS(grid, vis, newX, newY, n, m, X);
}
}

static int solve(int X, int n, int m, int[][] grid) {
int res = 0;
boolean[][] vis = new boolean[m][n];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 区域数量 + 1 标记连通高地为已访问
if (grid[i][j] > X && !vis[i][j]) {
res++;
DFS(grid, vis, i, j, n, m, X);
}
}
}

return res;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int X = sc.nextInt();
int m = sc.nextInt();
int n = sc.nextInt();

int[][] grid = new int[m][n];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = sc.nextInt();
}
}

System.out.print(solve(X, n, m, grid));
}
}

Python

import sys
sys.setrecursionlimit(1000000)
def DFS(grid, vis, x, y, n, m, X):
# 8个方向
direct = [
(–1, 0), (1, 0), (0, –1), (0, 1),
(–1, –1), (1, 1), (–1, 1), (1, –1)
]

# 防止重复访问
vis[x][y] = True

for dx, dy in direct:
newX = x + dx
newY = y + dy

# 超出格子范围
if newX < 0 or newX >= m or newY < 0 or newY >= n \\
or grid[newX][newY] <= X or vis[newX][newY]:
continue

# 递归访问
DFS(grid, vis, newX, newY, n, m, X)

def solve(X, n, m, grid):
res = 0
vis = [[False] * n for _ in range(m)]

for i in range(m):
for j in range(n):
# 区域数量 + 1 标记连通高地为已访问
if grid[i][j] > X and not vis[i][j]:
res += 1
DFS(grid, vis, i, j, n, m, X)

return res

X, m, n = map(int, input().split())

grid = []
for _ in range(m):
grid.append(list(map(int, input().split())))

print(solve(X, n, m, grid))

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

const lines = [];

rl.on('line', (line) => {
lines.push(line);
});

rl.on('close', () => {
let index = 0;

const [X, m, n] = lines[index++].split(' ').map(Number);

const grid = [];
for (let i = 0; i < m; i++) {
grid.push(lines[index++].split(' ').map(Number));
}

function DFS(grid, vis, x, y, n, m, X) {
// 8个方向
const direct = [
[–1, 0], [1, 0], [0, –1], [0, 1],
[–1, –1], [1, 1], [–1, 1], [1, –1]
];

// 防止重复访问
vis[x][y] = true;

for (let i = 0; i < 8; i++) {
const newX = x + direct[i][0];
const newY = y + direct[i][1];

// 超出格子范围
if (newX < 0 || newX >= m || newY < 0 || newY >= n
|| grid[newX][newY] <= X || vis[newX][newY]) {
continue;
}

// 递归访问
DFS(grid, vis, newX, newY, n, m, X);
}
}

function solve(X, n, m, grid) {
let res = 0;
const vis = Array.from(
{ length: m },
() => Array(n).fill(false)
);

for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// 区域数量 + 1 标记连通高地为已访问
if (grid[i][j] > X && !vis[i][j]) {
res++;
DFS(grid, vis, i, j, n, m, X);
}
}
}

return res;
}

console.log(solve(X, n, m, grid));
});

Go

package main

import (
"bufio"
"fmt"
"os"
)

func DFS(grid [][]int, vis [][]bool, x, y, n, m, X int) {
// 8个方向
direct := [8][2]int{
{–1, 0}, {1, 0}, {0, –1}, {0, 1},
{–1, –1}, {1, 1}, {–1, 1}, {1, –1},
}

// 防止重复访问
vis[x][y] = true

for i := 0; i < 8; i++ {
newX := x + direct[i][0]
newY := y + direct[i][1]

// 超出格子范围
if newX < 0 || newX >= m || newY < 0 || newY >= n ||
grid[newX][newY] <= X || vis[newX][newY] {
continue
}

// 递归访问
DFS(grid, vis, newX, newY, n, m, X)
}
}

func solve(X, n, m int, grid [][]int) int {
res := 0
vis := make([][]bool, m)

for i := 0; i < m; i++ {
vis[i] = make([]bool, n)
}

for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
// 区域数量 + 1 标记连通高地为已访问
if grid[i][j] > X && !vis[i][j] {
res++
DFS(grid, vis, i, j, n, m, X)
}
}
}

return res
}

func main() {
in := bufio.NewReader(os.Stdin)

var X, m, n int
fmt.Fscan(in, &X, &m, &n)

grid := make([][]int, m)

for i := 0; i < m; i++ {
grid[i] = make([]int, n)
for j := 0; j < n; j++ {
fmt.Fscan(in, &grid[i][j])
}
}

fmt.Print(solve(X, n, m, grid))
}

C语言

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

void DFS(int grid[][1000], bool vis[][1000],
int x, int y, int n, int m, int X) {
// 8个方向
int direct[8][2] = {
{–1, 0}, {1, 0}, {0, –1}, {0, 1},
{–1, –1}, {1, 1}, {–1, 1}, {1, –1}
};

// 防止重复访问
vis[x][y] = true;

for (int i = 0; i < 8; i++) {
int newX = x + direct[i][0];
int newY = y + direct[i][1];

// 超出格子范围
if (newX < 0 || newX >= m || newY < 0 || newY >= n ||
grid[newX][newY] <= X || vis[newX][newY]) {
continue;
}

// 递归访问
DFS(grid, vis, newX, newY, n, m, X);
}
}

int solve(int X, int n, int m, int grid[][1000]) {
int res = 0;
bool vis[1000][1000] = {false};

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 区域数量 + 1 标记连通高地为已访问
if (grid[i][j] > X && !vis[i][j]) {
res++;
DFS(grid, vis, i, j, n, m, X);
}
}
}

return res;
}

int main() {
int X, m, n;
scanf("%d %d %d", &X, &m, &n);

int grid[1000][1000];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &grid[i][j]);
}
}

printf("%d", solve(X, n, m, grid));

return 0;
}

​