题解

题目描述

在 PCB 电路板设计中，器件之间的连线需要避免线路的阻抗值增大，而且器件之间还有别的器件和干扰源。在布线时，我们希望受到的干扰尽量小。

电路板简化为一个 M x N 的矩阵，每个位置的值表示其源干扰度。如果位置的值为 0，表示没有干扰源；如果值为 d > 0，表示该位置是一个干扰源，干扰度为 d。

当连线经过位置 (x, y) 时：

1. 如果连线经过该位置，干扰度会增加该位置的源干扰度。
2. 如果连线经过离该位置的距离小于该位置的干扰度，则干扰度会增加 (d - distance)。
3. 如果距离大于或等于干扰度，则不会增加干扰度。

现在要求你计算从电路板左上角 (0, 0) 到右下角 (M-1, N-1) 的最小干扰度，且连线只能向下或向右。

思路解析

1. 干扰度累加：

   • 对于每个干扰源位置 (i, j)，其干扰度范围是由该位置的干扰度 d 决定的。它的影响不仅局限于 (i, j) 本身，还会扩展到该位置周围的其他位置，影响范围由 d 决定。
   • 计算每个位置的干扰度时，我们需要根据其到干扰源的距离来判断是否增加干扰度。

2. 动态规划：

   • 为了计算从 (0, 0) 到 (M-1, N-1) 的最小干扰度，我们可以使用动态规划。定义 dp[i][j] 为从左上角 (0, 0) 到当前位置 (i, j) 的最小干扰度。
   • 状态转移方程：
     • 如果当前位置为 (0, 0)，那么 dp[0][0] = graph0[0][0]，即干扰度是其本身的值。
     • 如果当前位置是第一行或第一列，那么可以从上一行或上一列转移过来，dp[i][j] = dp[i-1][j] + graph0[i][j] 或 dp[i][j] = dp[i][j-1] + graph0[i][j]。
     • 对于其他位置，dp[i][j] 为从上方或左方的最小值加上当前位置的干扰度，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + graph0[i][j]。

3. 时间复杂度优化：

   • 在计算每个位置的累积干扰度时，我们采用了优化的边界计算方法，避免了不必要的重复计算。每个干扰源只影响其范围内的区域，并且 y 的范围是动态调整的。

4. 最终结果：

   • 最终，我们的目标是输出 dp[M-1][N-1]，即从左上角到右下角的最小干扰度。

代码实现

Python 代码

def main():
    N, M = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(N)]
    graph0 = [[0] * M for _ in range(N)]  # 存储累积干扰度
    
    # 计算每个位置的累积干扰度
    for i in range(N):
        for j in range(M):
            d = graph[i][j]
            if d > 0:
                # 计算影响范围的边界
                startX = max(i - d, 0)
                endX = min(i + d, N - 1)
                # 遍历x范围
                for x in range(startX, endX + 1):
                    # 计算y范围，这里动态根据x的偏移调整y范围
                    delta = abs(x - i)
                    for y in range(max(j - (d - delta), 0), min(j + (d - delta), M - 1) + 1):
                        graph0[x][y] += max(0, d - abs(x - i) - abs(y - j))

    # 动态规划计算最小干扰度
    dp = [[float('inf')] * M for _ in range(N)]
    dp[0][0] = graph0[0][0]

    for i in range(N):
        for j in range(M):
            if i == 0 and j == 0:
                continue
            if i == 0:
                dp[i][j] = dp[i][j - 1] + graph0[i][j]
            elif j == 0:
                dp[i][j] = dp[i - 1][j] + graph0[i][j]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + graph0[i][j]

    # 输出右下角的最小干扰度
    print(dp[N - 1][M - 1])

if __name__ == "__main__":
    main()

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<vector<int>> graph(N, vector<int>(M));  // 存储干扰度
    vector<vector<int>> graph0(N, vector<int>(M, 0));  // 存储累积干扰度
    
    // 输入干扰度矩阵
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> graph[i][j];
        }
    }

    // 计算每个位置的累积干扰度
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int d = graph[i][j];
            if (d > 0) {
                // 计算影响范围的边界
                int startX = max(i - d, 0);
                int endX = min(i + d, N - 1);

                // 遍历x范围
                for (int x = startX; x <= endX; x++) {
                    // 计算y范围，这里动态根据x的偏移调整y范围
                    int delta = abs(x - i);
                    for (int y = max(j - (d - delta), 0); y <= min(j + (d - delta), M - 1); y++) {
                        graph0[x][y] += max(0, d - abs(x - i) - abs(y - j));
                    }
                }
            }
        }
    }

    // 动态规划计算最小干扰度
    vector<vector<int>> dp(N, vector<int>(M, INT_MAX));
    dp[0][0] = graph0[0][0];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i == 0 && j == 0) continue;  // 起始点跳过
            if (i == 0) dp[i][j] = dp[i][j-1] + graph0[i][j];
            else if (j == 0) dp[i][j] = dp[i-1][j] + graph0[i][j];
            else dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + graph0[i][j];
        }
    }

    // 输出右下角的最小干扰度
    cout << dp[N-1][M-1] << endl;
    return 0;
}

