荣耀软件算法笔试4-22

校招一对一进阶提高，带领学员斩获大厂实习秋招春招offer！！！

****************

题目1：

给定一个正整数数组，最大为100个成员，从第一个成员开始，走到数组最后一个成员最少的步骤数，第一步必须从第一元素开始，1<=步长<len/2，第二步开始以所在成员的数字走相应的步数，如果目标不可达返回-1，只输出最少的步骤数量

输入描述

由正整数组成的数组，以空格分隔，数组长度小于100，请自行解析数据数量。

输出描述

正整数，表示最少的步数，如果不存在输出-1

输入

7 5 9 4 2 6 8 3 5 4 3 9

输出

2

#include <iostream>
#include <vector>
#include <sstream>
#include <limits>

using namespace std;

int min_steps(const vector<int>& nums) {
    int n = nums.size();
    vector<int> steps(n, numeric_limits<int>::max());
    steps[0] = 0;

    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j <= i + nums[i] && j < n; ++j) {
            steps[j] = min(steps[j], steps[i] + 1);
        }
    }

    return steps[n - 1] == numeric_limits<int>::max() ? -1 : steps[n - 1];
}

int main() {
    string input;
    getline(cin, input);
    stringstream ss(input);
    int num;
    vector<int> nums;

    while (ss >> num) {
        nums.push_back(num);
    }
    
    int result = min_steps(nums);
    cout << result << endl;

    return 0;
}

题目2：

在nxn方阵里填入1，2，… ，nxn，要求填成蛇形。元素1从右上角开始，顺时针排列，例如，n=4时方阵为: 18 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 n <= 8。

输入描述

大于1不超过8的方阵的维数。

输出描述

打印填充后的方阵，每个元素占3个字符位宽。

示例1

输入

4

输出

10 11 12 1 

9  16 13 2 

8  15 14 3 

7 6  5  4 

#include <iostream>
#include <vector>

using namespace std;

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

    vector<vector<int>> matrix(n, vector<int>(n, 0));
    vector<vector<int>> dirs = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

    int x = 0, y = n - 1, dir = 0, cnt = 1;

    while (cnt <= n * n) {
        matrix[x][y] = cnt;
        cnt++;
        int nx = x + dirs[dir][0];
        int ny = y + dirs[dir][1];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n || matrix[nx][ny] != 0) {
            dir = (dir + 1) % 4;
        }
        x += dirs[dir][0];
        y += dirs[dir][1];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            string space = (matrix[i][j] < 10 ? "  " : " ");
            cout << space << matrix[i][j];
        }
        cout << endl;
    }

    return 0;
}

题目3：

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

输入描述

第一行输入两个整数N,M(O<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

输入

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

输出

2

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int n, m, x, y, z, w;
vector<vector<int>> matrix;
vector<vector<int>> dirs = {{0,1},{1,0},{0,-1},{-1,0}};
map<pair<int, int>, int> dp;

int dfs(int i, int j) {
    if (i == z && j == w) return 1;
    auto it = dp.find({i,j});
    if (it != dp.end()) return it->second;
    int cur = 0;
    for (auto dir : dirs) {
        int ni = i + dir[0], nj = j + dir[1];
        if (ni < 0 || nj < 0 || ni >= n || nj >= m || matrix[i][j] >= matrix[ni][nj]) continue;
        cur += dfs(ni, nj);
    }
    dp[{i,j}] = cur;
    return cur;
}

int main() {
    cin >> n >> m;
    matrix.resize(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    cin >> x >> y >> z >> w;
    cout << dfs(x, y) << endl;
    return 0;
}