(200分)- 信号发射和接收（Java JS Python）

(200分)- 信号发射和接收（Java & JS & Python）

题目描述

有一个二维的天线矩阵，每根天线可以向其他天线发射信号，也能接收其他天线的信号，为了简化起见，我们约定每根天线只能向东和向南发射信号，换言之，每根天线只能接收东向或南向的信号。

每根天线有自己的高度anth，每根天线的高度存储在一个二维数组中，各个天线的位置用[r, c]表示，r代表天线的行位置（从0开始编号），c代表天线的列位置（从0开始编号）。

在某一方向（东向或南向），某根天线可以收到多根其他天线的信号（也可能收不到任何其他天线的信号），对任一天线X和天线Y，天线X能接收到天线Y的条件是：

1. 天线X在天线Y的东边或南边
2. 天线X和天线Y之间的其他天线的高度都低于天线X和天线Y，或天线X和天线Y之间无其他天线，即无遮挡。

如下图示意：

在天线矩阵的第0行上：

• 天线[0, 0]接收不到任何其他天线的信号，
• 天线[0, 1]可以接收到天线[0, 0]的信号，
• 天线[0, 2]可以接收到天线[0, 1]的信号，
• 天线[0, 3]可以接收到天线[0, 1]和天线[0, 2]的信号，
• 天线[0, 4]可以接收到天线[0, 3]的信号，
• 天线[0, 5]可以接收到天线[0, 4]的信号；

在天线的第0列上：

• 天线[0, 0]接收不到任何其他天线的信号，
• 天线[1, 0]可以接收到天线[0, 0]的信号，
• 天线[2, 0]可以接收到天线[1, 0]的信号，
• 天线[3, 0]可以接收到天线[1, 0]和天线[2, 0]的信号，
• 天线[4, 0]可以接收到天线[3, 0]的信号，
• 天线[5, 0]可以接收到天线[3, 0]和天线[4, 0]的信号；

给一个m行n列的矩阵（二维数组），矩阵存储各根天线的高度，求出每根天线可以接收到多少根其他天线的信号，结果输出到m行n列的矩阵（二维矩阵）中。

输入描述

输入为1个m行n列的矩阵（二维矩阵）anth[m][n]，矩阵存储各根天线的高度，高度值anth[r]][c]为大于0的整数。

第一行为输入矩阵的行数和列数，如：

m n

第二行为输入矩阵的元素值，按行输入，如：

anth[0][0] anth[0][1] ... anth[0][n-1] anth[1][0] anth[1][1] ... anth[1][n-1] ... anth[m-1][0] ... anth[m-1][n-1]

输出描述

输出一个m行n列的矩阵（二维数组）ret[m][n]，矩阵存储每根天线能收到多少根其他天线的信号，根数为ret[r][c]。

第一行为输出矩阵的行数和列数，如:

m n

第二行为输出矩阵的元素值，按行输出，如：

ret[0][0] ret[0][1] ... ret[0][n-1] ret[1][0] ret[1][1] ... ret[1][n-1] ... ret[m-1][0] ... ret[m-1][n-1]

备注

• 1 ≤ m ≤ 500
• 1 ≤ n ≤ 500
• 0 ＜ anth[r][c] ＜ 10^5

用例

题目解析

首先，本题我们需要从输入的一维数组中解析出二维天线矩阵，JS的实现略微麻烦，具体逻辑请看源码。

下面我们以用例1为例子，来解析本题，如下图是用例1的二维天线矩阵anth

我们从anth[0][0]开始发射，本题说了，天线信号发射只能向东或者向南发射，即如下图所示

​​

由于用例1只有一层，因此只需要考虑向东发射信号。

而东边的天线是否能收到信号，也有前提条件，即“发射天线”与“接收天线”之间的天线的高度都低于“发射天线”与“接收天线”，或者“发射天线”与“接收天线”之间没有其他天线

因此，上面用例1中anth[0][0]可以发射到anth[0][1]，因为它们之间没有其他天线

但是anth[0][0]不能发射到anth[0][2]，因为它们之间的天线大于等于了它们

其实这一步，不需要走到anth[0][2]，因为anth[0][1] >= anth[0][0]，因此anth[0][0]必然会被anth[0][1]遮挡，导致无法继续向东发射。

因此，对于anth[0][0]作为发射点的所有情况已经讨论完了，它只有一个接收点，那就是anth[0][1]。

接下来继续讨论anth[0][1]作为发射点

首先，相邻的anth[0][2]肯定能接收到信号。

并且由于anth[0][2]小于anth[0][1]，因此无法完全将anth[0][1]发射的信号遮挡，

