T1

题目描述

老李在多年前承包了一个养猪场，并引入了若干只种猪，经过这些年的经营，现在养猪场有 N 只猪，编号从 0 到 N - 1（每只猪无论生死都有唯一的编号）；

老李在每只猪生产的时候记下了生产的母猪和出生的小猪，格式：x y1 y2 y3 ...（注：x 为猪妈妈，y1，y2，y3 ... 为新生的猪仔，以上编码均在 0，...，N - 1内，每只猪可以多次生产，每个猪崽只有一个猪妈妈）；

为了防疫需要，要检查任意两只猪是否有亲戚关系（两只猪具有相同的祖先），并计算关系亲疏情况（关系距离，相同编号距离为 0）

输入：第一行输入总数 N

第二行表示后续生产记录行数 M

后续 M 行输入生产记录，以空格分隔

最后一行输入m1，m2；表示待检查的m1和m2编号

输出

一个整数，表示m1，和m2之间的关系距离，无亲戚关系输出 -1

思路

先根据输入 使用 unordered_map 记录每只小猪的猪妈妈是谁，并且找的树的根，将其妈妈编码设定为 -1，作为循环终止条件。

从 m1 开始遍历 m1 的所有祖先，若有 m2，输出当前距离，直接 return 掉；若不是 m2，则使用 unordered_map 把当前祖先到 m1 的距离记下来。

若没结束，再从 m2 开始遍历 m2 的所有祖先，若出现 m1 的祖先，直接将两个距离相加输出，结束。

如果此时还没结束，说明 m1 和 m2 没有公共祖先，则输出 -1，结束；

代码

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {

    int N, M;
    cin >> N >> M;
    unordered_map<int, int> pigs_mum;
    while (M--) {
        int pig_mum, pig_son;
        cin >> pig_mum;
        while (cin >> pig_son) {
            pigs_mum[pig_son] = pig_mum;
            if (cin.get() == '\n') break;
        }
    }
    for (int i = 0; i < N; ++i) {
        if (pigs_mum.find(i) == pigs_mum.end()) {
            pigs_mum[i] = -1;
        }
    }

    int m1, m2;
    cin >> m1 >> m2;
    unordered_map<int, int> distance;
    int tmp = m1, d = 0;
    while (tmp != -1) {
        if (tmp == m2) {
            cout << d << endl;
            return 0;
        }
        else {
            distance[tmp] = d;
            d++;
            tmp = pigs_mum[tmp];
        }
    }
    tmp = m2; d = 0;
    while (tmp != -1) {
        if (distance.find(tmp) != distance.end()) {
            cout << (d + distance[tmp]) << endl;
            return 0;
        }
        else {
            d++;
            tmp = pigs_mum[tmp];
        }
    }
    cout << -1 << endl;

    return 0;
}

T2

题目描述：

在一个 M * N 的街区种，有一个士兵 S 和一个敌人 E，表示 X 为无法通过的街区，标识 B 为可以通过的街区；士兵在一个单位时间内可以从一个街区移动到相邻的街区（士兵每次只能水平或者垂直方向移动一个街区）；士兵每次改变方向时，需要额外花费一个单位的时间（士兵第一次移动一个街区时，不用考虑其初始方向，即只需要一个单位时间即可到达相邻街区）。计算士兵 S 最少 需要多少时间才能到达 E 所在的街区。

输入：第一行两个数组，表示街区大小，M行，N列；

接下来M行，每行N个字母，字母 S 表示士兵所在街区，字母 E 表示敌人所在街区，字母 X 表示障碍，字母 B 表示可以经过的街区。（只有一个 S，一个 E）；

输出：最少需要的时间，当士兵 S 永远无法到达敌人 E 所在的街区时，输出 -1；

思路

经典 dfs 题，笔试的时候脑袋抽筋了，搜到终点的时候，忘记 return 了，哎，难受！

代码

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

static int res = INT32_MAX;
void dfs(vector<vector<char>>& map, int i, int j, int step, int dir) {
    if (i < 0 || i >= map.size() || j < 0 || j >= map[0].size()) return;
    if (map[i][j] == 'X' || map[i][j] == 'S') return;
    if (map[i][j] == 'E') {
        res = min(res, step);
        return;
    }
    map[i][j] = 'X';
    int step_plus[4];
    step_plus[0] = (dir == 0 ? 1 : 2);
    step_plus[1] = (dir == 1 ? 1 : 2);
    step_plus[2] = (dir == 2 ? 1 : 2);
    step_plus[3] = (dir == 3 ? 1 : 2);
    dfs(map, i - 1, j, step + step_plus[0], 0);
    dfs(map, i, j + 1, step + step_plus[1], 1);
    dfs(map, i + 1, j, step + step_plus[2], 2);
    dfs(map, i, j - 1, step + step_plus[3], 3);
    map[i][j] = 'B';
}

int main() {

    int m, n;
    cin >> m >> n;
    int start_x, start_y;
    vector<vector<char>> map(m, vector<char>(n));
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < n; ++j) {
            map[i][j] = s[j];
            if (s[j] == 'S') {
                start_x = i;
                start_y = j;
            }
        }
    }

    dfs(map, start_x - 1, start_y, 1, 0);
    dfs(map, start_x, start_y + 1, 1, 1);
    dfs(map, start_x + 1, start_y, 1, 2);
    dfs(map, start_x, start_y - 1, 1, 3);

    if (res == INT32_MAX) cout << -1 << endl;
    else cout << res << endl;

    return 0;
}

