华为校招机试 - 网络保卫战（20240410）

雨点打透心脏的1/2处 2024-04-21 08:26 46阅读 0赞

#### 在线OJ测试 ####

[题目详情 - 网络保卫战 - HydroOJ][- _ - HydroOJ]

#### 题目描述 ####

公有云的某个 region 内，N 个网络节点组网情况可以使用一个 N \* N 的矩阵 matrix 表示。

在这个组网图中，matrix\[i\]\[j\] = p 时，表示用户在编号为 i 的节点访问编号为 j 的节点时，必须在 i 节点上具有 ≥ p 的权限等级（ p = 0 时表示无法通过第 i 节点访问 j 节点），如果用户成功访问了 j 节点，那么它在 j 节点上的权限等级调整为 p。

exposed 为一个整数数组，表示暴露在公网上的网络节点的编号列表。

某天扫描发现这批暴露在公网的节点存在被外部恶意攻击风险，且该攻击会影响到可访问的其他节点，并可以持续传递进行攻击。

被恶意攻击的节点从公网访问时，攻击者获得了 ROOT 权限（权限等级为10，即最大值）。

小李是一名网络安全工程师，为了在有限的时间内尽可能的减少故障带来的损失，需要立即将某个节点从公网"下线"。

假设攻击结束时，被攻击过的节点数量为 R ，请帮小李计算出将哪个节点下线能使 R 尽可能小，如果答案有多个节点，返回索引最小的那个节点。

请注意：从公网 "下线" 的节点，不会受到来自公网的攻击，但仍然可能被 "可访问" 的其他节点传递攻击。

#### 输入描述 ####

输入的：

*  第一行是网络节点数量 N
 *  后续的 N 行，每行 N 个数字 v，以空格分割，形成一个 N \* N 的矩阵，表示网络节点组网的矩阵
 *  最后一行，输入 exposed 数组，表示暴露在公网上的网络节点的编号列表，数组元素不会重复

输入范围说明：

*  2 ≤ N ≤ 24
 *  0 ≤ v ≤10
 *  0 ≤ exposed\[i\] ≤ N - 1

#### 输出描述 ####

输出在 exposed 数组中，计划 "下线" 的那个节点的编号。

#### 用例 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">4<br> 1 0 0 0<br> 0 1 2 0<br> 0 1 1 4<br> 0 0 3 1<br> 1 3</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">3</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;"> <p>1,3是公网暴露的节点</p> <p></p> <p>1,2,3三个节点是连通的，但相互访问需要考虑权限等级限制，例如：</p> <p>从1节点登录，访问到2节点后，权限等级不足以访问3号节点，</p> <p></p> 
    <ul> 
     <li>如果将1号节点从公网下线，那3号节点可以先访问2号在访问1号，此时R的值为3</li> 
     <li>如果将3号节点从公网下线，则只能通过1号节点访问到2号节点，而2号节点无法再访问3号节点，此时R的值为2</li> 
    </ul><p>答案选择R值更小的公网节点下线方案，因此答案为3</p> </td> 
  </tr> 
 </tbody> 
</table>

#### 题目解析 ####

题目用例图示如下：

![127db98142114877ad9fab7dac2e1b12.png][]

黑客可以从公网暴露的节点1或节点3中入侵，此时我们有两个选择，下线节点1或节点3：

*  如果下线节点1，那么黑客只能从节点3访问，初始时黑客权限为10

1.  节点3访问节点2需要权限3 < 10，因此黑客可以进入节点2，且黑客权限变为3
2.  节点2访问节点1需要权限1 < 3，因此黑客可以进入节点1，且黑客权限变为1
3.  因此下线节点1时，节点1，2，3会被攻击，R=3

*  如果下线节点3，那么黑客只能从节点1访问，初始时黑客权限为10

1.  节点1访问节点2需要权限2 < 10，因此黑客可以进入节点2，且黑客权限变为2
2.  节点2访问节点3需要权限4 > 2，因此黑客无法进入节点3
3.  因此下线节点3时，节点1,2会被攻击，3不会被攻击，R=2

因此最优策略是R=2，下线节点3。

本题解题策略可以是，遍历exposed每一个节点 i ，作为攻击者的入口节点，初始时攻击者权限permission=10，visited\[i\] = true，表示 i 节点已访问过，然后进行深搜：

