华为笔试题 路径搜索

Posted on | Edited on | In | Comments:

华为笔试题。感觉考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;
}