bing搜索_巨量引擎搜索

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

A–棋盘问题

POJ-1321

链接： https://vjudge.net/problem/15202/origin

类似n皇后问题，需要注意的是dfs的边界问题（t在此处

思路：当前走到i/u行j列，判断该点是否可以放棋子，不可以就j++，可以就dfs(i + 1)，对放的棋子数进行计数，若等于k则return，记得状态还原。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 const int N = 20;
 7 
 8 int n, k, flag;
 9 char g[N][N];
10 bool row[N];
11 
12 void dfs(int u, int x){
13     if(x == k) {
14         flag ++;
15         return;
16     }
17     
18     for(int i = u; i < n ; i ++ ){
19         for(int j = 0; j < n; j ++ ){
20             if(g[i][j] != '.' && !row[j]){
21             row[j] = true;
22             dfs(i + 1, x + 1);
23             row[j] = false;
24             }
25         }
26     }
27     return;
28 }
29 
30 int main()
31 {
32     while(scanf("%d %d", &n, &k) != EOF){
33         if(n ==-1 && k == -1) break;
34         flag = 0;
35         for(int y = 0; y < n; y ++ )
36             for(int z = 0; z < n; z ++ )
37                 cin>>g[y][z];
38         dfs(0, 0);
39         printf("%d\n",flag);
40     }
41     return 0;
42 }

View Code

B–Dungeon Master

POJ-2251

链接： https://vjudge.net/problem/15203/origin

一个三维地图上的bfs，注意三维数组的存储

变量设了太多，没有注意到重复了，改了很久才发现……

以后用结构体了orz

提交的时候选用G++，然后就是不要再用auto了

思路：从起点开始向六个方向进行搜索，其他和二维地图相同。

代码：

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 typedef pair<int, int> PII;
 9 queue<PII> q;//y z 
10 queue<int> u;//x
11 const int N = 35;
12 int d[N][N][N];
13 char g[N][N][N];
14 int l, r, c;//l:z  r:y  c:x
15 int sx, sy, sz;//终点 
16 int tx, ty, tz;//起点 
17 char str[2];
18 int bfs()
19 {
20     memset(d, -1, sizeof(d));
21     d[tz][ty][tx] = 0;
22     q.push({ty, tz});
23     u.push(tx);
24     int dx[6] = {0, 0, -1, 1, 0, 0};
25     int dy[6] = {-1, 1, 0, 0, 0, 0};
26     int dz[6] = {0, 0, 0, 0, 1, -1};//前后左右上下
27     
28     while(q.size()){
29         pair<int, int> t; 
30         t = q.front();
31         int a = t.first;//y
32         int b = u.front();//x
33         int o = t.second;//z
34         q.pop();
35         u.pop();
36         for(int i = 0; i < 6; i ++ ){
37             int x = b + dx[i];
38             int y = a + dy[i];
39             int z = o + dz[i];
40             if(x >= 0 && x < c && y >= 0 && y < r && z >= 0 && z < l && d[z][y][x] == -1 && (g[z][y][x] == '.' || g[z][y][x] == 'E'))
41             {
42                 d[z][y][x] = d[o][a][b] + 1;
43                 q.push({y, z});
44                 u.push(x);    
45             }
46             if(x == sx && sy == y && sz == z) break;
47         }
48     }
49     return d[sz][sy][sx];
50 }
51 
52 int main()
53 {
54     while(cin>>l>>r>>c){
55         gets(str);
56         if(l == 0 && r == 0 && c == 0) break;
57         for(int i = 0; i < l; i ++ ){
58             for(int j = 0; j < r; j ++ ){
59                 scanf("%s", g[i][j]);
60             }
61         }
62         
63         for(int i = 0; i < l; i ++ ){
64             for(int j = 0; j < r; j ++ ){
65                 for(int k = 0; k < c; k ++ ){
66                     if(g[i][j][k] == 'E') sx = k, sy = j, sz = i;
67                     if(g[i][j][k] == 'S') tx = k, ty = j, tz = i;
68                 }
69             }
70         }
71         int p = bfs();
72         if(p == -1) printf("Trapped!\n");
73         else printf("Escaped in %d minute(s).\n", p);
74     }
75     return 0;
76 }

