bing搜索_巨量引擎搜索

bing搜索_巨量引擎搜索A–棋盘问题POJ-1321链接:https://vjudge.net/problem/15202/origin类似n皇后问题,需要注意的是dfs的边界问题(t在此处思路:当前走到i/u行

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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,记得状态还原。

bing搜索_巨量引擎搜索
bing搜索_巨量引擎搜索

 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了

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

代码:

bing搜索_巨量引擎搜索
bing搜索_巨量引擎搜索

 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

代码:

bing搜索_巨量引擎搜索
bing搜索_巨量引擎搜索

 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

可以说是写的非常清楚了

代码:

bing搜索_巨量引擎搜索
bing搜索_巨量引擎搜索

 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开始搜,搜过一个数之后,将它的十倍和十倍加一这两个数压进队列继续搜

代码:

bing搜索_巨量引擎搜索
bing搜索_巨量引擎搜索

 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

代码:

bing搜索_巨量引擎搜索
bing搜索_巨量引擎搜索

 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

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

代码:

bing搜索_巨量引擎搜索
bing搜索_巨量引擎搜索

 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

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

代码:

bing搜索_巨量引擎搜索
bing搜索_巨量引擎搜索

 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

代码:

bing搜索_巨量引擎搜索
bing搜索_巨量引擎搜索

 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 }

View Code

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/167669.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Linux下安装Tomcat 10

    Linux下安装Tomcat 10(Linux)Deepin下安装Tomcat101)在官网下载tar.gz包2)解压到目录(这里‘用户名’换成你自己的)sudotar-zxvf/home/用户名/Downloads/apache-tomcat-10.0.0.tar.gz-C/usr/local3)重命名sudomv/usr/local/apache-tomcat-10.0.0/usr/local/Tomcat4)测试sudo/usr/local/Tomcat/bin/startup.sh若失败则

  • Android preference_安卓fragment切换

    Android preference_安卓fragment切换PreferenceFragmentAndroid应用程序通常要提供首选项,以允许用户定制应用程序。例如,可以允许用户保存那些用于访问Web资源的登录凭据,等等。在Android中,可以使用PreferenceActivity基类为用户显示一个用于编辑首选项的活动。在Android3.0和更高版本中,可以使用PreferenceFragment类实现相同的功能。//XML//新建(res…

  • RTP协议简介

    RTP协议简介以下转自:nkmnkm的专栏http://blog.csdn.net/niu_gao/article/details/69467812017/07/21RTP协议分析(转自:http://blog.csdn.net/bripengandre/article/details/2238818)分类: NetworkSecurity2008-04-0116

  • QStringList与QString互转

    QStringList与QString互转QStringListfonts;fonts&lt;&lt;"Arial"&lt;&lt;"Helvetica"&lt;&lt;"Times"&lt;&lt;"Courier";QStringstr=fonts.join(",");QStringstr="name1,path1;name2,p

  • 大约apache 2.4.X虚拟主机配置问题的版本号后,

    大约apache 2.4.X虚拟主机配置问题的版本号后,

  • dropdownlist绑定数据源_不能绑定到字段或数据成员

    dropdownlist绑定数据源_不能绑定到字段或数据成员如何使用DropDownList控件绑定数据呢,今天我们来介绍一下比较常用的一种方法——前后台结合方式:首先,我们需要拉一个DropDownList控件:然后,通过控件配置SqlDataSource数据源,选择合适的数据表:接着,设置DataTextField(数据源中提供项文本的字段)和DataValueField(数据源中提供项值的字段)属性:前台显示如下:配置完之后,一定不要忘记删除DataSourceID属性和生成的SqlDataSource控件:

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号