中庸行者 - 华为机试真题题解

alt

给定一个m * n的整数矩阵作为地图，短阵数值为地形高度；
中庸行者选择地图中的任意一点作为起点，尝试往上、下、左、右四个相邻格子移动;
移动时有如下约束:

中庸行者只能上坡或者下坡，不能走到高度相同的点
不允许连续上坡或者连续下坡，需要交替进行，
每个位置只能经过一次，不能重复行走，

请给出中庸行者在本地图内，能连续移动的最大次数。

输入

一个只包含整数的二维数组：

第一行两个数字，分别为行数和每行的列数;
后续数据为矩阵地图内容:
矩阵边长范围:[1, 8];
地形高度范围:[0, 100000];

输出

一个整数，代表中庸行者在本地图内，能连续移动的最大次数。

示例1

输入：
2 2
1 2
4 3

输出：
3

解释： 3 > 4 > 1 > 2

示例2

输入：
3 3
1 2 4
3 5 7
6 8 9

输出：
4

解释： 6 > 3 > 5 > 2 > 4

Java 题解

回溯

遍历每个位置做为起点进行回溯探索最大次数

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt(), n = scanner.nextInt();

        int[][] grid = new int[m][n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                grid[r][c] = scanner.nextInt();
            }
        }

        Solution solution = new Solution();
        System.out.println(solution.solve(grid));

    }
}

class Solution {
    int max;

    public int solve(int[][] g) {
        this.max = 0;
        int m = g.length, n = g[0].length;
        boolean[][] vis = new boolean[m][n];
        // 从每个位置作为起点尝试获取最大的移动步数
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                dfs(g, vis, r, c, 0, true);
                dfs(g, vis, r, c, 0, false);
            }
        }

        return this.max;
    }

    /**
     *
     * @param g 矩阵地图
     * @param vis 访问状态
     * @param r 当前所在位置行
     * @param c 当前所在位置列
     * @param times 已经移动的次数
     * @param up 是否走上坡到达当前位置
     */
    private void dfs(int[][] g, boolean[][] vis, int r, int c, int times, boolean up) {
        this.max = Math.max(max, times);
        int M = g.length, N = g[0].length;
		
        vis[r][c] = true;
        int[] dirs = new int[]{-1, 0, 1, 0, -1};
        for (int k = 1; k < 5; k++) {
            int nr = r + dirs[k - 1], nc = c + dirs[k];
            if (nr < 0 || nc < 0 || nr >= M || nc >= N || vis[nr][nc] || g[nr][nc] == g[r][c]) {
                continue;
            }

            if (up && g[nr][nc] > g[r][c]) continue;
            if (!up && g[nr][nc] < g[r][c]) continue;

            dfs(g, vis, nr, nc, times + 1, !up);
        }
        vis[r][c] = false;
    }
}

Python 题解

from itertools import pairwise

m, n = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(m)]

max_step = 0
vis = [[False] * n for _ in range(m)]

def dfs(r, c, step, up):
    global max_step, m, n
    vis[r][c] = True
    dirs = (-1, 0, 1, 0, -1)
    max_step = max(max_step, step)
    # print(f"({r}, {c}) step: {step}  up: {up}")
    for dr, dc in pairwise(dirs):
        nr, nc = r + dr, c + dc
        if 0 <= nr < m and 0 <= nc < n and not vis[nr][nc] and g[nr][nc] != g[r][c]:
            if up and g[nr][nc] > g[r][c]: continue
            if not up and g[nr][nc] < g[r][c]: continue
            dfs(nr, nc, step + 1, not up)
    vis[r][c] = False

for r in range(m):
    for c in range(n):
        dfs(r, c, 0, True)
        dfs(r, c, 0, False)

print(max_step)

C++ 题解

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int max_step;

/**
*
* @param g 矩阵地图
* @param vis 访问状态
* @param r 当前所在位置行
* @param c 当前所在位置列
* @param times 已经移动的次数
* @param up 是否走上坡到达当前位置
*/
void dfs(vector<vector<int>>& g, vector<vector<bool>>& vis, int r, int c, int times, bool up) {
    max_step = max(max_step, times);
    int M = g.size(), N = g[0].size();
    vis[r][c] = true;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    for (int k = 1; k < 5; k++) {
        int nr = r + dirs[k - 1], nc = c + dirs[k];
        if (nr < 0 || nc < 0 || nr >= M || nc >= N || vis[nr][nc] || g[nr][nc] == g[r][c]) {
            continue;
        }

        if (up && g[nr][nc] > g[r][c])
            continue;


        if (!up && g[nr][nc] < g[r][c])
            continue;


        dfs(g, vis, nr, nc, times + 1, !up);

    }
    vis[r][c] = false;
}

int main() {
    int m, n;
    cin >> m >> n;

    vector<vector<int>> grid(m, vector<int>(n));
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            cin >> grid[r][c];
        }
    }


    vector<vector<bool>> vis(m, vector<bool>(n, false));

    // 从每个位置作为起点尝试获取最大的移动步数
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            dfs(grid, vis, r, c, 0, true);
            dfs(grid, vis, r, c, 0, false);
        }
    }

    cout << max_step << endl;

    return 0;
}