刷题笔记合集🔗

计算网络信号-信号强度

问题描述

在一个网格地图中，网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透。现需要计算某个位置的网络信号值。注意：网络信号可以绕过阻隔物。

给定一个 的二维数组 ，其中：

• 表示 是空旷位置；
• （ 为正整数）表示 是信号源，信号强度为 ；
• 表示 是阻隔物。

信号源只有 1 个，阻隔物可能有 0 个或多个。网络信号向上下左右相邻的网格传播时，强度衰减 1。要求输出指定位置的网络信号值。

输入格式

第一行包含两个整数 和 ，表示网格地图的行数和列数。

第二行包含 个用空格分隔的整数，表示网格地图的状态。每 个数代表一行。

第三行包含两个整数 和 ，表示需要计算 的网络信号值。

输出格式

输出一个整数，表示指定位置的网络信号值。如果网络信号未覆盖到该位置，输出 0。

样例输入1

6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
1 4

样例输出1

2

样例输入2

6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1

样例输出2

0

样例解释

数据范围

• 
• ，或
• ，

题解

多源BFS

这道题目本质上是一个图的广度优先搜索（BFS）问题。关键在于理解信号的传播方式和如何处理阻隔物。

解题思路如下：

1. 首先，找到信号源的位置。
2. 从信号源开始，使用 BFS 向四周传播信号。
3. 在 BFS 过程中，记录每个位置的信号强度。
4. 遇到阻隔物时，停止向该方向传播。
5. 最后，返回指定位置的信号强度。

使用 BFS 的原因是它能够保证在遍历到某个位置时，该位置的信号强度是最大的。这是因为 BFS 是按照距离信号源的远近顺序进行遍历的。

关键点：

• 使用队列来实现 BFS。
• 使用一个二维数组来记录每个位置的信号强度。
• 在遍历过程中，注意检查边界条件和阻隔物。

参考代码

• Python

from collections import deque

def calculate_signal(m, n, grid, target_i, target_j):
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    signal = [[0] * n for _ in range(m)]
    
    # 找到信号源
    source = None
    for i in range(m):
        for j in range(n):
            if grid[i][j] > 0:
                source = (i, j)
                break
        if source:
            break
    
    if not source:
        return 0  # 没有信号源
    
    queue = deque([source])
    signal[source[0]][source[1]] = grid[source[0]][source[1]]
    
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != -1:
                new_signal = signal[x][y] - 1
                if new_signal > 0 and new_signal > signal[nx][ny]:
                    signal[nx][ny] = new_signal
                    queue.append((nx, ny))
    
    return signal[target_i][target_j]

# 读取输入
m, n = map(int, input().split())
grid = list(map(int, input().split()))
grid = [grid[i:i+n] for i in range(0, len(grid), n)]
target_i, target_j = map(int, input().split())

# 计算并输出结果
result = calculate_signal(m, n, grid, target_i, target_j)
print(result)

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000
#define MAX(a, b) ((a) > (b) ? (a) : (b))

// 定义队列结构
typedef struct {
    int x, y;
} Point;

typedef struct {
    Point* data;
    int front, rear, size;
} Queue;

// 初始化队列
Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->data = (Point*)malloc(capacity * sizeof(Point));
    queue->front = queue->rear = -1;
    queue->size = 0;
    return queue;
}

// 入队
void enqueue(Queue* queue, int x, int y) {
    queue->rear = (queue->rear + 1) % (MAX_SIZE * MAX_SIZE);
    queue->data[queue->rear].x = x;
    queue->data[queue->rear].y = y;
    queue->size++;
}

// 出队
Point dequeue(Queue* queue) {
    queue->front = (queue->front + 1) % (MAX_SIZE * MAX_SIZE);
    queue->size--;
    return queue->data[queue->front];
}

// 判断队列是否为空
int isEmpty(Queue* queue) {
    return queue->size == 0;
}

int calculate_signal(int m, int n, int grid[MAX_SIZE][MAX_SIZE], int target_i, int target_j) {
    int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int signal[MAX_SIZE][MAX_SIZE] = {0};
    int source_x = -1, source_y = -1;
    
    // 找到信号源
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0) {
                source_x = i;
                source_y = j;
                break;
            }
        }
        if (source_x != -1) break;
    }
    
    if (source_x == -1) return 0;  // 没有信号源
    
    signal[source_x][source_y] = grid[source_x][source_y];
    
    Queue* queue = createQueue(MAX_SIZE * MAX_SIZE);
    enqueue(queue, source_x, source_y);
    
    while (!isEmpty(queue)) {
        Point current = dequeue(queue);
        int x = current.x, y = current.y;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + directions[i][0];
            int ny = y + directions[i][1];
            
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] != -1) {
                int new_signal = signal[x][y] - 1;
                if (new_signal > signal[nx][ny]) {
                    signal[nx][ny] = new_signal;
                    enqueue(queue, nx, ny);