华为笔试题 路径搜索

华为笔试题。感觉考DFS的使用。

  • 更新:今天被美能华面试官提醒,dfs的判断语句可以写在函数开头,进入的时候再进行判断,这样程序会更简洁。

题目

题目描述

一张N*M的地图上每个点的海拔高度不同;从当前点只能访问上、下、左、右四个点中还没有到达过的点,且下一步选择的点的海拔高度必须高于当前点;求从地图中的点A到点B总的路径条数除以\(10^9\)的余数。地图左上角坐标为(0,0),右下角坐标为(N-1,M-1)。

输入描述

第一行输入两个整数N,M(0<N≤600, 0<M≤600)用空格隔开;接下来N行输入,每行M个整数用空格隔开,代表对应位置的海拔高度(0≤海拔高度≤360000);最后一行四个整数X,Y,Z,W;前两个代表A的坐标为(X,Y);后两个代表B的坐标为(Z,W);输入保证A、B坐标不同,且坐标合法。

输出描述

输出一个整数并换行,整数表示从A到B的总的路径条数除以\(10^9\)的余数。

示例1

输入

1
2
3
4
5
6
4 5
0 1 0 0 0
0 2 3 0 0
0 0 4 5 0
0 0 7 6 0
0 1 3 2

输出

1
2

分析

这题使用带记忆的DFS做,使用DFS的思路搜索路径,并且使用一个visited数组标记是否被访问到。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
#include <string>
using namespace std;

void dfs(int N, int M, int x, int y, int z, int w, int height, long & count, vector<vector<int> >& map, vector<vector<bool> > &visited){
if (x < 0 || y < 0 || x >= N || y >= M || map[x][y] <= height || visited[x][y]) {
return;
}

if (x == z && y == w) {
count++;
return;
}

visited[x][y] = true;
dfs(N, M, x - 1, y, z, w, map[x][y], count, map, visited); // 上
dfs(N, M, x, y - 1, z, w, map[x][y], count, map, visited); // 左
dfs(N, M, x + 1, y, z, w, map[x][y], count, map, visited); // 下
dfs(N, M, x, y + 1, z, w, map[x][y], count, map, visited); // 右
visited[x][y] = false;
}

int main() {
//freopen("input.txt", "r", stdin);
int N, M, X, Y, Z, W;
cin >> N >> M;
vector<vector<int> > map(N, vector<int>(M));
vector<vector<bool> > visited(N, vector<bool>(M));

for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int tmp;
cin >> tmp;
map[i][j] = tmp;
}
}
cin >> X >> Y >> Z >> W;

long count = 0;
dfs(N, M, X, Y, Z, W, -1, count, map, visited);
cout << count % 1000000000 << endl;
return 0;
}
Image