【笔试记录】华为 | 20230823 | cpp

获取连通的相邻节点列表

题目描述

在网元内，存在了 N 个转发节点，每个转发节点有自己唯一的标识 TB 且每个节点有 M 个端口，节点间通过端口进行报文通讯。出于业务隔离的需求，服务器内的端口被划分为多个通讯平面(用 VLAN 隔离，每个 VLAN 都有一个 VLAN ID作为标识)

1. 如果两个端口的VLAN ID相同，则说明这两个端口处于同个 VLAN，且处于连通状态;
2. 如果两个端口的VLAN ID不同，则说明这两个端口处于不同 VLAN，彼此不连通;

现给出节点 A 的端口数及其各端口所属的 VLAN ID，以及节点 A 相邻的其他节点和端口信息。 要求获取与节点 A 处于连通状态的所有相邻节点的 TB 列表（按 TB 从小到大顺序输出）

输入描述
第 1 行: M VLAN_ID_1…VLAN_ID_m 数据间有空格隔开，分别表示: 节点 A 有 M 个端口，各个端口所属的 VLAN_ID，即后面 VLAN_ID_m 表示第 m 个端口的 VLAN ID。

其中，网元内节点的端口数量 M 的取值范围为[1,4]; 端口划分 VLAN ID 的取值范围为[1,4];

第 2 行: N 表示与节点 A 相邻的其他节点有 N 个，N 的取值范围为[0,4000)

第 3 行开始，将有 N 行数据，分别描述与节点 A 相邻的节点的 TB 和端口信息

输入格式为: TBx Mx VLAN_ID_xx…VLAN_ID_xm 数据间有空格隔开，

分别表示: 节点 x 的 TBx，有 Mx 个端口，各个端口所属的 VLAN_ID，即后面 VLAN_ID_xm 表示第 m 个端口的 VLAN ID。 其中，网元内节点 TB 的取值范围为(0,4294967295);

输出描述
第 1 行: N

表示与节点 A 连通的相邻节点个数，如 N 为 0，则无需在输出其他信息

第 2 行: TB_1…TB_n

数据间有空格隔开，分别表示：与节点 A 连通的相邻节点的 TB，个数为 N，按从小到大的顺序输出。

输入示例

1 1
3
1024 2 1 2
1023 1 1
1025 3 2 2 3
1
2
3
4
5

输出示例

2
1023 1024
1
2

提示信息
节点 A 有 1 个端口，VLAN ID 为 1。

相邻的 3 个节点中：

节点 1024 有 2 个端口，其中一个端口的 VLAN ID 为 1，与节点 A 连通。

节点 1023 有 1 个端口，VLAN ID 为 1，与节点 A 连通。

节点 1025 的端口 VLAN ID 分别为 2, 2, 3，没有与节点 A 相同的 VLAN ID，不连通。

最终输出连通的 2 个相邻节点 1023 和 1024，按 TB 从小到大排序。

cpp代码

真的是读题半小时，做题五分钟。。。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define MAX 4000
int M;  // 节点A端口数量
int A_VLAN[4];  // 节点A的VLAN ID
int N;  // 节点A相邻节点数量
int N_VLAN[MAX][6];  // 相邻节点的信息
vector<int> result;
 