View Code

C–Catch That Cow

POJ-3278

链接： https://vjudge.net/problem/15204/origin

在一维地图上进行bfs寻找最短路径

有三种操作：加1，减1，乘2

需要进行剪枝，否则会mle

当n>=k时，直接输出n-k即可

注意标记状态（忘记标记一直mle

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <cmath>
 6 
 7 using namespace std;
 8 const int N = 1e5 + 10;
 9 bool flag[N];
10 int d[N];
11 int n, k;
12 queue<int> q;
13 int bfs(int a, int b){
14     memset(d, -1, sizeof d);
15     d[a] = 0;
16     q.push(a);
17     while(q.size()){
18         int p = q.front();
19         q.pop();
20         if(p-1 >= 0 && !flag[p-1]) {
21             q.push(p-1);
22             d[p-1] = d[p] + 1;
23             flag[p-1] = true;
24         }
25         if(p+1 <= N && !flag[p+1]){
26             q.push(p+1);
27             d[p+1] = d[p] + 1;
28             flag[p+1] = true;
29         }
30         if(p*2 <=N && !flag[p*2]){
31             q.push(p*2);
32             d[p*2] = d[p] + 1;
33             flag[p*2] = true;
34         }
35         if(p-1 == b || p+1 == b || p*2 == b) break;
36     }
37     return d[b];
38 }
39 
40 int main()
41 {
42     cin>>n>>k;
43     int ans;
44     while(q.size()) q.pop();
45     if(n >= k) ans = n - k;
46     else ans = bfs(n, k);
47     cout<<ans<<endl;
48     return 0;
49 }

View Code

D-Fliptile

POJ-3279

链接：https://vjudge.net/problem/17522/origin

这题我写了好多天……

需要用二进制对第一排状态进行枚举

于是学习了位运算的相关操作以及状态压缩

参考博客：https://blog.csdn.net/loy_184548/article/details/50949972

可以说是写的非常清楚了

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <cmath>
 7 
 8 using namespace std;
 9 
10 const int maxn = 16;
11 int m, n;
12 const int dx[5] = {-1, 0, 0, 0, 1};
13 const int dy[5] = {0, -1, 0, 1, 0};
14 int tile[maxn][maxn];
15 int opt[maxn][maxn];//最优解
16 int flip[maxn][maxn];//保存中间结果
17 
18 int get(int x, int y){
19     int c = tile[x][y];
20     for(int d = 0; d < 5; d ++ ){
21         int x2 = x + dx[d], y2 = y + dy[d];
22         if(0 <= x2 && x2 < m && 0 <= y2 && y2 < n)
23             c += flip[x2][y2];
24     }
25     return c % 2;
26 }
27 
28 int calc(){
29     for(int i = 1; i < m; i ++ ){
30         for(int j = 0; j < n; j ++ ){
31             if(get(i - 1, j)) flip[i][j] = 1 ;
32         }
33     }
34     for(int i = 0; i < n; i ++ ){
35         if(get(m - 1, i) != 0) return -1;
36     }
37     int res = 0;
38     for(int i = 0; i < m; i ++ ){
39         for(int j = 0; j < n; j ++ )
40             res += flip[i][j];
41     }
42     return res;
43 }
44 
45 void solve()
46 {
47     int res = -1;
48     for(int i = 0; i < 1 << n; i ++ ){
49         memset(flip, 0, sizeof flip);
50         for(int j = 0; j < n; j ++ ){
51             flip[0][n - j - 1] = i >> j & 1;
52         }
53         int num = calc();
54         if(num >= 0 && (res < 0 || num < res)){
55             res = num;
56             memcpy(opt, flip, sizeof flip);
57         }
58     }
59     if(res < 0) printf("IMPOSSIBLE\n");
60     else {
61         for(int i = 0; i < m; i ++ ){
62             for(int j = 0; j < n; j ++ ){
63                 printf("%d ", opt[i][j]);
64             }
65             printf("\n");
66         }
67     }
68 }
69 
70 int main()
71 {
72     cin>>m>>n;
73     for(int i = 0; i < m; i ++ )
74         for(int j = 0; j < n; j ++ )
75             cin>>tile[i][j];
76     solve();
77     return 0;
78 }

