又重头开始刷kuangbin，有些题用了和以前不一样的思路解决。全部题解如下
点击每道题的标题即可跳转至VJ题目页面。
A-棋盘问题
棋子不能摆在相同行和相同列，所以我们可以依此枚举每一行，然后标记每一列是否走过，在此基础上进行DFS即可。
代码如下：
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 int n,m,sum; 5 char mp[10][10]; 6 int vis[10] = {0}; 7 8 void dfs(int r,int k){ 9 if(k == m){ 10 sum++; 11 return ; 12 } 13 for(int i = r; i < n; i++){ 14 for(int j = 0; j < n; j++){ 15 if(mp[i][j] == '#' && !vis[j]){ 16 vis[j] = 1; 17 dfs(i+1,k+1); 18 vis[j] = 0; 19 } 20 } 21 } 22 } 23 24 int main(){ 25 while(cin>>n>>m && n > 0 && m > 0){ 26 memset(vis, 0, sizeof vis); 27 sum = 0; 28 for(int i = 0; i < n; i++){ 29 for(int j = 0; j < n; j++){ 30 cin>>mp[i][j]; 31 } 32 } 33 dfs(0,0); 34 cout << sum << endl; 35 } 36 return 0; 37 }
B-Dungeon Master
题意就是给你一个三维的迷宫，从S走到E，判断能否逃脱若能逃离则输出最短时间。
裸BFS/DFS，只是多了两个方向，向上走和向下走，我用的是BFS，代码如下：
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 6 int r,c,h; 7 char mp[35][35][35]; 8 bool vis[35][35][35]; 9 int sz,sx,sy,ez,ex,ey; 10 11 int fx[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,-1},{0,0,1}}; 12 13 struct node{ 14 int z,x,y,t; 15 }; 16 17 bool check(int x,int y,int z){ 18 if(mp[z][x][y] == '#' || vis[z][x][y] || z < 0 || z >= h || x < 0 || x >= r || y < 0 || y >= c){ 19 return false; 20 } 21 vis[z][x][y] = 1; 22 return true; 23 } 24 25 int bfs(){ 26 memset(vis, false, sizeof vis); 27 queue<node> q; 28 q.push(node{sz,sx,sy,0}); 29 vis[sz][sx][sy] = 1; 30 while(!q.empty()){ 31 node now = q.front(); 32 q.pop(); 33 //cout << now.z << " " << now.x << " " << now.y << endl; 34 if(now.z == ez && now.x == ex && now.y == ey){ 35 return now.t; 36 } 37 for(int i = 0; i < 6; i++){ 38 int nx = now.x + fx[i][0]; 39 int ny = now.y + fx[i][1]; 40 int nz = now.z + fx[i][2]; 41 if(check(nx,ny,nz)){ 42 q.push(node{nz,nx,ny,now.t+1}); 43 } 44 } 45 } 46 return -1; 47 } 48 49 50 int main(){ 51 ios_base::sync_with_stdio(0); 52 while(cin >> h >> r >> c && r ){ 53 for(int k = 0; k < h; k++){ 54 for(int i = 0; i < r; i++){ 55 for(int j = 0; j < c; j++){ 56 cin>>mp[k][i][j]; 57 if(mp[k][i][j] == 'S'){ 58 sz = k,sx = i,sy = j; 59 } 60 else if(mp[k][i][j] == 'E'){ 61 ez = k,ex = i,ey = j; 62 } 63 } 64 } 65 } 66 int ret = bfs(); 67 if(ret == -1) 68 cout << "Trapped!" << endl; 69 else 70 cout << "Escaped in " << ret << " minute(s)." << endl; 71 72 } 73 return 0; 74 }
C-Catch That Cow
题意就是你现在在n位置处，牛在k位置处，你有下面三种走路方式，每次花费一分钟，牛不会动，问抓到牛的最小时间。
- 走到x+1位置处
- 走到x-1位置处
- 走到x*2位置处
BFS模拟即可，注意判断走到x*2时候，应该先判断x*2是否越界再判断vis[x*2]是否走过，可以用短路运算符&&实现，否则会造成RE，当然你也可以开成两倍的 数组空间来避免这种错误，但我还是推荐使用前者方式。
代码如下：
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 6 int n,k; 7 bool vis[100005]; 8 9 struct node{ 10 int s,t; 11 }; 12 13 int bfs(){ 14 memset(vis,0,sizeof vis); 15 queue<node> q; 16 q.push(node{n,0}); 17 vis[n] = 1; 18 while(!q.empty()){ 19 node now = q.front(); 20 q.pop(); 21 if(now.s == k) 22 return now.t; 23 if(now.s-1 >= 0 && !vis[now.s-1]){ 24 vis[now.s-1] = 1; 25 q.push(node{now.s-1,now.t+1}); 26 } 27 if(now.s+1 <= 100000 && !vis[now.s+1]){ 28 vis[now.s+1] = 1; 29 q.push(node{now.s+1,now.t+1}); 30 } 31 if(now.s*2 <= 100000 && !vis[now.s*2]){ 32 vis[now.s*2] = 1; 33 q.push(node{now.s*2,now.t+1}); 34 } 35 } 36 return 0; 37 } 38 39 int main(){ 40 ios_base::sync_with_stdio(0); 41 while(cin>>n>>k){ 42 cout << bfs() << endl; 43 } 44 return 0; 45 }
D-Fliptile
玩过关灯游戏理解这个题就很简单，n*m的矩阵，0代表灯关，1代表灯开，然后可以反转某个灯的状态，但是这个灯周围四个方向的灯也会反转，然后问如何吧所有灯全关掉，若是不可能则输出IMPOSSIBLE，若是有多种情况请输出字典序最小的那个操作矩阵。
思路就是枚举，如何枚举，首先我们可以枚举第一层的每种操作可能，若是上一层有灯没关，这层的相应位置则必须反转，这样只要判断最下面一层的灯是否全关了即可。
那么我们需要对第一层枚举多少种状态呢？答案是2^m种，为什么呢，因为每层有m个灯，每种灯两个状态，所以就是2^m种操作方式，每种操作方式也就刚好对应了0——2^m-1中数的二进制，
例如对于样例，需要枚举0——15
0 = 0000
1 = 0001
……
15 = 1111
二进制刚好就是第一层的操作方式，然后我们从第二层开始，判断上一层是否还有状态为灯开的灯，有则操作当前位置，再判断最后一层是否全为灯关。
至于字典序处理，我们只需要数操作矩阵1的个数，找最小值即可，你可能会问相等的情况呢，因为我们是按0->2^m-1，所以若是前面的1个数和后面1个数相等，字典序一定是前面的更小，所以无需考虑。
代码如下：
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 #include <vector> 5 #include <string> 6 #include <iomanip> 7 #include <cmath> 8 #include <climits> 9 using namespace std; 10 11 int n,m; 12 int mp[20][20],fp[20][20],vis[20][20]; 13 int fx[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; 14 15 void change(int i,int j){ 16 fp[i][j] ^= 1; 17 for(int k = 0; k < 4; k++){ 18 int ni = i + fx[k][0]; 19 int nj = j + fx[k][1]; 20 if(ni >= 0 && nj >= 0 && ni < n && nj < m){ 21 fp[ni][nj] ^= 1; 22 } 23 } 24 } 25 26 int dfs(int k){ 27 memcpy(fp, mp, sizeof fp); 28 memset(vis, 0, sizeof vis); 29 int tot = m-1,res = 0; 30 while(k || tot>=0){ 31 int t = k%2; 32 vis[0][tot] = t; 33 res+=t; 34 if(t == 1) 35 change(0,tot); 36 tot--; 37 k /= 2; 38 } 39 //cout << setw(3) << setfill('0') << *fp[0] << endl; 40 for(int i = 1; i < n; i++){ 41 for(int j = 0; j < m; j++){ 42 if(fp[i-1][j] == 1){ 43 vis[i][j] = 1; 44 res++; 45 change(i,j); 46 } 47 } 48 } 49 for(int j = 0; j < m; j++){ 50 if(fp[n-1][j] == 1) 51 return 15*15*2; 52 } 53 return res; 54 } 55 56 int main(){ 57 ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); 58 while(cin>>n>>m){ 59 int ans[20][20]; 60 for(int i = 0; i < n; i++){ 61 for(int j = 0; j < m; j++){ 62 cin>>mp[i][j]; 63 } 64 } 65 int num = pow(2,m),minn = INT_MAX; 66 for(int i = 0; i < num; i++){ 67 int ret = dfs(i); 68 if(ret < minn){ 69 memcpy(ans, vis, sizeof vis); 70 minn = ret; 71 } 72 } 73 if(minn == 15*15*2) 74 cout << "IMPOSSIBLE" << endl; 75 else{ 76 for(int i = 0; i < n; i++){ 77 for(int j = 0; j < m; j++){ 78 if(j == 0) 79 cout << ans[i][j]; 80 else 81 cout << " " << ans[i][j]; 82 } 83 cout << endl; 84 } 85 } 86 } 87 return 0; 88 }
E-Find The Multiple
题意就是给你一个数n，然后让你找到一个只由1和0构成的数x，使得x是n的倍数。
BFS遍历即可，所有数组都在long long范围内有解，其实甚至都不需要BFS，直接依此枚举即可。
代码如下：
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 #include <string> 5 using namespace std; 6 7 int n; 8 9 long long bfs(){ 10 queue<long long> q; 11 q.push(1); 12 while(!q.empty()){ 13 long long x = q.front(); 14 q.pop(); 15 if(x % n == 0){ 16 return x; 17 } 18 q.push(x*10); 19 q.push(x*10+1); 20 } 21 return 0; 22 } 23 24 int main(){ 25 while(cin>>n && n){ 26 cout << bfs() << endl; 27 } 28 return 0; 29 }
F-Prime Path
题意就是给你两个数p1，p2，两个数都是四位数且都是素数，现在要把p1变成p2，规则是每次只能变换某一位上的数，且保证变换过程中的数也是素数。求最小变换次数。
还是BFS撒，从最高位开始变换，枚举所有素数的变换情况直至找到p2位置，这题麻烦的是变一位的数。
代码如下：
1 #include <iostream> 2 #include <queue> 3 #include <algorithm> 4 #include <string> 5 #include <cstring> 6 #include <cmath> 7 using namespace std; 8 9 int a,b; 10 int sum = 0; 11 bool vis[10005]; 12 13 struct node{ 14 int x,s; 15 }; 16 17 int change(int k,int i,int j){ 18 return k - (int(k/pow(10,3-i))%10)*pow(10,3-i) + j*pow(10,3-i); 19 } 20 21 bool isprime(int n){ 22 if(n==2 || n==3) 23 return true; 24 if(n%6 != 1 && n%6 != 5) 25 return false; 26 float n_sqrt = floor(sqrt((float)n)); 27 for(int i = 5; i <= n_sqrt; i += 6) 28 if(n%(i) == 0 | n%(i+2) == 0) 29 return false; 30 return true; 31 } 32 33 int bfs(int k){ 34 vis[k] = 1; 35 queue<node> q; 36 q.push(node{k,0}); 37 while(!q.empty()){ 38 node now = q.front(); 39 //cout << now.x << endl; 40 q.pop(); 41 if(now.x == b) 42 return now.s; 43 for(int i = 0; i < 4; i++){ 44 for(int j = 9; j >= 0; j--){ 45 if(i == 0 && j == 0) break; 46 int t = change(now.x,i,j); 47 if(isprime(t) && !vis[t]){ 48 vis[t] = 1; 49 q.push(node{t,now.s+1}); 50 } 51 } 52 } 53 } 54 return 0; 55 } 56 57 int main(){ 58 int t; 59 cin>>t; 60 while(t--){ 61 memset(vis, 0, sizeof vis); 62 cin>>a>>b; 63 sum = bfs(a); 64 cout << sum << endl; 65 } 66 return 0; 67 }
G-Shuffle'm Up
给你两个字符串长度都为n的字符串s1、s2，然后可以结合成题目图中那种形状，s2和s1交叉且s2的最下面一块在结合后的形状中还是最下面一块，s1又变成结合后的串的前n个字符，s2变成后n个字符，判断能否得到想要的字符串并询问最小变换次数。
主要考字符串处理，代码如下：
1 #include <iostream> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <map> 6 using namespace std; 7 8 string s1,s2,es; 9 int n; 10 map<string,int> vis; 11 12 string fun(string a,string b){ 13 string s = ""; 14 for(int i = 0; i < n; i++){ 15 s += b[i]; 16 s += a[i]; 17 } 18 return s; 19 } 20 21 int bfs(){ 22 int tot = 0; 23 while(1){ 24 tot ++; 25 string ss = fun(s1,s2); 26 //cout << ss << endl; 27 if(ss == es) 28 return tot; 29 if(!vis[ss]) 30 vis[ss] = 1; 31 else 32 break; 33 s1 = ss.substr(0,n); 34 s2 = ss.substr(n,n); 35 } 36 return -1; 37 } 38 39 int main(){ 40 int t; 41 cin>>t; 42 for(int tt = 1; tt <= t; tt++){ 43 cin>>n>>s1>>s2>>es; 44 cout << tt << ' ' << bfs() << endl; 45 } 46 return 0; 47 }
H-Pots
题意：有两个壶，容量分别为A，B，现在想要C（C ≤ max(a,b)）容量的水，然后可以相互倒水（只能倒到另一壶满或者本壶倒完为止），倒空本壶，装满本壶。问操作次数（SPJ，不需要最小操作 次数）并且应该如何操作。
因为有SPJ存在，所以直接BFS就行了，主要麻烦的是如何存储每次的操作。我是用一个vector<pair<char,int>>来实现，这样会消耗很大的空间，但题目空间很充裕，所以这个做法没有问题。
代码如下：
1 #include <iostream> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <map> 6 #include <vector> 7 #include <queue> 8 using namespace std; 9 10 int a,b,c; 11 bool vis[105][105]; 12 13 struct node{ 14 int a,b; 15 vector< pair<char,int> > v; 16 }; 17 18 void print(node n){ 19 cout << n.v.size() << endl; 20 for(vector< pair<char,int> >::iterator it = n.v.begin(); it != n.v.end(); it++){ 21 if(it->first == 'f') 22 cout << "FILL(" << it->second << ")" << endl; 23 else if(it->first == 'd') 24 cout << "DROP(" << it->second << ")" << endl; 25 else if(it->first == 'p') 26 cout << "POUR(" << it->second << ',' << (it->second == 1?2:1) << ")" << endl; 27 } 28 return ; 29 } 30 31 void bfs(){ 32 memset(vis, 0, sizeof vis); 33 queue<node> q; 34 q.push(node{0,0}); 35 vis[a][b] = 1; 36 while(!q.empty()){ 37 node now = q.front(),nt; 38 //cout << now.a << ' ' << now.b << endl; 39 q.pop(); 40 if(now.a == c || now.b == c){ 41 print(now); 42 return ; 43 } 44 if(now.a != 0 && !vis[0][now.b]){ 45 vis[0][now.b] = 1; 46 nt = now; 47 nt.a = 0; 48 nt.v.push_back(make_pair('d',1)); 49 q.push(nt); 50 } 51 if(now.b != 0 && !vis[0][now.a]){ 52 vis[now.a][0] = 1; 53 nt = now; 54 nt.b = 0; 55 nt.v.push_back(make_pair('d',2)); 56 q.push(nt); 57 } 58 if(now.a != a && !vis[a][now.b]){ 59 vis[a][now.b] = 1; 60 nt = now; 61 nt.a = a; 62 nt.v.push_back(make_pair('f',1)); 63 q.push(nt); 64 } 65 if(now.b != b && !vis[b][now.a]){ 66 vis[now.a][b] = 1; 67 nt = now; 68 nt.b = b; 69 nt.v.push_back(make_pair('f',2)); 70 q.push(nt); 71 } 72 if(now.a > 0 && now.b != b){ 73 int tb = now.b+now.a >= b?b:now.b+now.a; 74 int ta = b-now.b >= now.a?0:now.a-b+now.b; 75 if(!vis[ta][tb]){ 76 vis[ta][tb] = 1; 77 nt = now; 78 nt.a = ta; 79 nt.b = tb; 80 nt.v.push_back(make_pair('p',1)); 81 q.push(nt); 82 } 83 } 84 if(now.a != a && now.b > 0){ 85 int ta = now.a+now.b >= a?a:now.a+now.b; 86 int tb = a-now.a >= now.b?0:now.b-a+now.a; 87 if(!vis[ta][tb]){ 88 vis[ta][tb] = 1; 89 nt = now; 90 nt.a = ta; 91 nt.b = tb; 92 nt.v.push_back(make_pair('p',2)); 93 q.push(nt); 94 } 95 } 96 } 97 cout << "impossible" << endl; 98 return ; 99 } 100 101 int main(){ 102 while(cin>>a>>b>>c){ 103 bfs(); 104 } 105 return 0; 106 }
I-Fire!
题意就是人在J位置处，火在F位置处，不一定只有一堆火，火每分钟会向四周蔓延，人每分钟可以走一格，问能否逃出以及最小逃跑时间。
做了一遍再对比了一下以前的代码，发现区别还是很大的，以前是人每走一格就去BFS使得火蔓延一次，现在的做法是BFS人到达每个出口的时间，再BFS火到达每个出口的时间，再判断大小也就是判断人能否在火之前到达出口。
两份代码如下：
BEFORE（乱七八糟的宏定义比较多= =）：
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <sstream> 6 #include <iomanip> 7 #include <map> 8 #include <stack> 9 #include <deque> 10 #include <queue> 11 #include <vector> 12 #include <set> 13 #include <list> 14 #include <cstring> 15 #include <cctype> 16 #include <algorithm> 17 #include <iterator> 18 #include <cmath> 19 #include <bitset> 20 #include <ctime> 21 #include <fstream> 22 #include <limits.h> 23 #include <numeric> 24 25 using namespace std; 26 27 #define F first 28 #define S second 29 #define mian main 30 #define ture true 31 32 #define MAXN 1000000+5 33 #define MOD 1000000007 34 #define PI (acos(-1.0)) 35 #define EPS 1e-6 36 #define MMT(s) memset(s, 0, sizeof s) 37 typedef unsigned long long ull; 38 typedef long long ll; 39 typedef double db; 40 typedef long double ldb; 41 typedef stringstream sstm; 42 const int INF = 0x3f3f3f3f; 43 44 int n,m,t,jx,jy; 45 char mp[1005][1005]; 46 int vis[1005][1005]; 47 int fx[4][2] = {1,0,-1,0,0,-1,0,1}; 48 vector< pair<int,int> >q; 49 50 void init(){ 51 MMT(mp); 52 fill(vis[0],vis[0]+1005*1005,0); 53 q.clear(); 54 } 55 56 bool check(int x,int y){ 57 if(x < 0 || x >= n || y < 0 || y >= m || mp[x][y] == '#' || vis[x][y]) 58 return false; 59 return true; 60 } 61 62 int bfs(){ 63 queue< pair<int,int> >p; 64 queue< pair<int,int> >pf; 65 p.push(make_pair(jx,jy)); 66 int step = 0; 67 for(int i = 0, len = q.size(); i < len; i++){ 68 vis[q[i].F][q[i].S] = 1; 69 pf.push(q[i]); 70 } 71 vis[jx][jy] = 1; 72 while(!p.empty()){ 73 pair<int,int>nx = p.front(); 74 75 if(nx.F == 0 || nx.F == n-1 || nx.S == 0 || nx.S == m-1) 76 return vis[nx.F][nx.S]; 77 78 if(vis[nx.F][nx.S] > step) 79 step++; 80 if(vis[nx.F][nx.S] == step){ 81 while(!pf.empty()){ 82 pair<int,int>nf = pf.front(); 83 if(vis[nf.F][nf.S] > step) 84 break; 85 pf.pop(); 86 for(int i = 0; i < 4; i++){ 87 int nxx = nf.F + fx[i][0]; 88 int nxy = nf.S + fx[i][1]; 89 if(check(nxx,nxy)){ 90 vis[nxx][nxy] = vis[nf.F][nf.S] + 1; 91 pf.push(make_pair(nxx,nxy)); 92 } 93 } 94 } 95 } 96 p.pop(); 97 for(int i = 0; i < 4; i++){ 98 int nxx = nx.F + fx[i][0]; 99 int nxy = nx.S + fx[i][1]; 100 if(check(nxx,nxy)){ 101 vis[nxx][nxy] = vis[nx.F][nx.S] + 1; 102 p.push(make_pair(nxx,nxy)); 103 } 104 } 105 } 106 return -1; 107 } 108 109 int main(){ 110 ios_base::sync_with_stdio(false); 111 cout.tie(0); 112 cin.tie(0); 113 cin>>t; 114 while(t--){ 115 init(); 116 cin>>n>>m; 117 for(int i = 0; i < n; i++){ 118 for(int j = 0; j < m; j++){ 119 cin>>mp[i][j]; 120 if(mp[i][j] == 'J'){ 121 jx = i, jy = j; 122 } 123 if(mp[i][j] == 'F'){ 124 q.push_back(make_pair(i,j)); 125 } 126 } 127 } 128 int ret = bfs(); 129 if(ret > 0) 130 cout << ret << endl; 131 else 132 cout << "IMPOSSIBLE" << endl; 133 134 } 135 return 0; 136 }
NOW：
1 #include <iostream> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <map> 6 #include <vector> 7 #include <climits> 8 #include <queue> 9 using namespace std; 10 11 int n,m; 12 char mp[1005][1005]; 13 int dis[1005][1005]; 14 int fdis[1005][1005]; 15 bool vis[1005][1005]; 16 int px,py; 17 int fx[4][2] = {{1,0},{-1,0},{0,-1},{0,1}}; 18 struct node{ 19 int x,y; 20 }; 21 22 queue<node> q[2]; 23 24 bool pass1(int x,int y){ 25 if(x < 0 || y < 0 || x >= n || y >= m || mp[x][y] != '.' || dis[x][y]) 26 return false; 27 return true; 28 } 29 30 bool pass2(int x,int y){ 31 if(x < 0 || y < 0 || x >= n || y >= m || mp[x][y] == '#' || fdis[x][y]) 32 return false; 33 return true; 34 } 35 36 void bfs(){ 37 while(!q[0].empty()){ 38 node now = q[0].front(); 39 q[0].pop(); 40 for(int i = 0; i < 4; i++){ 41 int nx = now.x + fx[i][0]; 42 int ny = now.y + fx[i][1]; 43 if(pass1(nx,ny)){ 44 q[0].push(node{nx,ny}); 45 dis[nx][ny] = dis[now.x][now.y]+1; 46 } 47 } 48 } 49 50 while(!q[1].empty()){ 51 node now = q[1].front(); 52 q[1].pop(); 53 for(int i = 0; i < 4; i++){ 54 int nx = now.x + fx[i][0]; 55 int ny = now.y + fx[i][1]; 56 if(pass2(nx,ny)){ 57 q[1].push(node{nx,ny}); 58 fdis[nx][ny] = fdis[now.x][now.y]+1; 59 } 60 } 61 } 62 } 63 64 int check(){ 65 int ans = INT_MAX; 66 for(int j = 0; j < m; j++){ 67 if(dis[0][j] > 0 && (fdis[0][j] > dis[0][j] || fdis[0][j] == 0)) 68 ans = min(ans,dis[0][j]); 69 if(dis[n-1][j] > 0 && (fdis[n-1][j] > dis[n-1][j] || fdis[n-1][j] == 0)) 70 ans = min(ans,dis[n-1][j]); 71 } 72 for(int j = 0; j < n; j++){ 73 if(dis[j][0] > 0 && (fdis[j][0] > dis[j][0] || fdis[j][0] == 0)) 74 ans = min(ans,dis[j][0]); 75 if(dis[j][m-1] > 0 && (fdis[j][m-1] > dis[j][m-1] || fdis[j][m-1] == 0)) 76 ans = min(ans,dis[j][m-1]); 77 } 78 if(ans == INT_MAX) 79 return -1; 80 else 81 return ans; 82 } 83 84 void init(){ 85 while(!q[0].empty()) q[0].pop(); 86 while(!q[1].empty()) q[1].pop(); 87 memset(dis, 0, sizeof dis); 88 memset(fdis, 0, sizeof fdis); 89 return ; 90 } 91 92 int main(){ 93 int t; 94 cin>>t; 95 while(t--){ 96 init(); 97 cin>>n>>m; 98 for(int i = 0; i < n; i++){ 99 for(int j = 0; j < m; j++){ 100 cin>>mp[i][j]; 101 if(mp[i][j] == 'J') 102 q[0].push(node{i,j}),dis[i][j] = 1; 103 if(mp[i][j] == 'F') 104 q[1].push(node{i,j}),fdis[i][j] = 1; 105 } 106 } 107 bfs(); 108 int ret = check(); 109 if(ret == -1) 110 cout << "IMPOSSIBLE" << endl; 111 else 112 cout << ret << endl; 113 } 114 return 0; 115 }
J-迷宫问题
这个我以前写过一篇博客https://www.cnblogs.com/xenny/p/9473555.html
然后再贴一下现在的代码吧:
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <queue> 5 #include <stack> 6 #include <vector> 7 using namespace std; 8 9 char mp[5][5]; 10 bool vis[5][5]; 11 int fx[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; 12 vector< pair<int,int> > ans(1,make_pair(0,0)); 13 bool pass(int x,int y){ 14 if(x < 0 || y < 0 || x >= 5 || y >= 5 || vis[x][y] || mp[x][y] == '1') 15 return false; 16 return true; 17 } 18 19 void print(vector< pair<int,int> > v){ 20 for(vector< pair<int,int> >::iterator it = v.begin(); it != v.end(); it++){ 21 cout << '(' << it->first << ", " << it->second << ')' << endl; 22 } 23 } 24 25 void dfs(int x,int y,vector< pair<int,int> > v){ 26 if(x == 4 && y == 4){ 27 if(ans.size() == 1 || v.size() < ans.size()) 28 ans = v; 29 return ; 30 } 31 for(int i = 0; i < 4; i++){ 32 int nx = x + fx[i][0]; 33 int ny = y + fx[i][1]; 34 if(pass(nx,ny)){ 35 vis[nx][ny] = 1; 36 v.push_back(make_pair(nx,ny)); 37 dfs(nx,ny,v); 38 v.erase(--v.end()); 39 vis[nx][ny] = 0; 40 } 41 } 42 } 43 44 int main(){ 45 memset(vis, 0, sizeof vis); 46 vis[0][0] = 1; 47 for(int i = 0; i < 5; i++){ 48 for(int j = 0; j < 5; j++){ 49 cin>>mp[i][j]; 50 } 51 } 52 dfs(0,0,ans); 53 print(ans); 54 return 0; 55 }
感觉现在写的比以前的还是清晰明了了很多= =
K-Oil Deposits
很多人的搜索入门题都是这个题目吧，很经典，就是问有几块油田，一块油田的8个方向内有油田就看为连在一起。
把遍历过的油田记为*号，都可以把vis数组都省略掉。
代码如下：
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int n,m; 7 char mp[105][105]; 8 int fx[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; 9 10 bool pass(int x,int y){ 11 if(x < 0 || y < 0 || x >= n || y >= m || mp[x][y] == '*') 12 return false; 13 return true; 14 } 15 16 void dfs(int x,int y){ 17 for(int i = 0; i < 8; i++){ 18 int nx = x + fx[i][0]; 19 int ny = y + fx[i][1]; 20 if(pass(nx,ny)){ 21 mp[nx][ny] = '*'; 22 dfs(nx,ny); 23 } 24 } 25 } 26 27 int main(){ 28 while(cin>>n>>m && n){ 29 int sum = 0; 30 for(int i = 0; i < n; i++){ 31 for(int j = 0; j < m; j++){ 32 cin>>mp[i][j]; 33 } 34 } 35 for(int i = 0; i < n; i++){ 36 for(int j = 0; j < m; j++){ 37 if(mp[i][j] == '@'){ 38 sum++; 39 dfs(i,j); 40 } 41 } 42 } 43 cout << sum << endl; 44 } 45 return 0; 46 }
L-非常可乐
和Pots那个题类似，也是枚举每种状态，但是其实在搜索还可以加上剪枝，例如s为奇数直接输出NO，然后本题还有数学做法，可以自行百度，我不再给出。
代码如下：
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 7 int s,n,m; 8 bool vis[105][105][105]; 9 struct node{ 10 int s,n,m,t; 11 }; 12 13 bool check(node n){ 14 if((n.s > 0 && n.n > 0 && n.s == n.n && n.s + n.n == s) || \ 15 (n.s > 0 && n.m > 0 && n.s == n.m && n.s + n.m == s) || \ 16 (n.m > 0 && n.n > 0 && n.m == n.n && n.m + n.n == s)) 17 return true; 18 return false; 19 } 20 21 int bfs(){ 22 memset(vis, 0, sizeof vis); 23 queue<node> q; 24 q.push(node{s,0,0,0}); 25 vis[s][0][0] = 0; 26 while(!q.empty()){ 27 node now = q.front(); 28 q.pop(); 29 if(check(now)){ 30 return now.t; 31 } 32 node nt = now; 33 nt.s = now.s - (n-now.n) <= 0 ? 0 : now.s - (n-now.n); 34 nt.n = now.n + now.s >= n ? n : now.n + now.s; 35 if(!vis[nt.s][nt.n][nt.m]){ 36 vis[nt.s][nt.n][nt.m] = 1; 37 nt.t = now.t+1; 38 q.push(nt); 39 } 40 nt = now; 41 nt.s = now.s - (m-now.m) <= 0 ? 0 : now.s - (m-now.m); 42 nt.m = now.m + now.s >= m ? m : now.m + now.s; 43 if(!vis[nt.s][nt.n][nt.m]){ 44 vis[nt.s][nt.n][nt.m] = 1; 45 nt.t = now.t+1; 46 q.push(nt); 47 } 48 nt = now; 49 nt.n = now.n - (s-now.s) <= 0 ? 0 : now.n - (s-now.s); 50 nt.s = now.n + now.s >= s ? s : now.n + now.s; 51 if(!vis[nt.s][nt.n][nt.m]){ 52 vis[nt.s][nt.n][nt.m] = 1; 53 nt.t = now.t+1; 54 q.push(nt); 55 } 56 nt = now; 57 nt.m = now.m - (s-now.s) <= 0 ? 0 : now.m - (s-now.s); 58 nt.s = now.m + now.s >= s ? s : now.m + now.s; 59 if(!vis[nt.s][nt.n][nt.m]){ 60 vis[nt.s][nt.n][nt.m] = 1; 61 nt.t = now.t+1; 62 q.push(nt); 63 } 64 nt = now; 65 nt.n = now.n - (m-now.m) <= 0 ? 0 : now.n - (m-now.m); 66 nt.m = now.m + now.n >= m ? m : now.m + now.n; 67 if(!vis[nt.s][nt.n][nt.m]){ 68 vis[nt.s][nt.n][nt.m] = 1; 69 nt.t = now.t+1; 70 q.push(nt); 71 } 72 nt = now; 73 nt.m = now.m - (n-now.n) <= 0 ? 0 : now.m - (n-now.n); 74 nt.n = now.n + now.m >= n ? n : now.m + now.n; 75 if(!vis[nt.s][nt.n][nt.m]){ 76 vis[nt.s][nt.n][nt.m] = 1; 77 nt.t = now.t+1; 78 q.push(nt); 79 } 80 } 81 return -1; 82 } 83 84 int main(){ 85 while(cin>>s>>n>>m && s){ 86 int ret = bfs(); 87 if(ret == -1) 88 cout << "NO" << endl; 89 else 90 cout << ret << endl; 91 } 92 return 0; 93 }
M-Find a way
这个题我也写过博客，还是我的第一篇题解博客。
地址链接：https://www.cnblogs.com/xenny/p/9361825.html
然后这是现在写的代码：
1 #include <iostream> 2 #include <queue> 3 #include <vector> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 char mp[205][205]; 9 int vis[205][205][2]; 10 int fx[4][2] = {0,1,0,-1,-1,0,1,0}; 11 int n,m,yx,yy,mx,my; 12 struct node{ 13 int x,y; 14 }; 15 16 const int inf = 123456789; 17 18 bool check(int x,int y,int z){ 19 if(vis[x][y][z] != inf || x < 0 || x >= n || y < 0 || y >= m || mp[x][y] == '#') 20 return false; 21 return true; 22 } 23 24 void bfs(int x,int y,int z){ 25 vis[x][y][z] = 0; 26 queue<node>q; 27 q.push(node{x,y}); 28 while(!q.empty()){ 29 node now = q.front(); 30 q.pop(); 31 for(int i = 0; i < 4; i++){ 32 int nx = now.x + fx[i][0]; 33 int ny = now.y + fx[i][1]; 34 if(check(nx,ny,z)){ 35 vis[nx][ny][z] = vis[now.x][now.y][z] + 1; 36 q.push(node{nx,ny}); 37 } 38 } 39 } 40 } 41 42 int main(){ 43 while(cin>>n>>m){ 44 fill(vis[0][0], vis[0][0]+205*205*2, inf); 45 vector< pair<int,int> > v; 46 for(int i = 0; i < n; i++){ 47 for(int j = 0; j < m; j++){ 48 cin>>mp[i][j]; 49 if(mp[i][j] == 'Y') 50 yx = i,yy = j; 51 if(mp[i][j] == 'M') 52 mx = i,my = j; 53 if(mp[i][j] == '@') 54 v.push_back(make_pair(i,j)); 55 } 56 } 57 bfs(yx,yy,0); 58 bfs(mx,my,1); 59 int ans = INT_MAX; 60 for(vector< pair<int,int> >::iterator it = v.begin(); it != v.end(); it++) 61 ans = min(ans,vis[it->first][it->second][0] + vis[it->first][it->second][1]); 62 cout << ans*11 << endl; 63 } 64 65 return 0; 66 }
看了以前的博客和现在的，区别还是挺大的，各位也可以尝试用多种方法解决一道题。关于kuangbin专题一的所有题目到此就完了，又不懂的地方可以在评论区留言，同时欢迎指正上面代码的错误。
