华为OD机试 - 陷阱方格/机器人走迷宫问题 - 动态规划（Python/JS/C/C++ 双机位C卷 200分）

华为OD机试双机位C卷统一考试题库清单（持续收录中）以及考点说明（Python/JS/C/C++）。

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

房间由XY的方格组成，例如下图为6*4的大小。每一个方格以坐标(x, y)描述。

机器人固定从方格(0, 0)出发，只能向东或者向北前进。出口固定为房间的最东北角，如下图的方格(5, 3)。用例保证机器人可以从入口走到出口。

房间有些方格是墙壁，如(4, 1)，机器人不能经过那儿。

有些地方是一旦到达就无法走到出口的，如标记为B的方格，称之为陷阱方格。

有些地方是机器人无法到达的，如标记为A的方格，称之为不可达方格，不可达方格不包括墙壁所在的位置。

如下示例图中，陷阱方格有2个，不可达方格有3个。

请为该机器人实现路径规划功能：给定房间大小、墙壁位置，请计算出陷阱方格与不可达方格分别有多少个。

二、输入描述

第一行为房间的X和Y（0 < X,Y <= 1000）

• 第二行为房间中墙壁的个数N（0 <= N < X*Y）

• 接着下面会有N行墙壁的坐标

同一行中如果有多个数据 以一个空格隔开，用例保证所有的输入数据均合法。（结尾不带 回车换行）

三、输出描述

陷阱方格与不可达方格数量，两个信息在一行中输出，以一个空格隔开。（结尾不带回车换行）

四、测试用例

测试用例1：

1、输入

6 4
5
0 2
1 2
2 2
4 1
5 1

2、输出

2 3

3、说明

该输入对应上图示例中的迷宫，陷阱方格有2个，不可达方格有3个

测试用例2：

1、输入

6 4
4
2 0
2 1
3 0
3 1

2、输出

0 4

3、说明

该输入对应的迷宫如下图，没有陷阱方格，不可达方格有4个，分别是(4, 0) (4, 1) (5, 0) (5, 1)

五、解题思路

用两个二维布尔数组做动态规划：

reachable[y][x] 表示从起点(0,0)只向东/北能否到达该格

canReach[y][x] 表示从该格只向东/北能否到达终点(X-1,Y-1)，等价于从终点反向只向西/南能否到达该格

算法：

1. 正向DP求 reachable
2. 反向DP求 canReach
3. 统计非墙格：reachable为真且canReach为假 -> 陷阱；reachable为假 -> 不可达
   复杂度 O(X*Y)，适配 X,Y<=1000。

六、Python算法源码

importsysdefmain():data=sys.stdin.read().strip().split()ifnotdata:returnit=iter(data)X=int(next(it))Y=int(next(it))N=int(next(it))wall=[[False]*Xfor_inrange(Y)]for_inrange(N):wx=int(next(it))wy=int(next(it))wall[wy][wx]=Truereachable=[[False]*Xfor_inrange(Y)]# 正向DP：从起点只向东/北能否到达foryinrange(Y):forxinrange(X):ifwall[y][x]:continueifx==0andy==0:reachable[y][x]=Trueelse:from_left=x>0andreachable[y][x-1]from_down=y>0andreachable[y-1][x]reachable[y][x]=from_leftorfrom_down can_reach=[[False]*Xfor_inrange(Y)]# 反向DP：从终点反向向西/南能否到达foryinrange(Y-1,-1,-1):forxinrange(X-1,-1,-1):ifwall[y][x]:continueifx==X-1andy==Y-1:can_reach[y][x]=Trueelse:from_right=x+1<Xandcan_reach[y][x+1]from_up=y+1<Yandcan_reach[y+1][x]can_reach[y][x]=from_rightorfrom_up trap=0unreachable=0foryinrange(Y):forxinrange(X):ifwall[y][x]:continueifnotreachable[y][x]:unreachable+=1elifnotcan_reach[y][x]:trap+=1sys.stdout.write(f"{trap}{unreachable}")if__name__=="__main__":main()

七、JavaScript算法源码