因此anth[0][3]可以接收到anth[0][1]的信号？

注意：这里我打了一个问号，因为题目要求，如果“发射天线”和“接收天线”之间有其他天线，那么其他天线的高度必须低于“发射天线”和“接收天线”。

上面打问号的原因是：我们只判断了中间天线 anth[0][2] < anth[0][1] 发射天线，并没有判断中间天线 anth[0][2] 也小于 anth[0][3] 接收天线。

• 而，这里中间天线 anth[0][2] 确实是小于 anth[0][3] 接收天线的，因此anth[0][3]可以接收到anth[0][1]的信号。

如果，我们采用双重for，外层遍历发射天线，内层遍历接收天线，则还需一个for遍历求得发射天线和接收天线之间的：所有中间天线中最高的高度h，如果这个高度h 大于等于发射天线，或者接收天线，则发射天线和接收天线之间无法进行通信。

这其实已经是三重for了，再加上每个天线都会接收来自东向和南向这两个方向的信号，因此需要进行两次三重for。

这里的优化，我们可以利用单调递减栈。

首先定义一个单调递减栈stack，然后开始遍历天线anth[i][j]（比如先处理东向，即按行从左到右遍历）：

1、如果stack为空，则直接将天线anth[i][j]加入stack

2、如果stack不为空，则获取栈顶天线top

2.1、如果anth[i][j] > top，则将stack栈顶的top弹出，然后anth[i][j]对应的ret[i][j]++，表示anth[i][j]天线新增接收一个信号，而由于stack栈是递减栈，因此anth[i][j]还可以继续接收新栈顶天线的信号

2.2、如果anth[i][j] == top，则将stack栈顶的top弹出，然后anth[i][j]新增接收一个信号，ret[i][j]++。（注意，由于stack是严格递减栈，因此如果栈顶元素和anth[i][j]等高，则必然只有一个，且stack弹栈后的新栈顶必然大于anth[i][j]，此时其实可以直接结束）

