All Tracks Algorithms Graphs Breadth First Search Problem

Bacha lo
/
No tags
Problem
Editorial
Analytics

There is play ground which is designed in a grid \(G\). It has \(N\) rows and \(M\) columns. Each cell of grid can be of one the three types mentioned below-

  • Blocked cell marked by \(B\), Nobody can use this cell.
  • Exit cell marked by \(E\), there is exit gate in this cell.
  • Child cell marked by \(C\), there is a child playing in this cell.

Suddenly a tiger appears in playground, so every child wants to exit from playground. You to find the shortest distance for each child so that he/she exit.

Input format

First line contains two integers, \(N\) and \(M\).

Next \(N\) lines contains \(M\) characters ( \(B\) or \(E\) or \(C\) ) , type of the cell \((i, j)\)

Output format

Print \(N\) lines, Each line contains \(M\) integers separated by space represent shortest distance for cell \((i, j)\). Print \(-1\)  for blocked cell or cell that can never be reached to any exit cell or exit cell.

Constraints

\(1 \le M * N \le 10^6\)

\(G(i, j) \epsilon \{B, E, C\}\)

SAMPLE INPUT
3 3
CCE
BCC
ECC
SAMPLE OUTPUT
2 1 -1 
-1 2 1 
-1 1 2 
Time Limit: 0.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?