*  深搜的下一个节点 j，要满足 matrix\[i\]\[j\] != 0 && permission >= matrix\[i\]\[j\] && !visited\[j\]，进入 j 后，攻击者权限permission变为matrix\[i\]\[j\]
 *  当节点 i 不存在下一个可以进入的节点 j 时，对应递归分支终止

我们只要统计深搜过程中，访问过的节点数量，即为对应入口节点的R值。

当我们计算出exposed每一个节点 i 对应的 R 值后，就可以进行下一步：

遍历exposed每一个节点 i，假设下线节点 i，则exposed剩余节点中最大R值，即为下线节点 i ，攻击者所有攻击的节点数。

最终题解取这个过程中，产生最少攻击节点数的下线节点。

更多细节请看代码实现。

#### JS算法源码 ####

#### Java算法源码 ####

import java.util.*;
    
    public class Main {
        static int n;
        static int[][] matrix;
        static int[] exposed;
    
        static HashMap<Integer, ArrayList<Integer>> next;
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
    
            n = sc.nextInt();
    
            matrix = new int[n][n];
            next = new HashMap<>();
    
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = sc.nextInt();
    
                    next.putIfAbsent(i, new ArrayList<>());
    
                    if (i != j && matrix[i][j] > 0) {
                        next.get(i).add(j);
                    }
                }
            }
    
            // 清空缓冲区
            sc.nextLine();
    
            exposed = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    
            System.out.println(solution());
        }
    
        public static int solution() {
            // 将公网暴露的节点编号升序
            Arrays.sort(exposed);
    
            // R[i] 表示攻击者从节点exposed[i]进入，所能攻击的节点数量
            int[] R = Arrays.stream(exposed).map(nodeIdx -> {
                if (matrix[nodeIdx][nodeIdx] == 0) {
                    return 0;
                }
    
                HashSet<Integer> visited = new HashSet<>();
                visited.add(nodeIdx);
                return dfs(nodeIdx, 10, visited);
            }).toArray();
    
            int min = Integer.MAX_VALUE;
            int idx = -1;
    
            // 下线exposed[i]节点
            for (int i = 0; i < exposed.length; i++) {
                // maxR记录下线exposed[i]节点后，攻击者从其他暴露节点进入所能产生的最大攻击数量
                int maxR = 0;
    
                // 攻击者从exposed[j]进入，则能攻击节点数量为R[j]
                for (int j = 0; j < exposed.length; j++) {
                    // 如果 i == j，则exposed[j]为下线节点，不可进入
                    if (j != i) {
                        maxR = Math.max(maxR, R[j]);
                    }
                }
    
                // 下线exposed[i]节点，则攻击者最多可以攻击maxR个节点，如果maxR < min，则下线exposed[i]节点是更优策略
                if (maxR < min) {
                    min = maxR;
                    idx = exposed[i];
                }
    
            }
    
            return idx;
        }
    
        /**
         * @param i          攻击者进入的节点编号
         * @param permission 攻击者此时的权限
         * @param visited    记录已攻击过的节点
         * @return 从节点i进入，攻击者所能攻击的节点数量
         */
        public static int dfs(int i, int permission, HashSet<Integer> visited) {
            // 可以访问i点，此时被攻击的节点数为1
            int count = 1;
    
            // 找到i节点的下游节点j
            for (int j : next.get(i)) {
                // 如果j已经被访问过，则跳过
                if (visited.contains(j)) continue;
    
                // 如果j未被访问过，且攻击者当前权限大于等于（i访问j所需的权限值），则可以进入j节点
                if (permission >= matrix[i][j]) {
                    // 递归处理
                    visited.add(j);
                    count += dfs(j, matrix[i][j], visited);
                }
            }
    
            // 返回攻击者从i节点进入后，所能攻击的节点数量count
            return count;
        }
    
    
    }

#### Python算法源码 ####