View Code

位运算的一些操作

1.空集  0
2.只含第i个元素的集合  1 << i
3.含有全部n个元素的集合  (1 << n) - 1
4.判断第i个元素是否属于s  if(s >> i & 1)
5.向集合中加入第i个元素 s | 1 << i
6.取出第i个元素  s >> i & 1
7.从集合中去掉第i个元素  s & ~(1 << i)
8. s + t  s|t
9.st  s & t

用二进制枚举状态
1.枚举所有子集   
    for(int s = 0; s < 1 << n; s ++ )
2.枚举某个集合sup的子集
    int sub = sup;
    do{sub = (sub - 1) & sup;} while(sub != sup);
3.枚举集合的大小为k的子集
    字典序最小子集为 comb = (1 << k) - 1
    每次循环求出最低位 x = comb & - comb
    y = comb + x;
    comb = ((comb & ~y) / x >> 1 ) | y;

E-Find the Multiple

POJ-1426

链接：https://vjudge.net/problem/15205/origin

题意：给出一个数，找到它的一个倍数且该倍数（10进制下）只由0和1组成

坑点：题目里说这个倍数不超过300位，我以为要用字符串，准备换java写了，结果发现long long就能过

　　　还有就是用c++提交t了，g++过了

待解决的疑惑：查了一些题解，发现很多人用dfs过的，搜到第19层就不搜了，不太明白为什么（

思路：简单的bfs，从1开始搜，搜过一个数之后，将它的十倍和十倍加一这两个数压进队列继续搜

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <queue>
 7 
 8 using namespace std;
 9 
10 long long bfs(int x){
11     queue<long long> q;
12     q.push(1);
13     while(q.size()){
14         long long f = q.front();
15         q.pop();
16         if(f % x == 0)
17             return f;
18         q.push(f * 10);
19         q.push(f * 10 + 1);
20     }
21     return -1;
22 }
23 
24 int main()
25 {
26     int n;
27     while(scanf("%d", &n) != EOF && n != 0){
28         long long x = bfs(n);
29         printf("%lld\n", x);
30     }
31     return 0;
32 }

View Code

F-Prime Path

POJ-3126

链接：https://vjudge.net/problem/15206/origin

题意：给出两个素数，每次只能改动一位，使第一个素数转变成第二个素数，求最少变多少次

思路：依然是一个简单bfs，改变数的每一位，判断其是否为素数，如果是，压入队列（各位只需要换成素数）

本题感想：我是憨憨?改了好久的bug，最后发现把个十百位的循环写进千位的去了……还有while循环里把queue.front的距离给初始化了orz

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 
 7 using namespace std;
 8 const int N = 1e5 + 10;
 9 int d[N];
10 bool vis[N];
11 int a, b;
12 bool is_prime(int x)
13 {
14     if (x < 2) return false;
15     for (int i = 2; i <= x / i; i ++ )
16         if (x % i == 0)
17             return false;
18     return true;
19 }
20 
21 void bfs() {
22     queue<int> q;
23     q.push(a);
24     while (!q.empty()) {
25         int p = q.front();
26         q.pop();
27         vis[p] = true;
28         if (p == b){
29             printf("%d\n", d[p]);
30             return ;
31         }
32         for (int i = 1; i < 10; i++) {
33             int y = p % 1000;
34             int u = y + i * 1000;
35             if (u != p && is_prime(u) && !vis[u]) {
36                 q.push(u);
37                 d[u] = d[p] + 1;
38                 vis[u] = true;
39             }
40         }
41         for (int i = 0; i < 10; i++) {
42             int x = p % 100;
43             int y = p / 1000;
44             int u = y * 1000 + i * 100 + x;
45             if (u != p && is_prime(u) && !vis[u]) {
46                 q.push(u);
47                 d[u] = d[p] + 1;
48                 vis[u] = true;
49             }
50         }
51         for (int i = 0; i < 10; i++) {
52             int x = p % 10;
53             int y = p / 100;
54             int u = y * 100 + x + i * 10;
55             if (u != p && is_prime(u) && !vis[u]) {
56                 q.push(u);
57                 d[u] = d[p] + 1;
58                 vis[u] = true;
59             }
60         }
61         for (int i = 1; i < 10; i += 2) {
62             int x = p / 10;
63             int u = x * 10 + i;
64             if (u != p && is_prime(u) && !vis[u]) {
65                 q.push(u);
66                 d[u] = d[p] + 1;
67                 vis[u] = true;
68             }
69         }
70     }
71     printf("Impossible\n");
72     return ;
73 }
74 
75 int main()
76 {
77     int t;
78     cin>>t;
79     while(t --){
80         scanf("%d %d", &a, &b);
81         memset(vis, false, sizeof vis);
82         memset(d, 0, sizeof d);
83         bfs();
84     }
85     return 0;
86 }