constfs=require('fs');constinput=fs.readFileSync(0,'utf8').trim();if(input.length===0)process.exit(0);constdata=input.split(/\s+/).map(Number);letidx=0;constX=data[idx++];constY=data[idx++];constN=data[idx++];constwall=Array.from({length:Y},()=>Array(X).fill(false));for(leti=0;i<N;i++){constwx=data[idx++];constwy=data[idx++];wall[wy][wx]=true;}constreachable=Array.from({length:Y},()=>Array(X).fill(false));// 正向DP：从起点只向东/北能否到达for(lety=0;y<Y;y++){for(letx=0;x<X;x++){if(wall[y][x])continue;if(x===0&&y===0){reachable[y][x]=true;}else{constfromLeft=x>0&&reachable[y][x-1];constfromDown=y>0&&reachable[y-1][x];reachable[y][x]=fromLeft||fromDown;}}}constcanReach=Array.from({length:Y},()=>Array(X).fill(false));// 反向DP：从终点反向向西/南能否到达for(lety=Y-1;y>=0;y--){for(letx=X-1;x>=0;x--){if(wall[y][x])continue;if(x===X-1&&y===Y-1){canReach[y][x]=true;}else{constfromRight=x+1<X&&canReach[y][x+1];constfromUp=y+1<Y&&canReach[y+1][x];canReach[y][x]=fromRight||fromUp;}}}lettrap=0;letunreachable=0;for(lety=0;y<Y;y++){for(letx=0;x<X;x++){if(wall[y][x])continue;if(!reachable[y][x]){unreachable++;}elseif(!canReach[y][x]){trap++;}}}process.stdout.write(`${trap}${unreachable}`);

八、C算法源码

#include<stdio.h>#include<stdlib.h>intmain(){intX,Y;if(scanf("%d %d",&X,&Y)!=2)return0;intN;scanf("%d",&N);intsize=X*Y;// 使用一维数组模拟二维char*wall=(char*)calloc(size,sizeof(char));char*reachable=(char*)calloc(size,sizeof(char));char*canReach=(char*)calloc(size,sizeof(char));for(inti=0;i<N;i++){intwx,wy;scanf("%d %d",&wx,&wy);wall[wy*X+wx]=1;}// 正向DP：从起点只向东/北能否到达for(inty=0;y<Y;y++){for(intx=0;x<X;x++){intidx=y*X+x;if(wall[idx])continue;if(x==0&&y==0){reachable[idx]=1;}else{intfromLeft=(x>0)&&reachable[y*X+(x-1)];intfromDown=(y>0)&&reachable[(y-1)*X+x];reachable[idx]=(fromLeft||fromDown)?1:0;}}}// 反向DP：从终点反向向西/南能否到达for(inty=Y-1;y>=0;y--){for(intx=X-1;x>=0;x--){intidx=y*X+x;if(wall[idx])continue;if(x==X-1&&y==Y-1){canReach[idx]=1;}else{intfromRight=(x+1<X)&&canReach[y*X+(x+1)];intfromUp=(y+1<Y)&&canReach[(y+1)*X+x];canReach[idx]=(fromRight||fromUp)?1:0;}}}inttrap=0,unreachable=0;for(inty=0;y<Y;y++){for(intx=0;x<X;x++){intidx=y*X+x;if(wall[idx])continue;if(!reachable[idx]){unreachable++;}elseif(!canReach[idx]){trap++;}}}printf("%d %d",trap,unreachable);free(wall);free(reachable);free(canReach);return0;}

九、C++算法源码

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intX,Y;if(!(cin>>X>>Y))return0;intN;cin>>N;vector<vector<bool>>wall(Y,vector<bool>(X,false));for(inti=0;i<N;i++){intwx,wy;cin>>wx>>wy;wall[wy][wx]=true;}vector<vector<bool>>reachable(Y,vector<bool>(X,false));// 正向DP：从起点只向东/北能否到达for(inty=0;y<Y;y++){for(intx=0;x<X;x++){if(wall[y][x])continue;if(x==0&&y==0){reachable[y][x]=true;}else{boolfromLeft=x>0&&reachable[y][x-1];boolfromDown=y>0&&reachable[y-1][x];reachable[y][x]=fromLeft||fromDown;}}}vector<vector<bool>>canReach(Y,vector<bool>(X,false));// 反向DP：从终点反向向西/南能否到达for(inty=Y-1;y>=0;y--){for(intx=X-1;x>=0;x--){if(wall[y][x])continue;if(x==X-1&&y==Y-1){canReach[y][x]=true;}else{boolfromRight=x+1<X&&canReach[y][x+1];boolfromUp=y+1<Y&&canReach[y+1][x];canReach[y][x]=fromRight||fromUp;}}}inttrap=0,unreachable=0;for(inty=0;y<Y;y++){for(intx=0;x<X;x++){if(wall[y][x])continue;if(!reachable[y][x]){unreachable++;}elseif(!canReach[y][x]){trap++;}}}cout<<trap<<" "<<unreachable;return0;}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 双机位C卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。