网格多源最短路

【题意】给定一个 n 行 m 列的网格，每个格子要么是空地（用 '.' 表示），要么是障碍（用 '#' 表示），要么是感染源（用 'S' 表示）。每一秒，所有已被感染的格子会同时把它上下左右相邻的空地格子感染。求每个格子最早被感染的时刻；若永远不会被感染（包括障碍格和无法到达的空地），输出 -1。
【输入格式】第一行两个整数 n 和 m。接下来 n 行，每行一个长度为 m 的字符串，只包含 '.'、'#'、'S'。
【输出格式】输出 n 行，每行 m 个整数，表示每个格子最早被感染的时刻；障碍格和无法被感染的空地输出 -1。
【数据范围】1 ≤ n, m ≤ 2000，n×m ≤ 4×10^6。
【样例输入】
1 2
S.
【样例输出】
0 1