Interview Question
- 0of 0 votes
AnswerDr. Alberquert invented the following three devices to set up a simple communication network:
- dev May 22, 2012 in United States
Synthesizer (S), which produces signals continuously and transmits (propagates / passes on) them to neighbouring cells but cannot receive signals.
Receiver (R), which can receive signals from neighbouring signal sources but cannot produce or propagate signal.
Transmitter (T), which is capable of both receiving signal from and transmitting signals to neighbouring cells. Transmitters also are NOT capable of producing signals.
These devices are laid in a matrix formation. Signals are propagated at the rate of one cell per time unit. The absorption rate of a receiver is unlimited and so also the transmission and absorption rate of a transmitter unlimited. For simplicity we shall ignore the exact nature of signals being produced and consider them uniform across sources. Devices on the extreme right side can also communicate with the extreme left hand side device present in the same row (see fig 2). Similarly a device on the extreme top can also communicate with a device at the extreme bottom if they are present in the same column.
Please Note:
Neighbourhood is a four cell neighbourhood, i.e, the neighbourhood of a cell is defined by cells to its NORTH, SOUTH, EAST and WEST (see fig 1).
All Synthesizers will start to produce signals as soon as the simulation begins.
There could be multiple Synthesizers in a matrix arrangement.
Your task is to write a program that would take a matrix containing devices and output the time at which each receiver/transmitter receives its first signal.
Input specification:
The first line has two integers M and N indicating the number of rows and columns of the matrix. 0 < M, N <= 20
M lines follow the first line. Each of these M lines contains N characters and a terminating new line. Each character is one of S, T or R.
Output specification:
The output should be a matrix of M rows with each row containing N integers separated by spaces indicating the minimum time required for the signal to reach the corresponding device. The output for cells containing Synthesizers is 0. For devices that never receive any signal, print -1.
Sample Input and Output:
Input:
3 4
SRTR
TTTT
TTTS
Output:
0 1 3 1
1 2 2 1
1 2 1 0
Input:
2 3
RTT
TTR
Output:
-1 -1 -1
-1 -1 -1| Report Duplicate | Flag | PURGE
Java
One simple (may not be most optimal) solution is to find shortest paths from each S to T's and R's.
- Pranav May 22, 2012