int main() {
    // 读取节点A的端口数量和VLAN ID
    cin >> M;
    for(int i = 0; i < M; i++) {
        cin >> A_VLAN[i];
    }
     
    // 读取相邻节点的数量
    cin >> N;
     
    // 读取每个相邻节点的TB、端口数量和VLAN ID
    for(int i = 0; i < N; i++) {
        cin >> N_VLAN[i][0] >> N_VLAN[i][1];  // TB和Mx
        bool isConnected = false;  // 标志是否连通
         
        for(int j = 0; j < N_VLAN[i][1]; j++) {
            cin >> N_VLAN[i][j + 2];  // 读取VLAN ID
             
            if(!isConnected){
                // 检查是否有相同的VLAN ID
                for(int k = 0; k < M; k++) {
                    if(N_VLAN[i][j + 2] == A_VLAN[k]) {
                        isConnected = true;
                        break;
                    }
                }
            }
        }
        // 如果连通，将TB添加到结果中
        if(isConnected) {
            result.push_back(N_VLAN[i][0]);
        }
    }
     
    // 对结果进行排序
    sort(result.begin(), result.end());
     
    // 输出结果
    cout << result.size() << endl;
    for(int i = 0; i < result.size(); i++) {
        cout << result[i];
        if(i != result.size() - 1) cout << " ";
    }
     
    return 0;
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58

消息传输

题目描述

在给定的 m x n (1 <= m, n <= 1000) 网格地图 grid 中，分布着一些信号塔，用于区域间通信。

每个单元格可以有以下三种状态：

• 值 0 代表空地，无法传递信号；
• 值 1 代表信号塔 A，在收到消息后，信号塔 A 可以在 1ms 后将信号发送给上下左右四个方向的信号塔；
• 值 2 代表信号塔 B，在收到消息后，信号塔 B 可以在 2ms 后将信号发送给上下左右四个方向的信号塔。

给定一个坐标 (j, k)，输入保证坐标 (j, k) 位置一定有信号塔。在坐标 (j, k) 位置的信号塔触发一个信号。

要求返回网格地图中所有信号塔收到信号的最短时间，单位为 ms。如果有信号塔无法收到信号，则返回 -1。

输入描述
第一行：网格的列数 n。

第二行：网格的行数 m。

第三行：触发信号的信号塔坐标 (j, k)。

接下来的 m 行：每行包含 n 个整数，表示该行网格中每个位置的信号塔安装信息（通过空格间隔每个状态值）。

输出描述
输出返回 网格地图中所有信号塔收到信号的最小时间，单位为ms。如果不可能，返回-1。

输入示例

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

输出示例

4
1

初始答案

感觉这题和京东的皇后移动的最小步数，所以我首要考虑了BFS。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define N 1004
#define pi pair<int, int>
int m, n;   // 网格行数，列数
int j, k;   // 触发信号的信号塔(j, k)
int grid[N][N];
int dx[4] = { -1, 1, 0, 0 }; // 上下左右
int dy[4] = { 0, 0, -1, 1 }; // 上下左右
 
int main() {
    cin >> n >> m;
    cin >> j >> k;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            cin >> grid[r][c];
        }
    }
 
    // 特殊情况：只有一行
    if (m <= 1){
        for(int i = 0; i < n; i++){
            if(i < k && i < n-1 && grid[0][i] != 0 && grid[0][i+1] == 0){
                cout << -1 << endl; 
                return 0;
            }
                 
            if(i > k && i >= 1 && grid[0][i] != 0 && grid[0][i-1] == 0){
                cout << -1 << endl; 
                return 0;
            }
        }
    }
         
    // 特殊情况：只有一列
    if (n <= 1){
        for(int i = 0; i < m; i++){
            if(i < j && i < m-1 && grid[i][0] != 0 && grid[i+1][0] == 0){
                cout << -1 << endl; 
                return 0;
            }
                 
            if(i > j && i >= 1 && grid[i][0] != 0 && grid[i-1][0] == 0){
                cout << -1 << endl; 
                return 0;
            }
        }
    }
 
 
    vector<vector<int>> ttime(m, vector<int>(n, -1));
    int max_time = -1;
    vector<vector<int>> visited(m, vector<int>(n, 0));
    queue<pi> q;  // 队列存放当前信号塔发射信号能够收到的信号塔index
    q.push(pi(j, k));
    visited[j][k] = 1;  // 因为是从(j, k)开始的，所以要设置已访问 
    ttime[j][k] = 0;
    while (!q.empty()) {
        pi cur = q.front(); q.pop();
        int cur_x = cur.first;
        int cur_y = cur.second;
        // 上下左右四种情况分别看看 
        for (int i = 0; i < 4; i++) {
            int q_x = cur_x + dx[i];
            int q_y = cur_y + dy[i];
            // 如果此处没有信号塔，或被访问过，或索引超出范围，就continue 
            if (q_x < 0 || q_x >= m || q_y < 0 || q_y >= n || grid[q_x][q_y] == 0 || visited[q_x][q_y] == 1) {
                // cout << "continue" << endl;
                continue;
            }
            // 将(q_x, q_y)处标记为已访问
            visited[q_x][q_y] = 1;
            // 计算从(cur_x, cur_y)发送信号到(q_x, q_y)的时间（并加上之前的时间） 
            ttime[q_x][q_y] = ttime[cur_x][cur_y] + grid[cur_x][cur_y];
            max_time = max(max_time, ttime[q_x][q_y]);
            // cout << "time: " << time[q_x][q_y] << " max_time: " << max_time << endl;
            q.push(pi(q_x, q_y));
        }
    }
 
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != 0 && ttime[r][c] == -1) {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << max_time << endl;
    return 0;
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

但是这个代码在运行下面这个案例时出现了wrong answer：

运行时间：
85ms
消耗内存：
6780kb
========[test2.in]=========
21
5
3 14
2 1 1 1 2 2 0 2 1 1 0 0 1 1 1 2 2 1 1 1 1
2 1 2 1 1 2 0 2 2 2 2 1 1 2 2 1 2 1 1 1 1
0 1 1 0 2 1 2 1 2 0 1 1 1 2 1 1 0 0 0 2 1
2 1 2 1 1 1 1 0 1 1 1 1 0 2 2 1 2 2 1 2 1
0 2 1 1 2 2 1 0 2 1 2 2 0 1 2 2 1 0 1 2 2

========[test2.out]=========
Expected						      |	Yours
24							      |	30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

后续改进

实在想不出来哪里错了，于是问了chatgpt，有了以下回答：

分析你的代码，发现问题出现在传递时间的计算上。你在计算时间时总是直接加上信号塔的时间，而不是根据不同信号塔的不同传递时间来更新时间。因此，存在多次更新时间的情况，导致最终的时间计算错误。

为了修复这个问题，我们需要改进时间的计算方式，并确保每个信号塔只在更短时间内收到信号时才会被更新。

以下是修正后的代码：

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

#define N 1004
#define pi pair<int, int>
#define ti tuple<int, int, int> // (time, x, y)

int m, n;   // 网格行数，列数
int j, k;   // 触发信号的信号塔(j, k)
int grid[N][N];
int dx[4] = { -1, 1, 0, 0 }; // 上下左右
int dy[4] = { 0, 0, -1, 1 }; // 上下左右

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

    vector<vector<int>> ttime(m, vector<int>(n, INT_MAX));
    int max_time = -1;
    vector<vector<int>> visited(m, vector<int>(n, 0));
    priority_queue<ti, vector<ti>, greater<ti>> pq; // 优先队列 (time, x, y)
    pq.push({0, j, k});
    ttime[j][k] = 0;

    while (!pq.empty()) {
        auto [cur_time, cur_x, cur_y] = pq.top();
        pq.pop();

        if (visited[cur_x][cur_y]) continue;
        visited[cur_x][cur_y] = 1;

        for (int i = 0; i < 4; i++) {
            int q_x = cur_x + dx[i];
            int q_y = cur_y + dy[i];

            if (q_x < 0 || q_x >= m || q_y < 0 || q_y >= n || grid[q_x][q_y] == 0) {
                continue;
            }

            int new_time = cur_time + (grid[cur_x][cur_y] == 1 ? 1 : 2);
            if (new_time < ttime[q_x][q_y]) {
                ttime[q_x][q_y] = new_time;
                pq.push({new_time, q_x, q_y});
                max_time = max(max_time, new_time);
            }
        }
    }

    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != 0 && ttime[r][c] == INT_MAX) {
                cout << -1 << endl;
                return 0;
            }
        }
    }

    cout << max_time << endl;
    return 0;
}

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