View Code

G-Shuffle’m Up

POJ-3087

链接：https://vjudge.net/problem/15207/origin

题意：给出s1,s2,s3三个字符串（s1，s2长度为c，s3长度为2c），s1,s2通过s2一张s1一张的方式组成新的字符串a，如果a与s3相同，则输出这是第几组数据和变换了几次，如果不同，就将前一半作为新的s1，后一半作为新的s2，重复上述操作，如果不能得到就输出-1

思路：好像用不上搜索，直接模拟做了……

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <string>
 7 #include <map>
 8 using namespace std;
 9 
10 int main()
11 {
12     char s1[110], s2[110], s3[220], str[2];
13     int t, c;
14     scanf("%d", &t);
15     int flag = 0;
16     while(t--){
17         flag ++ ;
18         scanf("%d", &c);
19         scanf("%s", s1);
20         gets(str);
21         scanf("%s", s2);
22         gets(str);
23         scanf("%s", s3);
24         gets(str);
25         map<string, bool> mp;
26         int time = 0;
27         while(true){
28             char a[220];
29             int cnt = 0;
30             for(int i = 0; i < c; i ++ ){
31                 a[cnt ++ ] = s2[i];
32                 a[cnt ++ ] = s1[i];
33             }
34             a[cnt] = '\0';
35             time ++ ;
36             if(!strcmp(a, s3)){
37                 printf("%d %d\n", flag, time);
38                 break;
39             }
40             if(mp[a] == true && strcmp(a, s3)){
41                 printf("%d -1\n", flag);
42                 break;
43             }
44             mp[a] = true;
45             for(int i = 0; i < c; i ++ )
46                 s1[i] = a[i];
47             for(int i = c; i < 2 * c; i ++ )
48                 s2[i-c] = a[i];
49             s1[c] = '\0';
50             s2[c] = '\0';
51         }
52     }
53     return 0;
54 }

View Code

H-Pots

POJ-3414

链接：https://vjudge.net/problem/15208/origin

题意：有两个容积为a，b的容器，开始都为空，有六种操作，问最少经过怎样的操作能使其中一个容器的水体积达到c

思路：还是用bfs，如果进行操作之后得到的新体积为出现过，就压入队列中。

注意：本题要保存bfs的路径，我用的方法是新建一个三维数组，存储上一个点的两个值和进行的操作。bfs准备跳出时进行输出，用while向前遍历，直至（0， 0），每次将操作压进栈里，遍历结束后再输出然后出栈。不知道有没有更简单的方法（

本题自闭debug一个多小时，总结一下错误：

1.第一个进队的是{0，0}，而不是{a，b}

2.六种操作有各自的进入条件，进入之后先进行操作再判断是否已经出现过，没出现再距离++

3.+1和++的区别（我好智障

4.输出的while里改变x和y的值时，注意x = p[x][y][0]后x的值变了！！！！！y的值直接用x算出来就不对了！！！！！一直没看出来这里orz