2.3、如果anth[i][j] < top，则表示anth[i][j]已经无法接收到top之前的信号了，因为已经被top完全阻挡了。因此anth[i][j]只能栈顶天线的信号，ret[i][j]++，而无法继续接收前面天线的信号。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length === 2) { const [m, n] = lines[0].split(" ").map(Number); const arr = lines[1].split(" ").map(Number); console.log(getResult(arr, m, n)); lines.length = 0; } }); function getResult(arr, m, n) { const anth = new Array(m).fill(0).map(() => new Array(n)); for (let i = 0; i < m * n; i++) { const r = Math.floor(i / n); const c = i % n; anth[r][c] = arr[i]; } const ret = new Array(m).fill(0).map(() => new Array(n).fill(0)); // 先处理水平方向，即先进行每行的东向发射处理 for (let i = 0; i < m; i++) { const stack = []; for (let j = 0; j < n; j++) { // 如果栈顶天线比anth[i][j]，则anth[i][j]必然能接收到栈顶天线的信号，并且还能继续接收栈顶前面一个天线的信号（递减栈，栈顶前面天线高度必然大于栈顶天线高度） while (stack.length && anth[i][j] > stack.at(-1)) { ret[i][j]++; stack.pop(); } // 走到此步，如果stack还有值，那么由于是递减栈，因此此时栈顶天线高度必然 >= anth[i][j] if (stack.length) { // 如果栈顶天线高度 == anth[i][j]，那么此时anth[i][j]可以接收栈顶天线的信号，比如5 3 2 3，最后一个3可以接收到前面等高3的信号，但是无法继续接收前面5的信号，因此这里anth[i][j]结束处理 if (anth[i][j] == stack.at(-1)) { ret[i][j]++; stack.pop(); // 维护严格递减栈 } // 此情况必然是：anth[i][j] < stack.at(-1)，那么此时anth[i][j]可以接收栈顶天线的信号，比如6 5 2 3，最后一个3可以接收到前面5的信号，但是无法继续接收更前面6的信号，因此这里anth[i][j]结束处理 else { ret[i][j]++; } } stack.push(anth[i][j]); } } // 再处理垂直方向，即每列的南向发射处理，和上面同理 for (let j = 0; j < n; j++) { const stack = []; for (let i = 0; i < m; i++) { // 如果栈顶天线比anth[i][j]，则anth[i][j]必然能接收到栈顶天线的信号，并且还能继续接收栈顶前面一个天线的信号（递减栈，栈顶前面天线高度必然大于栈顶天线高度） while (stack.length && anth[i][j] > stack.at(-1)) { ret[i][j]++; stack.pop(); } // 走到此步，如果stack还有值，那么由于是递减栈，因此此时栈顶天线高度必然 >= anth[i][j] if (stack.length) { // 如果栈顶天线高度 == anth[i][j]，那么此时anth[i][j]可以接收栈顶天线的信号，比如5 3 2 3，最后一个3可以接收到前面等高3的信号，但是无法继续接收前面5的信号，因此这里anth[i][j]结束处理 if (anth[i][j] == stack.at(-1)) { ret[i][j]++; stack.pop(); // 维护严格递减栈 } // 此情况必然是：anth[i][j] < stack.at(-1)，那么此时anth[i][j]可以接收栈顶天线的信号，比如6 5 2 3，最后一个3可以接收到前面5的信号，但是无法继续接收更前面6的信号，因此这里anth[i][j]结束处理 else { ret[i][j]++; } } stack.push(anth[i][j]); } } return `${m} ${n}\n${ret.toString().split(",").join(" ")}`; }

提取公共代码，优化代码结构

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length === 2) { const [m, n] = lines[0].split(" ").map(Number); const arr = lines[1].split(" ").map(Number); console.log(getResult(arr, m, n)); lines.length = 0; } }); function getResult(arr, m, n) { const anth = new Array(m).fill(0).map(() => new Array(n)); for (let i = 0; i < m * n; i++) { const r = Math.floor(i / n); const c = i % n; anth[r][c] = arr[i]; } const ret = new Array(m).fill(0).map(() => new Array(n).fill(0)); // 先处理水平方向，即先进行每行的东向发射处理 for (let i = 0; i < m; i++) { const stack = []; for (let j = 0; j < n; j++) { common(stack, anth, ret, i, j); } } // 再处理垂直方向，即每列的南向发射处理，和上面同理 for (let j = 0; j < n; j++) { const stack = []; for (let i = 0; i < m; i++) { common(stack, anth, ret, i, j); } } return `${m} ${n}\n${ret.toString().split(",").join(" ")}`; } function common(stack, anth, ret, i, j) { // 如果栈顶天线比anth[i][j]，则anth[i][j]必然能接收到栈顶天线的信号，并且还能继续接收栈顶前面一个天线的信号（递减栈，栈顶前面天线高度必然大于栈顶天线高度） while (stack.length && anth[i][j] > stack.at(-1)) { ret[i][j]++; stack.pop(); } // 走到此步，如果stack还有值，那么由于是递减栈，因此此时栈顶天线高度必然 >= anth[i][j] if (stack.length) { // 如果栈顶天线高度 == anth[i][j]，那么此时anth[i][j]可以接收栈顶天线的信号，比如5 3 2 3，最后一个3可以接收到前面等高3的信号，但是无法继续接收前面5的信号，因此这里anth[i][j]结束处理 if (anth[i][j] == stack.at(-1)) { ret[i][j]++; stack.pop(); // 维护严格递减栈 } // 此情况必然是：anth[i][j] < stack.at(-1)，那么此时anth[i][j]可以接收栈顶天线的信号，比如6 5 2 3，最后一个3可以接收到前面5的信号，但是无法继续接收更前面6的信号，因此这里anth[i][j]结束处理 else { ret[i][j]++; } } stack.push(anth[i][j]); }

Java算法源码

import java.util.LinkedList; import java.util.Scanner; import java.util.StringJoiner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[][] anth = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { anth[i][j] = sc.nextInt(); } } System.out.println(getResult(anth, m, n)); } public static String getResult(int[][] anth, int m, int n) { int[][] ret = new int[m][n]; // 先处理南向发射信号 for (int j = 0; j < n; j++) { LinkedList<Integer> stack = new LinkedList<>(); for (int i = 0; i < m; i++) { // 如果栈顶天线比anth[i][j]，则anth[i][j]必然能接收到栈顶天线的信号，并且还能继续接收栈顶前面一个天线的信号（递减栈，栈顶前面天线高度必然大于栈顶天线高度） while (stack.size() > 0 && anth[i][j] > stack.getLast()) { ret[i][j] += 1; stack.removeLast(); } // 走到此步，如果stack还有值，那么由于是递减栈，因此此时栈顶天线高度必然 if (stack.size() > 0) { // 如果栈顶天线高度 == anth[i][j]，那么此时anth[i][j]可以接收栈顶天线的信号， // 比如5 3 2 3，最后一个3可以接收到前面等高3的信号，但是无法继续接收前面5的信号，因此这里anth[i][j]结束处理 if (anth[i][j] == stack.getLast()) { ret[i][j] += 1; stack.removeLast(); // 维护严格递减栈 } // 此情况必然是：anth[i][j] < stack.at(-1)，那么此时anth[i][j]可以接收栈顶天线的信号， // 比如6 5 2 3，最后一个3可以接收到前面5的信号，但是无法继续接收更前面6的信号，因此这里anth[i][j]结束处理 else { ret[i][j] += 1; } } stack.add(anth[i][j]); } } StringJoiner sj = new StringJoiner(" "); // 再处理东向发射信号,和上面同理 for (int i = 0; i < m; i++) { LinkedList<Integer> stack = new LinkedList<>(); for (int j = 0; j < n; j++) { // 如果栈顶天线比anth[i][j]，则anth[i][j]必然能接收到栈顶天线的信号，并且还能继续接收栈顶前面一个天线的信号（递减栈，栈顶前面天线高度必然大于栈顶天线高度） while (stack.size() > 0 && anth[i][j] > stack.getLast()) { ret[i][j] += 1; stack.removeLast(); } // 走到此步，如果stack还有值，那么由于是递减栈，因此此时栈顶天线高度必然 if (stack.size() > 0) { // 如果栈顶天线高度 == anth[i][j]，那么此时anth[i][j]可以接收栈顶天线的信号， // 比如5 3 2 3，最后一个3可以接收到前面等高3的信号，但是无法继续接收前面5的信号，因此这里anth[i][j]结束处理 if (anth[i][j] == stack.getLast()) { ret[i][j] += 1; stack.removeLast(); // 维护严格递减栈 } // 此情况必然是：anth[i][j] < stack.at(-1)，那么此时anth[i][j]可以接收栈顶天线的信号， // 比如6 5 2 3，最后一个3可以接收到前面5的信号，但是无法继续接收更前面6的信号，因此这里anth[i][j]结束处理 else { ret[i][j] += 1; } } stack.add(anth[i][j]); sj.add(ret[i][j] + ""); } } return m + " " + n + "\n" + sj.toString(); } }

提取公共代码，优化代码结构

import java.util.LinkedList; import java.util.Scanner; import java.util.StringJoiner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[][] anth = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { anth[i][j] = sc.nextInt(); } } System.out.println(getResult(anth, m, n)); } public static String getResult(int[][] anth, int m, int n) { int[][] ret = new int[m][n]; // 先处理南向发射信号 for (int j = 0; j < n; j++) { LinkedList<Integer> stack = new LinkedList<>(); for (int i = 0; i < m; i++) { common(stack, anth, ret, i, j); } } StringJoiner sj = new StringJoiner(" "); // 再处理东向发射信号,和上面同理 for (int i = 0; i < m; i++) { LinkedList<Integer> stack = new LinkedList<>(); for (int j = 0; j < n; j++) { common(stack, anth, ret, i, j); sj.add(ret[i][j] + ""); } } return m + " " + n + "\n" + sj.toString(); } public static void common(LinkedList<Integer> stack, int[][] anth, int[][] ret, int i, int j) { // 如果栈顶天线比anth[i][j]，则anth[i][j]必然能接收到栈顶天线的信号，并且还能继续接收栈顶前面一个天线的信号（递减栈，栈顶前面天线高度必然大于栈顶天线高度） while (stack.size() > 0 && anth[i][j] > stack.getLast()) { ret[i][j] += 1; stack.removeLast(); } // 走到此步，如果stack还有值，那么由于是递减栈，因此此时栈顶天线高度必然 if (stack.size() > 0) { // 如果栈顶天线高度 == anth[i][j]，那么此时anth[i][j]可以接收栈顶天线的信号， // 比如5 3 2 3，最后一个3可以接收到前面等高3的信号，但是无法继续接收前面5的信号，因此这里anth[i][j]结束处理 if (anth[i][j] == stack.getLast()) { ret[i][j] += 1; stack.removeLast(); // 维护严格递减栈 } // 此情况必然是：anth[i][j] < stack.at(-1)，那么此时anth[i][j]可以接收栈顶天线的信号， // 比如6 5 2 3，最后一个3可以接收到前面5的信号，但是无法继续接收更前面6的信号，因此这里anth[i][j]结束处理 else { ret[i][j] += 1; } } stack.add(anth[i][j]); } }

Python算法源码

# 输入获取 m, n = map(int, input().split()) arr = list(map(int, input().split())) # 算法源码 def getResult(m, n, arr): anth = [[0 for j in range(n)] for i in range(m)] for i in range(m * n): r = int(i / n) c = i % n anth[r][c] = arr[i] ret = [[0 for j in range(n)] for i in range(m)] # 先处理东向发射信号 for i in range(m): stack = [] for j in range(n): # 如果栈顶天线比anth[i][j]，则anth[i][j]必然能接收到栈顶天线的信号，并且还能继续接收栈顶前面一个天线的信号（递减栈，栈顶前面天线高度必然大于栈顶天线高度） while len(stack) > 0 and anth[i][j] > stack[-1]: ret[i][j] += 1 stack.pop() # 走到此步，如果stack还有值，那么由于是递减栈，因此此时栈顶天线高度必然 if len(stack) > 0: # 如果栈顶天线高度 == anth[i][j]，那么此时anth[i][j]可以接收栈顶天线的信号，比如5 3 2 3，最后一个3可以接收到前面等高3的信号，但是无法继续接收前面5的信号，因此这里anth[i][j]结束处理 if anth[i][j] == stack[-1]: ret[i][j] += 1 stack.pop() # 维护严格递减栈 # 此情况必然是：anth[i][j] < stack.at(-1)，那么此时anth[i][j]可以接收栈顶天线的信号，比如6 5 2 3，最后一个3可以接收到前面5的信号，但是无法继续接收更前面6的信号，因此这里anth[i][j]结束处理 else: ret[i][j] += 1 stack.append(anth[i][j]) # 再处理南向发射信号 for j in range(n): stack = [] for i in range(m): # 如果栈顶天线比anth[i][j]，则anth[i][j]必然能接收到栈顶天线的信号，并且还能继续接收栈顶前面一个天线的信号（递减栈，栈顶前面天线高度必然大于栈顶天线高度） while len(stack) > 0 and anth[i][j] > stack[-1]: ret[i][j] += 1 stack.pop() # 走到此步，如果stack还有值，那么由于是递减栈，因此此时栈顶天线高度必然 if len(stack) > 0: # 如果栈顶天线高度 == anth[i][j]，那么此时anth[i][j]可以接收栈顶天线的信号，比如5 3 2 3，最后一个3可以接收到前面等高3的信号，但是无法继续接收前面5的信号，因此这里anth[i][j]结束处理 if anth[i][j] == stack[-1]: ret[i][j] += 1 stack.pop() # 维护严格递减栈 # 此情况必然是：anth[i][j] < stack.at(-1)，那么此时anth[i][j]可以接收栈顶天线的信号，比如6 5 2 3，最后一个3可以接收到前面5的信号，但是无法继续接收更前面6的信号，因此这里anth[i][j]结束处理 else: ret[i][j] += 1 stack.append(anth[i][j]) res = " ".join([" ".join(map(str, i)) for i in ret]) print(f'{m} {n}\n{res}') # 算法调用 getResult(m, n, arr)

提取公共代码，优化代码结构

# 输入获取 m, n = map(int, input().split()) arr = list(map(int, input().split())) def common(stack, anth, ret, i, j): # 如果栈顶天线比anth[i][j]，则anth[i][j]必然能接收到栈顶天线的信号，并且还能继续接收栈顶前面一个天线的信号（递减栈，栈顶前面天线高度必然大于栈顶天线高度） while len(stack) > 0 and anth[i][j] > stack[-1]: ret[i][j] += 1 stack.pop() # 走到此步，如果stack还有值，那么由于是递减栈，因此此时栈顶天线高度必然 if len(stack) > 0: # 如果栈顶天线高度 == anth[i][j]，那么此时anth[i][j]可以接收栈顶天线的信号，比如5 3 2 3，最后一个3可以接收到前面等高3的信号，但是无法继续接收前面5的信号，因此这里anth[i][j]结束处理 if anth[i][j] == stack[-1]: ret[i][j] += 1 stack.pop() # 维护严格递减栈 # 此情况必然是：anth[i][j] < stack.at(-1)，那么此时anth[i][j]可以接收栈顶天线的信号，比如6 5 2 3，最后一个3可以接收到前面5的信号，但是无法继续接收更前面6的信号，因此这里anth[i][j]结束处理 else: ret[i][j] += 1 stack.append(anth[i][j]) # 算法源码 def getResult(m, n, arr): anth = [[0 for j in range(n)] for i in range(m)] for i in range(m * n): r = int(i / n) c = i % n anth[r][c] = arr[i] ret = [[0 for j in range(n)] for i in range(m)] # 先处理东向发射信号 for i in range(m): stack = [] for j in range(n): common(stack, anth, ret, i, j) # 再处理南向发射信号 for j in range(n): stack = [] for i in range(m): common(stack, anth, ret, i, j) res = " ".join([" ".join(map(str, i)) for i in ret]) print(f'{m} {n}\n{res}') # 算法调用 getResult(m, n, arr)