【100%通过率】华为OD机试真题 C++ 【机器人活动区域】【2022 Q4 |200分】

以你之姓@ 2023-09-24 16:46 19阅读 0赞

### [**华为OD机试- 题目列表 2023Q1 点这里！！**][OD_- _ 2023Q1] ###

### [**2023华为OD机试-刷题指南 点这里！！**][2023_OD_-_] ###

### 题目描述 ###

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

### 输出 ###

### 说明 ###

相邻网格差值绝对值都小于等于 1 ，且为最大区域，对应网格点数目为 6。

### 示例2 ###

输入

2 3

1 3 5

4 1 3

输出

### 解题思路 ###

1.  常规思路应该就是用深度优先搜索dfs解答，用并查集也可以做。

1.  dfs思路是递归每个网格，比较与其上下左右的格子是否满足要求，若满足要求则进入该格子继续重复上述步骤，每个满足要求的格子都存到vector中，最后取size最大的区域所含格子的个数。

1.  并查集的思路是把每个格子分别和其右边和下边的格子比较，是否和当前格子绝对值差<=1，若满足则把这一对格子合并归为一类。最后统计有几类，个数最多的类的个数即为所求。

### 题型总结 ###

1.  无论是并查集还是深度优先搜索，都是有固定的模式，掌握之后就很简单了。

1.  2022Q4新题库中，大大增加了对递归题目的考察力度，大概能占到两成的比例。很多题目都可以用递归解决，但是递归题目门槛还是挺高的，很多同学会被绕晕。但只要掌握其中的技巧之后，就会感觉这类题目是有固定套路的，学会之后就感觉很简单了，和动态规划问题的五个步骤一样，递归的题目也有个做题三部曲。

1.  新题库中递归的题目又可以细分成两类，一类就是机器人这种面向二维矩阵，用dfs做，这一类相对组合方案的题目会难一些，因为模板不是很固定。

1.  另一类就是组合方案的题目，相对于二维数组的递归要简单不少，核心思想是通过回溯算法，枚举出所有可能的组合方案，从这些组合方案中寻找题目要求的最优解。递归时很重要的一点是要找一个终止条件结束递归。新题库中提高了难度，很多递归题目都只有100分，这些题型在2022Q4之前的OD机试中，都是作为200分大题的。

1.  考点分类

*  dfs二维矩阵的题目：机器人，上班之路，开心消消乐，查找单入口空闲区域，计算快递业务主站点

*  组合方案的题目：核酸检测安排，羊狼农夫过河，最少线段覆盖，等和子数组最小和，最大平分数组，组装新的数组，统一限载最小值，硬件产品销售方案，查找充电设备组合

### 考点 ###

深度优先搜索,并查集

### 代码 ###

c++

并查集

#include <iostream>
    #include <vector>
    #include <map>
    using namespace std;
    
    int M,N;
    int f[22501];
    
    int find(int x) {
        return x==f[x]?x:(f[x]=find(f[x]));
    }
    void merge(int i,int j) {
        int a=find(i);
        int b=find(j);
        if(a!=b){
            f[a]=b;
        }
    }
    
    int main() {
        cin>>M>>N;
        int arr[M][N];
        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                cin>>arr[i][j];
            }
        }
    
        for(int i=1;i<=M*N;i++) {
            f[i]=i;
        }
        
        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                int ind=i*N+j+1;
                if(j+1<N && abs(arr[i][j]-arr[i][j+1])<=1) {
                    //cout<<ind<<" "<<ind+1<<endl;
                    merge(ind,ind+1);
                }
                if(i+1<M && abs(arr[i][j]-arr[i+1][j])<=1) {
                    merge(ind,ind+N);
                }
            }
        }
        
        map<int,int> mp;
        for(int i=1;i<=M*N;i++) { //M*N写成M+N了，还死活查不出来
            int a=find(i);
            cout<<a<<endl;
            mp[a]++;
        }
        int res=0;
        for(auto m:mp) {
            if(m.second>res) {
                res=m.second;
            }
        }
        cout<<res<<endl;
        system("pause");
        return 0;
    }

dfs