以后赋值还是分行写吧，写在一行看不出来

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <cstring>
  6 #include <queue>
  7 #include <stack>
  8 
  9 using namespace std;
 10 
 11 int a, b, c;
 12 typedef pair<int, int> PII;
 13 const int N = 110;
 14 int level[N][N], p[N][N][3];
 15 bool vis[N][N], flag;
 16 
 17 string path[] = {
 18     "FILL(1)"
 19     ,"FILL(2)"
 20     ,"DROP(1)"
 21     ,"DROP(2)"
 22     ,"POUR(1,2)"
 23     ,"POUR(2,1)"
 24 };
 25 
 26 PII fi(int i, int x, int y){
 27     if(i == 1)
 28         return {a, y};
 29     else
 30         return {x, b};
 31 }
 32 
 33 PII drop(int i, int x, int y){
 34     if(i == 1)
 35         return {0, y};
 36     else
 37         return {x, 0};
 38 }
 39 
 40 PII pour(int i, int x, int y){//i为被倒水的容器
 41     if(i == 1){
 42         int cnt = a - x;
 43         if(y > cnt)
 44             return {a, y - cnt};
 45         else
 46             return {x + y, 0};
 47     }
 48     else{
 49         int cnt = b - y;
 50         if(x > cnt)
 51             return {x - cnt, b};
 52         else
 53             return {0, x + y};
 54     }
 55 }
 56 
 57 void print(int x, int y){
 58     printf("%d\n", level[x][y]);
 59     stack<int> s;
 60     int xx = x, yy = y;
 61     while(level[x][y]!=0){
 62         s.push(p[x][y][2]);
 63         x = p[xx][yy][0];
 64         y = p[xx][yy][1];
 65         xx = x;
 66         yy = y;
 67     }
 68     while(!s.empty()){
 69         int k = s.top();
 70         cout<<path[k]<<endl;
 71         s.pop();
 72     }
 73 }
 74 
 75 void bfs(){
 76     queue<PII> q;
 77     q.push({0, 0});
 78     level[0][0] = 0;
 79     memset(p, 0, sizeof p);
 80     while(!q.empty()){
 81         PII cnt = q.front();
 82         int x1 = cnt.first;
 83         int x2 = cnt.second;
 84         q.pop();
 85         vis[x1][x2] = true;
 86         if(x1 == c || x2 == c){
 87             print(x1, x2);
 88             flag = true;
 89             break;
 90         }
 91         else{
 92 
 93             if(x1 != a){
 94                 PII m = fi(1, x1, x2);
 95                 int y1 = m.first, y2 = m.second;
 96                 if(!vis[y1][y2]){
 97                     p[y1][y2][0] = x1, p[y1][y2][1] = x2, p[y1][y2][2] = 0;
 98                     level[y1][y2] = level[x1][x2] + 1;
 99                     q.push(m);
100                 }
101             }
102 
103             if(x2 != b){
104                 PII m = fi(2, x1, x2);
105                 int y1 = m.first, y2 = m.second;
106                 if(!vis[y1][y2]){
107                     p[y1][y2][0] = x1, p[y1][y2][1] = x2, p[y1][y2][2] = 1;
108                     level[y1][y2] = level[x1][x2] + 1 ;
109                     q.push(m);
110                 }
111             }
112 
113             if(x1 != 0){
114                 PII m = drop(1, x1, x2);
115                 int y1 = m.first, y2 = m.second;
116                 if(!vis[y1][y2]){
117                     p[y1][y2][0] = x1, p[y1][y2][1] = x2, p[y1][y2][2] = 2;
118                     level[y1][y2] = level[x1][x2] + 1 ;
119                     q.push(m);
120                 }
121             }
122 
123             if(x2 != 0){
124                 PII m = drop(2, x1, x2);
125                 int y1 = m.first, y2 = m.second;
126                 if(!vis[y1][y2]){
127                     p[y1][y2][0] = x1, p[y1][y2][1] = x2, p[y1][y2][2] = 3;
128                     level[y1][y2] = level[x1][x2] + 1 ;
129                     q.push(m);
130                 }
131             }
132 
133             if(x2 != b && x1 != 0){
134                 PII m = pour(2, x1, x2);
135                 int y1 = m.first, y2 = m.second;
136                 if(!vis[y1][y2]){
137                     p[y1][y2][0] = x1, p[y1][y2][1] = x2, p[y1][y2][2] = 4;
138                     level[y1][y2] = level[x1][x2] + 1 ;
139                     q.push(m);
140                 }
141             }
142 
143             if(x1 != a && x2 != 0){
144                 PII m = pour(1, x1, x2);
145                 int y1 = m.first, y2 = m.second;
146                 if(!vis[y1][y2]){
147                     p[y1][y2][0] = x1, p[y1][y2][1] = x2, p[y1][y2][2] = 5;
148                     level[y1][y2] = level[x1][x2] + 1 ;
149                     q.push(m);
150                 }
151             }
152 
153         }
154     }
155     if(!flag) printf("impossible\n");
156 }
157 
158 int main()
159 {
160     scanf("%d %d %d", &a, &b, &c);
161     bfs();
162     return 0;
163 }