Java 代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        int[][] graph = new int[N][M];   // 存储干扰度
        int[][] graph0 = new int[N][M];  // 存储累积干扰度
        
        // 输入干扰度矩阵
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                graph[i][j] = sc.nextInt();
            }
        }
        
        // 计算每个位置的累积干扰度
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int d = graph[i][j];
                if (d > 0) {
                    // 计算影响范围的边界
                    int startX = Math.max(i - d, 0);
                    int endX = Math.min(i + d, N - 1);

                    // 遍历x范围
                    for (int x = startX; x <= endX; x++) {
                        // 计算y范围，这里动态根据x的偏移调整y范围
                        int delta = Math.abs(x - i);
                        for (int y = Math.max(j - (d - delta), 0); y <= Math.min(j + (d - delta), M - 1); y++) {
                            graph0[x][y] += Math.max(0, d - Math.abs(x - i) - Math.abs(y - j));
                        }
                    }
                }
            }
        }

        // 动态规划计算最小干扰度
        int[][] dp = new int[N][M];
        dp[0][0] = graph0[0][0];
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) dp[i][j] = dp[i][j - 1] + graph0[i][j];
                else if (j == 0) dp[i][j] = dp[i - 1][j] + graph0[i][j];
                else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + graph0[i][j];
            }
        }

        // 输出右下角的最小干扰度
        System.out.println(dp[N - 1][M - 1]);
    }
}

题目内容

在$PCB$印刷电路板设计中，器件之间的连线需要避免线路的阻抗值增大、而且赛件之间还有别的器件和别的干扰源，在布线时我们希望受到的干扰尽量小。

现将电路板简化成一个$M×N$的矩阵，每个位置(单元格)的值表示其源干扰度。

如果单元格的值为$0$，表示此位置没有干扰源;如果单元格的值为非$0$，则表示此位置是干扰源，其值为源干扰度。 连线经过干扰源或干扰源附近会增加连线的总干扰度。

位置$A[x,y]$的干扰源的源干扰度为$d(d>0)$，则连线的干扰度计算如下:

$1$、若连线经过位置$A[x,y]$,则其总干扰度会增加d;

$2$、若连线经过离位置$A[x,y]$距离小于$d$的位置时，设其距离为$K$，则总干 扰度会增加$(d-k)$;

$3$、若连线经过离位置A[x,y]距离大于或等于d的位置时，总干扰度不会增加;

注:

位置$[x1,y1]$和位置$[x2.y2]$之间距离的定义为:$|x1 -x2|$+$|y1-y21|$。

如下$3x3$矩阵，位置$[1,1]$的源干扰度是$2$，连线的位置序列为:$[0.0)->[0.1)->[0,2]->[1,2]>[2,2]$。

其中$[0,1]$和$[1,0]$到干扰源的距离为$1$，会叠加$1$的干扰度;其他位置到$[1,1]$的距离均大于等于$2$，所以不会叠加干扰度。

因此这条连线的总干扰度为$2$

现在我们需要将左上角的器件到右下角的器件进行连线，两个器件的位置分别是左上角的$[0.0]$和右下角的$[M-1,N-1]$。由于我们希望连线尽量地短,从位置$[0,0]$到$[M-1,N-1]$的连线途中，我们规定连线只能向下或向右。

请根据输入($M×N$的矩阵)，计算出连线的最小干扰度。

输入描述

第一行是两个整数$M$和$N$($M$和$N$最大值为$1000$)，表示行数和列数;

接着是$M$行的数据，每一行包含$N$个整数，代表每个位置的源干扰度，每个源干扰度小于$50$

输出描述

左上角[0,0]到右下角[M-1,N-1]连线的最小总干扰度。

样例1

输入

3 3
0 0 0
0 2 0
0 0 0

输出

2

说明

其中一条可以使干扰度最小的路径为:$[0.0]->[0.1]->[0.2]->[1.2]->[2,2]$，其干扰度为$2$

样例2

输入

5 5
0 0 0 0 0
0 0 2 0 0
0 2 0 2 0
0 0 0 0 0 
0 0 0 0 0 

输出

1

说明

先从$[0.0]$往下走到最下面$[4.0]$，再往右走到右下角$[4,4]$，途径$[2,0]$时叠加了一个干扰度。

样例3

输入

5 5
0 0 0 0 0
0 0 2 0 0
0 2 0 2 0
0 0 2 0 0 
0 0 0 0 0 

输出

2

说明

先从$[0.0]$往下走到最下面$[4.0]$，再往右走到右下角$[4,4]$，途径$[2,0]$时叠加了一个干扰度。