using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 3");
WillReturn.Add("...");
WillReturn.Add(".#.");
WillReturn.Add("...");
//8
}
else if (InputPattern == "Input2") {
WillReturn.Add("1 6");
WillReturn.Add("......");
//-1
}
else if (InputPattern == "Input3") {
WillReturn.Add("4 4");
WillReturn.Add("....");
WillReturn.Add("#...");
WillReturn.Add("....");
WillReturn.Add("...#");
//12
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static char[,] mBanArr;
static int UB_X;
static int UB_Y;
static void Main()
{
List<string> InputList = GetInputList();
mBanArr = CreateBanArr(InputList.Skip(1));
UB_X = mBanArr.GetUpperBound(0);
UB_Y = mBanArr.GetUpperBound(1);
var ResultList = new List<JyoutaiDef>();
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (mBanArr[LoopX, LoopY] == '#') continue;
ResultList.AddRange(ExecDFS(LoopX, LoopY));
}
}
if (ResultList.Exists(pX => pX.Level >= 3) == false) {
Console.WriteLine(-1);
}
else {
Console.WriteLine(ResultList.Max(pX => pX.Level));
}
}
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal HashSet<int> VisitedSet;
internal int Level;
}
// 始点を引数として、DFSを行う
static List<JyoutaiDef> ExecDFS(int pStaX, int pStaY)
{
var WillReturn = new List<JyoutaiDef>();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = pStaX;
WillPush.CurrY = pStaY;
WillPush.VisitedSet = new HashSet<int>();
WillPush.Level = 0;
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
// クリア判定
if (Popped.Level > 0 && Popped.CurrX == pStaX && Popped.CurrY == pStaY) {
WillReturn.Add(Popped);
continue;
}
Action<int, int> PushAct = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB_X < pNewX) return;
if (pNewY < 0 || UB_Y < pNewY) return;
if (mBanArr[pNewX, pNewY] == '#') return;
int Hash = GetHash(pNewX, pNewY);
if (Popped.VisitedSet.Contains(Hash)) return;
WillPush.CurrX = pNewX;
WillPush.CurrY = pNewY;
WillPush.VisitedSet = new HashSet<int>(Popped.VisitedSet);
WillPush.VisitedSet.Add(Hash);
WillPush.Level = Popped.Level + 1;
Stk.Push(WillPush);
};
PushAct(Popped.CurrX, Popped.CurrY - 1);
PushAct(Popped.CurrX, Popped.CurrY + 1);
PushAct(Popped.CurrX - 1, Popped.CurrY);
PushAct(Popped.CurrX + 1, Popped.CurrY);
}
return WillReturn;
}
// 座標のハッシュ値を返す
static int GetHash(int pX, int pY)
{
return pX * 100 + pY;
}
////////////////////////////////////////////////////////////////
// IEnumerable<string>をcharの2次元配列に設定する
////////////////////////////////////////////////////////////////
static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = pStrEnum.ToList();
if (StrList.Count == 0) {
return new char[0, 0];
}
int UB_X = StrList[0].Length - 1;
int UB_Y = StrList.Count - 1;
char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = StrList[Y][X];
}
}
return WillReturn;
}
}