View Code

// oj交不上题orz flag没了

I-Fire Game

FZU-2150

链接：https://vjudge.net/problem/48789/origin

题意：n * m 的矩阵， #代表草， . 代表空地，有两个人，分别选两块地（可以相同）放一把火烧草，火只能向上下左右蔓延，如果是空地就不能烧过去，问能不能烧完，如果可以，最少烧多少秒

思路：从两个点开始进行bfs

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <string>
  5 #include <cstring>
  6 #include <cmath>
  7 #include <queue>
  8 #include <vector>
  9 
 10 using namespace std;
 11 
 12 #define inf 0x3f3f3f3f
 13 
 14 int n, m;
 15 bool vis[15][15];
 16 char grid[15][15];
 17 int casee;
 18 int ans;
 19 struct node{
 20     int x, y, depth;
 21 };
 22 vector<node> grass;
 23 bool check(int x, int y){
 24     return !vis[x][y] && grid[x][y] == '#' && x >= 0 && x < n && y >= 0 && y < m;
 25 }
 26 
 27 bool judge(){
 28     for(int i = 0; i < n; i ++ ){
 29         for(int j = 0; j < m; j ++ ){
 30             if(grid[i][j] == '#' && !vis[i][j])
 31                 return false;
 32         }
 33     }
 34     return true;
 35 }
 36 
 37 void init(){
 38     grass.clear();
 39     memset(vis, false, sizeof vis);
 40 }
 41 
 42 int nex[][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
 43 
 44 int bfs(node n1, node n2){
 45     queue<node> q;
 46     while(!q.empty()) q.pop();
 47     q.push(n1);
 48     q.push(n2);
 49     memset(vis, false, sizeof vis);
 50     vis[n1.x][n1.y] = true;
 51     vis[n2.x][n2.y] = true;
 52     int depthest = 0;
 53 
 54     while(!q.empty()){
 55         node now = q.front();
 56         node nxt;
 57         q.pop();
 58         depthest = now.depth;
 59         for(int i = 0; i < 4; i ++ ){
 60             nxt.x = now.x + nex[i][0];
 61             nxt.y = now.y + nex[i][1];
 62             nxt.depth = now.depth + 1;
 63             if(check(nxt.x, nxt.y)){
 64                 if(!vis[nxt.x][nxt.y]){
 65                     vis[nxt.x][nxt.y] = true;
 66                     q.push(nxt);
 67                 }
 68             }
 69         }
 70     }
 71     return depthest;
 72 }
 73 
 74 int main()
 75 {
 76     int t;
 77     scanf("%d", &t);
 78     while(t -- ){
 79         init();
 80         ans = inf;
 81         scanf("%d %d", &n, &m);
 82         for(int i = 0; i < n; i ++ )
 83             scanf("%s", grid[i]);
 84         for(int i = 0; i < n; i ++ )
 85             for(int j = 0; j < m; j ++ ){
 86                 if(grid[i][j] == '#'){
 87                     node g;
 88                     g.x = i;
 89                     g.y = j;
 90                     g.depth = 0;
 91                     grass.push_back(g);
 92                 }
 93             }
 94         for(int i = 0; i < grass.size(); i ++ ){
 95             for(int j = i; j < grass.size(); j ++ ){
 96                 grass[i].depth = 0;
 97                 grass[j].depth = 0;
 98                 int tmp = bfs(grass[i], grass[j]);
 99                 if(judge())
100                     ans = min(ans, tmp);
101             }
102         }
103         printf("Case %d: ", ++casee);
104         if(ans == inf)
105             printf("-1\n");
106         else
107             printf("%d\n", ans);
108     }
109     return 0;
110 }