BfS
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int n, m, g[11][11], dist[11][11], dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
vector<pii> sbk;//记录草地
int bfs(pii a, pii b){
memset(dist, -1, sizeof dist);
queue<pii> q;
q.push(a);
if(a != b) q.push(b);//a,b不一样放b,不然会重复
dist[a.first][a.second] = dist[b.first][b.second] = 0;
int cnt = 0, maxt = 0;//cnt记录点燃的草地个数
for(;q.size();q.pop(), cnt++){
auto [x, y] = q.front();
for(int i = 0; i < 4; i++){
int nx = x + dx[i], ny = y + dy[i];
if(~nx && ~ny && nx < n && ny < m && g[nx][ny] && dist[nx][ny] == -1){
q.push({nx, ny});
dist[nx][ny] = dist[x][y] + 1;
maxt = max(maxt, dist[nx][ny]);
}
}
}
if(cnt == (int)sbk.size()) return maxt;//如果点燃了所有草地
return -1;
}
int main(){
int tt; cin >> tt;
for(int _ = 1; _ <= tt; _++){
sbk.clear();
cin >> n >> m; char c;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(cin >> c && c == '#') g[i][j] = 1, sbk.push_back({i, j});//记录草地
else g[i][j] = 0;
if(sbk.empty()){//没有草地
printf("Case %d: -1\n", _);
continue;
}
int ans = 2e9;
for(int i = 0; i < (int)sbk.size(); i++)
for(int j = i; j < (int)sbk.size(); j++){//暴力枚举两个点燃的草地
int tmp = bfs(sbk[i], sbk[j]);
if(tmp != -1) ans = min(ans, tmp);//记录答案
}
if(ans == 2e9) ans = -1;
printf("Case %d: %d\n", _, ans);
}
return 0;
}