#P3248. 计算网络信号(200分)
-
1000ms
Tried: 81
Accepted: 26
Difficulty: 3
所属公司 :
华为od
计算网络信号(200分)
题面描述
在一个二维网格地图中,信号从唯一的信号源出发,经过空旷位置向四个方向传播,但遇到阻隔物无法穿透。给定地图的行数和列数、各个网格的状态(空旷位置、信号源和阻隔物),以及要计算的特定位置,要求输出该位置的网络信号值。如果没有信号覆盖该位置,则输出 0。例如,输入描述了一个 6 行 5 列的地图,计算位置 (1, 4) 的网络信号值,结果为 2。
思路
-
输入读取:首先,我们需要读取网格的尺寸 (m \times n) 和网格数据,接着获取需要计算的目标位置。
-
信号源定位:在网格中找到信号源的位置及其初始信号强度。信号源是唯一的,因此只需遍历一次网格。
-
信号传播:我们使用优先队列来管理信号传播的顺序。每次我们从队列中取出信号强度最大的节点,并检查它的上下左右相邻位置:
- 如果相邻位置有效(在边界内且不是阻隔物),我们计算从当前节点传播过去的信号强度。
- 如果新的信号强度大于该位置已有的信号强度,就更新它并将新位置加入队列。
-
输出结果:最后,输出目标位置的信号强度。如果该位置的信号强度仍为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