Problem D: 信使PIPI

Problem D: 信使PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 47  Solved: 10
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI是CSU的一名送信员。每天他都要在各个教学楼之间送信。
CSU可以视为一个NxN的2D地图,其中'C'代表升华楼,'c'代表其他教学楼,'#'代表不能走的地形,'.'代表可以走的地形。
现在校长要将一个重要信件传给所有其他教学楼。校长可以从升华楼派出一名或者多名送信员向若干教学楼送信。当一名信使到达一个教学楼,这个教学楼可以继续派出一名或者多名信使再奔向其他教学楼传递信件。直到所有教学楼都被送到。
一名信使每个单位时间可以在地图上移动到上下左右相邻的一格中。为了不过度消耗,校长想知道要想通知到所有教学楼,最少需要所有信使累计消耗多少单位时间?

Input

第一行包含一个整数N。

以下N行包含一个NxN的字符矩阵,代表地图。

1 <= N <= 100 地图中的教学楼不超过100个。

Output

一个整数代表答案

Sample Input

4  
c..c
....
....
C..c

Sample Output

9