계속 시간 초과가 뜨다가 이번에는 오답 행진을 하고 있습니다.
머리가 멍해질 때까지 생각해 봤는데, 잘 모르겠네요.
고수님의 도움을 요청드려요.
간단한 알고리즘 설명입니다.

1. 1초 후를 시뮬레이션 합니다. tick()함수.

2. delete_path_and_return_len()을 for loop으로 돌립니다. 이 함수는 패스를 찾아서 그 길이를 돌려줍니다. 대상이 된 path는 지워주고요. 여기서 약간의 트릭을 썼는데, path를 찾을 때, 처음 부터 찾는게 아니라, 이전 찾아진 path 시작점부터 찾았습니다. 처음부터 찾을라니 시간초과가 뜨더라구요;;

3. delete_path_and_return_len()이 path를 더 이상 찾지 못하면, 박테리아가 하나도 없는지 봅니다. empty()함수.

4. 비어 있지 않다면, loop이 있다는 말이므로 -1 출력. 아니면 (max_len+1) / 2 +1

몇가지 덧붙이면
* 인텍싱은 (1,1)부터 했습니다. 편의를 위해
* 예외처리한 경우는, 초기에 박테리아 하나도 없는 경우.

알고리즘이 틀린 걸까요? 아니면 구현을 잘 못한걸까요?;;
아래는 소스입니다.

~~~ c++
#include
#include
#include
using namespace std;

int T, W, H, last_h, last_w;
char B[505][505];

void tick() {
std::vector > ch;

for (int h = 1; h <= H; h++)
    for (int w = 1; w <= W; w++)
        if (B[h][w] && (B[h - 1][w] + B[h + 1][w] + B[h][w - 1] + B[h][w + 1]) != 2)
            ch.push_back(std::make_pair(h, w));
for (size_t i = 0; i < ch.size(); i++)
    B[ch[i].first][ch[i].second] = 0;

}

int delete_path_return_len() {
int h, w, fnd = 0;
//path 시작점을 찾는다.
for (h = last_h; h <= H; h++) {
for (w = last_w; w <= W; w++) {
// 박테리아를 가지고 있고, 주변 박테리아가 1개보다 같거나 작을 때, 나는 path 시작점이 된다.
if (B[h][w] && (B[h - 1][w] + B[h + 1][w] + B[h][w - 1] + B[h][w + 1]) <= 1) {
fnd = 1;
break;
}
}
if (fnd) break;
}

if (!fnd) return 0;

int l = 0;
// 찾은 path 시작점을 저장하고 다음에는 여기서 시작한다. 이 시점 이전에는 path 시작점이 있을 수 없으므로
last_h = h, last_w = w;

// path를 따라가며 길이를 구하고 지운다.
while (B[h][w]) {
    l++;
    B[h][w] = 0;
    if (B[h - 1][w]) h--;
    else if (B[h + 1][w]) h++;
    else if (B[h][w - 1]) w--;
    else if (B[h][w + 1]) w++;
}
return l;

}

int empty() {
for (int h = 1; h <= H; h++)
for (int w = 1; w <= W; w++)
if (B[h][w])
return 0;
return 1;
}

int main() {
cin >> T;
while (T--) {
memset(B, 0, sizeof(B));
cin >> W >> H;
last_h = last_w = 1;
for (int h = 1; h <= H; h++) {
cin >> &B[h][1];
for (int w = 1; w <= W; w++)
B[h][w] = (B[h][w] == '*');
}
if (empty())
cout << "0" << endl;
else {
tick();
int mx = 0;
for (int i = delete_path_return_len(); i; i = delete_path_return_len()) {
mx = max(mx, i);
}
cout << (empty() ? (mx + 1) / 2 + 1 : -1) << endl;
}
}
}

</spoiler>