题面描述

在一个二维网格地图中，信号从唯一的信号源出发，经过空旷位置向四个方向传播，但遇到阻隔物无法穿透。给定地图的行数和列数、各个网格的状态（空旷位置、信号源和阻隔物），以及要计算的特定位置，要求输出该位置的网络信号值。如果没有信号覆盖该位置，则输出 0。例如，输入描述了一个 6 行 5 列的地图，计算位置 (1, 4) 的网络信号值，结果为 2。

思路

1. 输入读取：首先，我们需要读取网格的尺寸 (m \times n) 和网格数据，接着获取需要计算的目标位置。

2. 信号源定位：在网格中找到信号源的位置及其初始信号强度。信号源是唯一的，因此只需遍历一次网格。

3. 信号传播：我们使用优先队列来管理信号传播的顺序。每次我们从队列中取出信号强度最大的节点，并检查它的上下左右相邻位置：

   • 如果相邻位置有效（在边界内且不是阻隔物），我们计算从当前节点传播过去的信号强度。
   • 如果新的信号强度大于该位置已有的信号强度，就更新它并将新位置加入队列。

4. 输出结果：最后，输出目标位置的信号强度。如果该位置的信号强度仍为0，则表示该位置没有信号覆盖。

关键部分解析

• 优先队列的使用：利用优先队列能够保证我们总是优先处理信号强度最大的节点，从而有效地模拟信号的传播过程。

• 信号更新逻辑：在处理每个节点时，我们会检查其四个方向的邻居，并决定是否更新信号强度。只有当新的信号强度大于当前记录的强度时，才进行更新。

cpp

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

// 定义方向，上、下、左、右
const vector<pair<int, int>> directions = { { -1,0 }, { 1,0 }, { 0,-1 }, { 0,1 } };

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int m, n;
    cin >> m >> n;
    
    // 读取网格
    vector<vector<int>> grid(m, vector<int>(n, 0));
    for(int i=0;i<m;i++) {
        for(int j=0;j<n;j++) {
            cin >> grid[i][j];
        }
    }
    
    // 读取目标位置
    int target_i, target_j;
    cin >> target_i >> target_j;
    
    // 找到信号源的位置和初始信号
    int source_i = -1, source_j = -1, source_strength = 0;
    for(int i=0;i<m;i++) {
        for(int j=0;j<n;j++) {
            if(grid[i][j] > 0){
                source_i = i;
                source_j = j;
                source_strength = grid[i][j];
                break;
            }
        }
        if(source_i != -1) break;
    }
    
    // 如果没有找到信号源，输出0
    if(source_i == -1){
        cout << "0";
        return 0;
    }
    
    // 初始化信号强度网格
    vector<vector<int>> signal(m, vector<int>(n, 0));
    // 优先队列，按信号强度从大到小
    // 元素为 {信号强度, {i, j}}
    priority_queue<pair<int, pair<int, int>>> pq;
    
    // 设置源点信号
    signal[source_i][source_j] = source_strength;
    pq.push({source_strength, {source_i, source_j}});
    
    while(!pq.empty()){
        auto current = pq.top();
        pq.pop();
        int current_signal = current.first;
        int x = current.second.first;
        int y = current.second.second;
        
        // 如果当前信号已经小于网格中的记录，跳过
        if(current_signal < signal[x][y]) continue;
        
        for(auto &dir : directions){
            int new_x = x + dir.first;
            int new_y = y + dir.second;
            
            // 检查边界
            if(new_x < 0 || new_x >= m || new_y < 0 || new_y >= n)
                continue;
            // 检查是否是阻隔物
            if(grid[new_x][new_y] == -1)
                continue;
            
            // 计算新的信号强度
            int new_signal = current_signal - 1;
            if(new_signal <= 0)
                continue;
            // 如果新的信号强度大于已有的，更新并入队
            if(new_signal > signal[new_x][new_y]){
                signal[new_x][new_y] = new_signal;
                pq.push({new_signal, {new_x, new_y}});
            }
        }
    }
    
    // 输出目标位置的信号强度
    cout << signal[target_i][target_j];
    
    return 0;
}

python

import heapq