直接提交试试，发现居然是正确的。。。[大拇指]

主要改动：

1. 引入优先队列：优先队列用于确保总是处理当前最短时间的信号传递。
2. 优化时间更新逻辑：只有当新的时间更短时，才会更新信号塔的时间，并将其加入优先队列。确实，我的初始代码更新时间时没有考虑这个，可能会导致原本是更短的时间被更长的时间更新。

其他题解

这里主要参考卡哥的公众号文章：华为笔试，遥遥领先！

跟我初始答案一样，用的是普通的广搜。但是这里并没有用visited数组来标记访问过的位置，因为不会重复走的，题图里的信号都是正数，根据距离判断大小可以保证不走回头路。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int inf = 1e6;
int main () {
    int n, m, startx, starty;
    cin >> n >> m;
    cin >> startx >> starty;
    vector<vector<int>> grid(m, vector<int>(n));
    vector<vector<int>> dis(m, vector<int>(n, inf));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    queue<pair<int, int>> que;
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    que.push(pair<int, int>(startx, starty));
    dis[startx][starty] = 0;
    while(!que.empty()) {
        pair<int, int> cur = que.front(); que.pop();
        for (int i = 0; i < 4; i++)  {
            int newx = cur.first + dir[i][1];
            int newy = cur.second + dir[i][0];
            if (newx < 0 || newx >= m || newy < 0 || newy >= n || grid[cur.first][cur.second] == 0) continue;

            if (dis[newx][newy] > dis[cur.first][cur.second] + grid[cur.first][cur.second]) {
                dis[newx][newy] = dis[cur.first][cur.second] + grid[cur.first][cur.second];
                que.push(pair<int, int>(newx, newy));
            }
        }
    }
    int result = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dis[i][j] == inf) {
                cout << -1 << endl;
                return 0;
            }
            result = max(result, dis[i][j]);
        }
    }
    cout << result << endl;
}
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
45

