又重头开始刷kuangbin，有些题用了和以前不一样的思路解决。全部题解如下
点击每道题的标题即可跳转至VJ题目页面。
棋子不能摆在相同行和相同列，所以我们可以依此枚举每一行，然后标记每一列是否走过，在此基础上进行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 }
题意就是给你一个三维的迷宫，从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 }
题意就是你现在在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 }
玩过关灯游戏理解这个题就很简单，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 }
题意就是给你一个数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 }
题意就是给你两个数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 }
给你两个字符串长度都为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 }
题意：有两个壶，容量分别为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 }
题意就是人在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 }
这个我以前写过一篇博客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 }
感觉现在写的比以前的还是清晰明了了很多= =
很多人的搜索入门题都是这个题目吧，很经典，就是问有几块油田，一块油田的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 }
和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 }
这个题我也写过博客，还是我的第一篇题解博客。
地址链接：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专题一的所有题目到此就完了，又不懂的地方可以在评论区留言，同时欢迎指正上面代码的错误。
DEFAULT keyword in ABAP and Optional Class in Java