# 定义方向，上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def main():
    m, n = map(int, input().split())
    
    # 读取网格
    grid = []
    data = list(map(int, input().split()))
    for i in range(m):
        grid.append(data[i * n:(i + 1) * n])
    
    # 读取目标位置
    target_i, target_j = map(int, input().split())
    
    # 找到信号源的位置和初始信号
    source_i, source_j, source_strength = -1, -1, 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] > 0:
                source_i, source_j, source_strength = i, j, grid[i][j]
                break
        if source_i != -1:
            break
    
    # 如果没有找到信号源，输出0
    if source_i == -1:
        print(0)
        return
    
    # 初始化信号强度网格
    signal = [[0] * n for _ in range(m)]
    
    # 优先队列，按信号强度从大到小
    pq = []
    
    # 设置源点信号
    signal[source_i][source_j] = source_strength
    heapq.heappush(pq, (-source_strength, (source_i, source_j)))  # 使用负数来实现大顶堆
    
    while pq:
        current_signal, (x, y) = heapq.heappop(pq)
        current_signal = -current_signal  # 还原信号强度为正
        
        # 如果当前信号已经小于网格中的记录，跳过
        if current_signal < signal[x][y]:
            continue
        
        for dx, dy in directions:
            new_x, new_y = x + dx, y + dy
            
            # 检查边界
            if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:
                continue
            # 检查是否是阻隔物
            if grid[new_x][new_y] == -1:
                continue
            
            # 计算新的信号强度
            new_signal = current_signal - 1
            if new_signal <= 0:
                continue
            
            # 如果新的信号强度大于已有的，更新并入队
            if new_signal > signal[new_x][new_y]:
                signal[new_x][new_y] = new_signal
                heapq.heappush(pq, (-new_signal, (new_x, new_y)))  # 使用负数来实现大顶堆
    
    # 输出目标位置的信号强度
    print(signal[target_i][target_j])

if __name__ == "__main__":
    main()

java

import java.util.LinkedList;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int m = sc.nextInt();
        int n = sc.nextInt();
 
        LinkedList<Integer> queue = new LinkedList<>();
 
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
 
                if (matrix[i][j] > 0) {
                    queue.add(i * n + j);
                }
            }
        }
 
        int tx = sc.nextInt();
        int ty = sc.nextInt();
 
        // 上下左右偏移量
        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
        // bfs按层扩散
        while (!queue.isEmpty()) {
            int size = queue.size();
 
            for (int i = 0; i < size; i++) {
                int pos = queue.removeFirst();
 
                int x = pos / n;
                int y = pos % n;
 
                for (int[] offset : offsets) {
                    int newX = x + offset[0];
                    int newY = y + offset[1];
 
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 0) {
                        matrix[newX][newY] = matrix[x][y] - 1;
 
                        if (matrix[newX][newY] > 0) {
                            queue.addLast(newX * n + newY);
                        }
                    }
                }
            }
        }
 
        System.out.println(matrix[tx][ty]);
    }
}

题目内容

网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。注意:网络信号可以绕过阻隔物。

• $array[m] [n]$ 的二维数组代表网格地图，
• $array[i] [j] = 0$代表i行j列是空旷位置;
• $array[i] [j] = x$( $x$ 为正整数)代表 $i$ 行 $j$ 列是信号源，信号强度是$x$;
• $array[i] [j] = -1$代表 $i$ 行 $j$ 列是阻隔物。
• 信号源只有 $1$ 个，阻隔物可能有 $0$ 个或多个
• 网络信号衰减是上下左右相邻的网格衰减 $1$

现要求输出对应位置的网络信号值。

输入描述

输入为三行，

• 第一行为 $m$ 、$n$ ，代表输入是一个 $m × n$ 的数组。
• 第二行是一串 $m × n$ 个用空格分隔的整数。每连续 $n$ 个数代表一行，再往后 $n$ 个代表下一行，以此类推。对应的值代表对应的网格是空旷位置，还是信号源，还是阻隔物。
• 第三行是 $i$ 、 $j$，代表需要计算 $array[i] [j]$ 的网络信号值。

注意：此处 $i$ 和 $j$ 均从 $0$ 开始，即第一行 $i$ 为 $0$。

例如

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$行第$4$列的网络信号值，如下图，值为$2$。

输出描述

输出对应位置的网络信号值，如果网络信号未覆盖到，也输出 $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

输出

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

输出

0