import sys
    
    # 输入获取
    n = int(input())
    matrix = [list(map(int, input().split())) for _ in range(n)]
    exposed = list(map(int, input().split()))
    
    next = {}
    
    
    def dfs(i, permission, visited):
        """
        :param i: 攻击者进入的节点编号
        :param permission: 攻击者此时的权限
        :param visited: 记录已攻击过的节点
        :return: 从节点i进入，攻击者所能攻击的节点数量
        """
        # 可以访问i点，此时被攻击的节点数为1
        count = 1
    
        # 找到i节点的下游节点j
        for j in next[i]:
            # 如果j已经被访问过，则跳过
            if j in visited:
                continue
    
            # 如果j未被访问过，且攻击者当前权限大于等于（i访问j所需的权限值），则可以进入j节点
            if permission >= matrix[i][j]:
                # 递归处理
                visited.add(j)
                count += dfs(j, matrix[i][j], visited)
    
        # 返回攻击者从i节点进入后，所能攻击的节点数量count
        return count
    
    
    # 算法入口
    def solution():
        # 找到i节点可以访问的下游节点
        for i in range(n):
            next[i] = []
            for j in range(n):
                if i != j and matrix[i][j] > 0:
                    next[i].append(j)
    
        # 将公网暴露的节点编号升序
        exposed.sort()
    
        # R[i] 表示攻击者从节点exposed[i]进入，所能攻击的节点数量
        R = [0] * len(exposed)
        for i in range(len(exposed)):
            nodeIdx = exposed[i]
    
            if matrix[nodeIdx][nodeIdx] == 0:
                continue
    
            visited = set()
            visited.add(nodeIdx)
    
            R[i] = dfs(nodeIdx, 10, visited)
    
        minR = sys.maxsize
        idx = -1
    
        # 下线exposed[i]节点
        for i in range(len(exposed)):
            # maxR记录下线exposed[i]节点后，攻击者从其他暴露节点进入所能产生的最大攻击数量
            maxR = 0
    
            # 攻击者从exposed[j]进入，则能攻击节点数量为R[j]
            for j in range(len(exposed)):
                # 如果 i == j，则exposed[j]为下线节点，不可进入
                if j != i:
                    maxR = max(maxR, R[j])
    
            # 下线exposed[i]节点，则攻击者最多可以攻击maxR个节点，如果maxR < min，则下线exposed[i]节点是更优策略
            if maxR < minR:
                minR = maxR
                idx = exposed[i]
    
        return idx
    
    
    # 算法调用
    print(solution())

#### C算法源码 ####

#include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>
    #include <math.h>
    
    #define MAX_N 24
    
    int n;
    int matrix[MAX_N][MAX_N];
    
    int exposed[MAX_N];
    int exposed_size = 0;
    
    /**
     * @param i          攻击者进入的节点编号
     * @param permission 攻击者此时的权限
     * @param visited    记录已攻击过的节点
     * @return 从节点i进入，攻击者所能攻击的节点数量
     */
    int dfs(int i, int permission, int visited[]) {
        // 可以访问i点，此时被攻击的节点数为1
        int count = 1;
    
        // 找到i节点的下游节点j
        for (int j = 0; j < n; j++) {
            // 如果j已经被访问过，则跳过
            if (visited[j]) continue;
    
            // matrix[i][j] == 0 表示 i无法访问j
            // 如果i可以访问j，则当前攻击者权限permission大于等于i访问j的权限，才能进入j
            if (matrix[i][j] != 0 && permission >= matrix[i][j]) {
                // 递归处理
                visited[j] = 1;
                count += dfs(j, matrix[i][j], visited);
            }
        }
    
        // 返回攻击者从i节点进入后，所能攻击的节点数量count
        return count;
    }
    
    int cmp(const void *a, const void *b) {
        return *((int *) a) - *((int *) b);
    }
    
    int solution() {
        // 将公网暴露的节点编号升序
        qsort(exposed, exposed_size, sizeof(int), cmp);
    
        // R[i] 表示攻击者从节点exposed[i]进入，所能攻击的节点数量
        int R[MAX_N] = {0};
        for (int i = 0; i < exposed_size; i++) {
            int nodeIdx = exposed[i];
    
            if (matrix[nodeIdx][nodeIdx] > 0) {
                int visited[MAX_N] = {0};
                visited[nodeIdx] = 1;
    
                R[i] = dfs(nodeIdx, 10, visited);
            }
        }
    
        int min = INT_MAX;
        int idx = -1;
    
        // 下线exposed[i]节点
        for (int i = 0; i < exposed_size; i++) {
            // maxR记录下线exposed[i]节点后，攻击者从其他暴露节点进入所能产生的最大攻击数量
            int maxR = 0;
    
            // 攻击者从exposed[j]进入，则能攻击节点数量为R[j]
            for (int j = 0; j < exposed_size; j++) {
                // 如果 i == j，则exposed[j]为下线节点，不可进入
                if (j != i) {
                    maxR = (int) fmax(maxR, R[j]);
                }
            }
    
            // 下线exposed[i]节点，则攻击者最多可以攻击maxR个节点，如果maxR < min，则下线exposed[i]节点是更优策略
            if (maxR < min) {
                min = maxR;
                idx = exposed[i];
            }
        }
    
        return idx;
    }
    
    int main() {
        scanf("%d", &n);
    
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &matrix[i][j]);
            }
        }
    
        int v;
        while (scanf("%d", &v) != EOF) {
            exposed[exposed_size++] = v;
        }
    
        printf("%d\n", solution());
    
        return 0;
    }