在我初始代码的基础上将visited数组去掉，再增加距离判断，就ac了：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define N 1004
#define pi pair<int, int>
const int inf = 1e6;
int m, n;   // 网格行数，列数
int j, k;   // 触发信号的信号塔(j, k)
int grid[N][N];
int dx[4] = { -1, 1, 0, 0 }; // 上下左右
int dy[4] = { 0, 0, -1, 1 }; // 上下左右
 
int main() {
    cin >> n >> m;
    cin >> j >> k;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            cin >> grid[r][c];
        }
    }
 
    // 特殊情况：只有一行
    if (m <= 1){
        for(int i = 0; i < n; i++){
            if(i < k && i < n-1 && grid[0][i] != 0 && grid[0][i+1] == 0){
                cout << -1 << endl; 
                return 0;
            }
                 
            if(i > k && i >= 1 && grid[0][i] != 0 && grid[0][i-1] == 0){
                cout << -1 << endl; 
                return 0;
            }
        }
    }
         
    // 特殊情况：只有一列
    if (n <= 1){
        for(int i = 0; i < m; i++){
            if(i < j && i < m-1 && grid[i][0] != 0 && grid[i+1][0] == 0){
                cout << -1 << endl; 
                return 0;
            }
                 
            if(i > j && i >= 1 && grid[i][0] != 0 && grid[i-1][0] == 0){
                cout << -1 << endl; 
                return 0;
            }
        }
    }
 
 
    vector<vector<int>> ttime(m, vector<int>(n, inf));
    //vector<vector<int>> visited(m, vector<int>(n, 0));
    queue<pi> q;  // 队列存放当前信号塔发射信号能够收到的信号塔index
    q.push(pi(j, k));
    //visited[j][k] = 1;  // 因为是从(j, k)开始的，所以要设置已访问 
    ttime[j][k] = 0;
    while (!q.empty()) {
        pi cur = q.front(); q.pop();
        int cur_x = cur.first;
        int cur_y = cur.second;
        // 上下左右四种情况分别看看 
        for (int i = 0; i < 4; i++) {
            int q_x = cur_x + dx[i];
            int q_y = cur_y + dy[i];
            // 如果此处没有信号塔，或被访问过，或索引超出范围，就continue 
            if (q_x < 0 || q_x >= m || q_y < 0 || q_y >= n || grid[cur_x][cur_y] == 0) {
                continue;
            }
            // 将(q_x, q_y)处标记为已访问
            //visited[q_x][q_y] = 1;
            // 计算从(cur_x, cur_y)发送信号到(q_x, q_y)的时间（并加上之前的时间） 
            if(ttime[q_x][q_y] > ttime[cur_x][cur_y] + grid[cur_x][cur_y]){
                ttime[q_x][q_y] = ttime[cur_x][cur_y] + grid[cur_x][cur_y];
                q.push(pi(q_x, q_y));
            }
                
        }
    }
 
    int result = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != 0 && ttime[r][c] == inf) {
                cout << -1 << endl;
                return 0;
            }
            result = max(result, ttime[r][c]);
        }
    }
    cout << result << endl;
    return 0;
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95