hi
is there any one who can give me the complete solution in java.
1 Answer
Dr. Alberquert invented the
following three devices to set
up a simple communication
network:
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