Max Visible Network Cell
Browserstack's core business involves testing websites and applications across a vast array of real devices and browsers. Imagine a new feature where we want to intelligently place "monitoring probes" (signal emitters) across a virtual network grid to maximize coverage for "data collection points" (empty cells). This problem simulates a simplified version of determining optimal placement by identifying the most "visible" data collection point, given existing signal emitters and network obstacles. Understanding line-of-sight propagation in a grid is crucial for network planning and resource optimization.
You are given a 2D grid representing a virtual network. Each cell can be:
. (empty): A potential data collection point.S (signal emitter): A source broadcasting a signal.# (obstacle): A block that prevents signal propagation.Your task is to implement a function findMaxVisibleCell that identifies an empty cell ('.') in the grid that receives signals from the maximum number of distinct signal emitters. A signal from an emitter travels in all 8 cardinal and diagonal directions (horizontal, vertical, and both diagonals) until it hits an obstacle (#) or the boundary of the grid. Any empty cell . on a direct line of sight from an emitter, without an obstacle in between, receives a signal from that emitter.
If there are multiple empty cells that receive the maximum number of signals, any one of them is a valid answer.
If no empty cells exist, or no empty cell receives any signal, return [-1, -1].
grid: string[][]
grid: A 2D array of strings, where each string is a single character (., S, or #). grid[r][c] represents the character at row r and column c.number[]
[row, col] representing the 0-indexed coordinates of an empty cell . that receives the maximum number of distinct signals.[-1, -1].S) or empty cells (.) do not block propagation; only obstacles (#) do.Examples
Example 1
Input:
grid = [["S",".","."], [".","#","."], [".",".","S"]]
Output:
[0,2]
Note:
Cell (0,2) receives signals from S at (0,0) and S at (2,2). Cell (2,0) also receives from S at (0,0) and S at (2,2). Both (0,2) and (2,0) achieve the maximum count of 2. Any valid cell is acceptable.
Example 2
Input:
grid = [[".",".","."], [".",".","."], [".",".","."]]
Output:
[-1,-1]
Note:
There are no signal emitters in the grid, so no empty cell receives any signal. The maximum count is 0, thus we return [-1,-1].
Example 3
Input:
grid = [["#","#"],["#","S"]]
Output:
[-1,-1]
Note:
There are no empty cells ('.') in the grid to receive signals. Thus, we return [-1,-1].
Example 4
Input:
grid = [["S", ".", "#", ".", "S"], [".", ".", ".", ".", "."], ["#", ".", "S", ".", "#"], [".", ".", ".", ".", "."], ["S", ".", "#", ".", "S"]]
Output:
[1,1]
Note:
Many cells receive signals. For example, cell (1,1) receives signals from S at (0,0), S at (2,2), and S at (4,0). Cell (1,3) receives signals from S at (0,4), S at (2,2), and S at (4,4). Both achieve 3 distinct signals. Other cells might also achieve this maximum. For this example, [1,1] is a valid output.
Constraints
1 <= grid.length, grid[0].length <= 500grid[r][c] will be one of '.', 'S', '#'O(N*M * max(N,M)) time complexity.Loading editor...