T3

题目描述：

某公司停车场安装了一套智慧停车系统，在车辆进入停车场时，系统会自动计算一条最短路径，并为这一条路径在地面点亮导路灯，如果没有可用停车位，则在入口亮起红灯。

为了简化处理，我们使用起始的车道坐标表示停车场入口，用一个二维数组来记录当前的停车情况，如：

8 15 8 1
1 2 2 1 2 2 1 2 2 1 2 2 1 2 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 1 2 1 0 1 3 2 2 2 1 2 2 2
1 2 1 2 2 0 1 3 1 2 1 2 1 2 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 2 2 2 0 2 2 1 1 0 1 2 1 2
2 2 2 2 2 0 2 2 2 2 0 2 2 2 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

• 8 15 表示矩阵的行数 M 值 8，和列数 N 值 15；
• 8 1 表示入口坐标（分别表示行和列，行列号均从1号计数）：8 代表第 8 行，1 代表第 1 列，以空格分割；即表示入口时绿地从这个坐标点开始点亮；
• 矩阵数代表停车场情况，0 代表车道；1 代表空车位；2 代表已停车车位；3 代表柱子，不可通过；

请你根据停车场情况，点亮一条通往可用车位的最短路径。

路径规则：

1. 所有车位为南北向，车辆只能从车位的南侧或北侧的车道进入停车位，不能横向停车；
2. 如果存在相同距离的目标车位，优先选择行坐标比较小的，其次选择列坐标比较小的；
3. 如果到达同一个车位有多条相同距离的路径，有限选择路径节点行坐标和较小的，其次选择列坐标和较小的；

输入：

M N i j

A11 ... A1j ... A1N

...

Ai1 ... Aij  ...  Ain

...

Am1 ... Amj ... Amn

输出：

输出导路灯的路径坐标

如果没有可用的停车位，则输出：-1 -1

如果存在可用的停车位，则输出最短路径（依次输出的每两个数代表一个点）

思路

这就是一个 bfs 搜寻路径的题目，只是需要考虑的点较多；起点是给定的，终点未知，要在搜寻的过程中判断；

题目需要输出路径，所有需要维护一个二维 path 数组来记录路径，记录方式为将 path[i][j] 的值赋为 1， 2， 3， 4，分别表示当前点是从哪个方向搜过来的；

另外需要考虑路径距离相同的情况，题目给定有限考虑行标较小，或行和较小；

所以在 bfs 搜索每个节点的四个方向时，优先 上，在左，然后下，最后右，按照这个顺序去入队列，应该是可以保证最优的（笔试时细节没做好，没有运行出来，所以不确定）

代码

仅代表个人想法，不确定是不是能 accept，题目所给测试案例都能通过；

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

static int dir_x[] = {-1, 0, 1, 0};
static int dir_y[] = {0, -1, 0, 1};

int main() {

    int m, n, begin_x, begin_y;
    cin >> m >> n >> begin_x >> begin_y;
    vector<vector<int>> parking(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> parking[i][j];
        }
    }

    begin_x--;
    begin_y--;

    vector<vector<int>> path(m, vector<int>(n, 0));
    queue<vector<int>> que;
    que.push({begin_x, begin_y});
    parking[begin_x][begin_y] = 3;
    vector<int> end = {-1, -1};
    while (!que.empty()) {
        bool flag = false;
        int size = que.size();
        for (int i = 0; i < size; ++i) {
            vector<int> loc = que.front();
            que.pop();
            for (int i = 0; i < 4; ++i) {
                int next_x = loc[0] + dir_x[i], next_y = loc[1] + dir_y[i];
                if (next_x < 0 || next_x >= m || next_y < 0 || next_y >= n) continue;
                if ((i == 0 || i == 2) && parking[next_x][next_y] == 1) {
                    end = {next_x, next_y};
                    path[next_x][next_y] = i + 1;
                    flag = true;
                    break;
                }
                else if (parking[next_x][next_y] == 0) {
                    que.push({next_x, next_y});
                    parking[next_x][next_y] = 3;
                    path[next_x][next_y] = i + 1;
                }
            }
        }
        if (flag) break;
    }

    if (end[0] == -1 && end[1] == -1) {
        cout << -1 << " " << -1 << endl; 
    }
    else {
        vector<int> outPath;
        int x = end[0], y = end[1];
        while (x != begin_x || y != begin_y) {
            outPath.push_back(y);
            outPath.push_back(x);
            if (path[x][y] == 1) x--;
            if (path[x][y] == 2) y++;
            if (path[x][y] == 3) x++;
            if (path[x][y] == 4) y--;
        }
        outPath.push_back(begin_y);
        outPath.push_back(begin_x);
        for (int i = outPath.size() - 1; i > 0; --i) {
            cout << outPath[i] + 1 << " ";
        }
        cout << outPath[0] + 1 << endl;
    }

    return 0;
}