#include <iostream>
    #include <sstream>
    #include <map>
    #include <set>
    #include <stack>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <vector>
    #include <time.h>
    #include <bitset>
    using namespace std;
    int M,N;
    int res=0;
    void dfs( int i, int j, vector<vector<int>> &arr, vector<int> &vec) {
        int a=arr[i][j];
        arr[i][j]=-1;
        vec.push_back(a);
        if(i-1>=0 && arr[i-1][j]!=-1 && abs(arr[i-1][j]-a)<=1) {//up
            dfs(i-1,j,arr,vec);
        }
        if(i+1<M && arr[i+1][j]!=-1 && abs(arr[i+1][j]-a)<=1) {//down
            dfs(i+1,j,arr,vec);
        }
        if(j-1>=0 && arr[i][j-1]!=-1 && abs(arr[i][j-1]-a)<=1) {//left
            dfs(i,j-1,arr,vec);
        }
        if(j+1<N && arr[i][j+1]!=-1 && abs(arr[i][j+1]-a)<=1) {//right
            dfs(i,j+1,arr,vec);
        }
     }
    int main() {
        cin>>M>>N;
        vector<vector<int>> arr(M,vector<int>(N));
        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                cin>>arr[i][j];
            }
        }
        
        for(int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                if(arr[i][j]!=-1) {
                    vector<int> vec;
                    dfs(i,j,arr,vec);
                    int cnt=vec.size();
                    res=max(res,cnt);
                }
            }
        }
        cout<<res<<endl;
        system("pause");
        return 0;
    }

python

dfs

arr=[]
    def dfs(m,n,i,j):
        global arr
        if i>=m or j>=n or i<0 or j<0 or arr[i][j]==-1:
            return 0
        t=arr[i][j]
        arr[i][j]=-1
        cnt=1
        if i-1>=0 and abs(arr[i-1][j]-t)<=1:
            cnt+=dfs(m,n,i-1,j)
        if i+1<m and abs(arr[i+1][j]-t)<=1:
            cnt+=dfs(m,n,i+1,j)
        if j-1>=0 and abs(arr[i][j-1]-t)<=1:
            cnt+=dfs(m,n,i,j-1)
        if j+1<n and abs(arr[i][j+1]-t)<=1:
            cnt+=dfs(m,n,i,j+1)
        return cnt
    
    m,n=input().split()
    m=int(m)
    n=int(n)
    
    for i in range(m):
        vec=input().split()
        tmp=[]
        for j in vec:
            tmp.append(int(j))
        arr.append(tmp)
    res=0
    for i in range(m):
        for j in range(n):
            if arr[i][j]!=-1:
                tmp=dfs(m,n,i,j)
                res=max(res,tmp)
    print(res)

并查集

class UF:
        def __init__(self,n):
            self.n=n
            self.Fa=[]
        def init(self):
            for i in range(self.n):
                self.Fa.append(i)
        def find(self,x):
            if x==self.Fa[x]:
                return x
            else:
                self.Fa[x]=self.find(self.Fa[x])
                return self.Fa[x]
        def merge(self,x,y):
            a=self.find(x)
            b=self.find(y)
            if a!=b:
                self.Fa[a]=b
    
    arr=[]
    m,n=input().split()
    m=int(m)
    n=int(n)
    for i in range(m):
        vec=input().split()
        tmp=[]
        for j in vec:
            tmp.append(int(j))
        arr.append(tmp)
    
    uf=UF(m*n)
    uf.init()
    for i in range(m):
        for j in range(n):
            if i+1<m and abs(arr[i][j]-arr[i+1][j])<=1:
                uf.merge(i*n+j,i*n+j+n)
            if j+1<n and abs(arr[i][j]-arr[i][j+1])<=1:
                uf.merge(i*n+j,i*n+j+1)
    map={}
    res=0
    for i in range(m*n):
        t=uf.find(i)
        if t not in map:
            map[t]=0
        map[t]+=1
        res=max(res,map[t])
    print(res)

[OD_- _ 2023Q1]: https://blog.csdn.net/goldarmour/article/details/128962271
[2023_OD_-_]: https://blog.csdn.net/goldarmour/article/details/129807099