#### C++算法源码 ####

#include <bits/stdc++.h>
    using namespace std;
    
    int n;
    vector<vector<int>> matrix;
    map<int, vector<int>> nxt;
    vector<int> exposed;
    
    /**
     * @param i          攻击者进入的节点编号
     * @param permission 攻击者此时的权限
     * @param visited    记录已攻击过的节点
     * @return 从节点i进入，攻击者所能攻击的节点数量
     */
    int dfs(int i, int permission, set<int> &visited) {
        // 可以访问i点，此时被攻击的节点数为1
        int count = 1;
    
        // 找到i节点的下游节点j
        for (const auto &j: nxt[i]) {
            // 如果j已经被访问过，则跳过
            if (visited.count(j) > 0) continue;
    
            // 如果j未被访问过，且攻击者当前权限大于等于（i访问j所需的权限值），则可以进入j节点
            if (permission >= matrix[i][j]) {
                // 递归处理
                visited.insert(j);
                count += dfs(j, matrix[i][j], visited);
            }
        }
    
        // 返回攻击者从i节点进入后，所能攻击的节点数量count
        return count;
    }
    
    int solution() {
        // 将公网暴露的节点编号升序
        sort(exposed.begin(), exposed.end());
    
        // R[i] 表示攻击者从节点exposed[i]进入，所能攻击的节点数量
        vector<int> R(n, 0);
        for (int i = 0; i < exposed.size(); i++) {
            int nodeIdx = exposed[i];
    
            if (matrix[nodeIdx][nodeIdx] > 0) {
                set<int> visited;
                visited.insert(nodeIdx);
                R[i] = dfs(nodeIdx, 10, visited);
            }
        }
    
        int min = INT_MAX;
        int idx = -1;
    
        // 下线exposed[i]节点
        for (int i = 0; i < exposed.size(); i++) {
            // maxR记录下线exposed[i]节点后，攻击者从其他暴露节点进入所能产生的最大攻击数量
            int maxR = 0;
    
            // 攻击者从exposed[j]进入，则能攻击节点数量为R[j]
            for (int j = 0; j < exposed.size(); j++) {
                // 如果 i == j，则exposed[j]为下线节点，不可进入
                if (j != i) {
                    maxR = max(maxR, R[j]);
                }
            }
    
            // 下线exposed[i]节点，则攻击者最多可以攻击maxR个节点，如果maxR < min，则下线exposed[i]节点是更优策略
            if (maxR < min) {
                min = maxR;
                idx = exposed[i];
            }
        }
    
        return idx;
    }
    
    int main() {
        cin >> n;
    
        matrix = vector<vector<int>>(n, vector<int>(n));
    
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> matrix[i][j];
    
                if (i != j && matrix[i][j] > 0) {
                    nxt[i].emplace_back(j);
                }
            }
        }
    
        // 本地测试时，需要ctrl+z或者ctrl+d结束输入获取
        int idx;
        while (cin >> idx) {
            exposed.emplace_back(idx);
        }
    
        cout << solution() << endl;
    
        return 0;
    }

[- _ - HydroOJ]: https://hydro.ac/d/HWOCR/p/OCR028
[127db98142114877ad9fab7dac2e1b12.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/82c8b866002349e2b6aec9b1f654f026.png