【筆試記錄】華為 | 20230823

獲取連通的相鄰節點列表

題目描述

在網元內，存在了 N 個轉發節點，每個轉發節點有自己唯一的標識 TB 且每個節點有 M 個端口，節點間通過端口進行報文通訊。出于業務隔離的需求，服務器內的端口被劃分為多個通訊平面(用 VLAN 隔離，每個 VLAN 都有一個 VLAN ID作為標識)

如果兩個端口的VLAN ID相同，則說明這兩個端口處于同個 VLAN，且處于連通狀態;
如果兩個端口的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

輸出示例

2
1023 1024

提示信息
節點 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 IDcin >> M;for(int i = 0; i < M; i++) {cin >> A_VLAN[i];}// 讀取相鄰節點的數量cin >> N;// 讀取每個相鄰節點的TB、端口數量和VLAN IDfor(int i = 0; i < N; i++) {cin >> N_VLAN[i][0] >> N_VLAN[i][1];  // TB和Mxbool isConnected = false;  // 標志是否連通for(int j = 0; j < N_VLAN[i][1]; j++) {cin >> N_VLAN[i][j + 2];  // 讀取VLAN IDif(!isConnected){// 檢查是否有相同的VLAN IDfor(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;
}

消息傳輸

題目描述

在給定的 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。

輸入示例

輸出示例

初始答案

感覺這題和京東的皇后移動的最小步數，所以我首要考慮了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;  // 隊列存放當前信號塔發射信號能夠收到的信號塔indexq.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;// cout << "cur: " << cur_x << ", " << cur_y << "\n";// 上下左右四種情況分別看看 for (int i = 0; i < 4; i++) {int q_x = cur_x + dx[i];int q_y = cur_y + dy[i];// cout << "ques: " << q_x << ", " << q_y << " ";// 如果此處沒有信號塔，或被訪問過，或索引超出范圍，就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;
}

但是這個代碼在運行下面這個案例時出現了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

后續改進

實在想不出來哪里錯了，于是問了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;
}