php网站开发说明文档,上海网站建设yes404,wordpress 找不到文章,开通网站需要多少钱本篇博文是笔者归纳汇总的AcWing基础课题集#xff0c;方便读者后期复盘巩固~
PS#xff1a;本篇文章只给出完整的算法实现#xff0c;并没有讲解具体的算法思路。如果想看算法思路#xff0c;可以阅读笔者往期写过的文章#xff08;或许会有#xff09;#xff0c;也可…本篇博文是笔者归纳汇总的AcWing基础课题集方便读者后期复盘巩固~
PS本篇文章只给出完整的算法实现并没有讲解具体的算法思路。如果想看算法思路可以阅读笔者往期写过的文章或许会有也可以移步AcWing官网看详情。
本篇文章的特点每道题会给出多种解法不局限于一种思路可以帮助读者从不同角度思考题目。算法代码简洁适合背诵记忆~~
Flood Fill
AcWing1097. 池塘计数
传送门
// 写法1BFS
#include bits/stdc.h
using namespace std;
const int N 1010;
using PII pairint, int;
#define x first
#define y second
int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};
char g[N][N];
bool st[N][N];
PII q[N * N];
int n, m;void bfs(int sx, int sy) {int hh 0, tt 0;q[0] {sx, sy};st[sx][sy] true;while (hh tt) {PII t q[hh ];for (int i 0; i 8; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b m || g[a][b] . || st[a][b]) continue;q[ tt] {a, b};st[a][b] true;}}
}int main()
{cin n m;for (int i 0; i n; i)for (int j 0; j m; j)cin g[i][j];int ans 0;for (int i 0; i n; i) {for (int j 0; j m; j) {if (g[i][j] W !st[i][j]) {bfs(i, j); ans;}}}printf(%d\n, ans);return 0;
}// 写法2DFS
#include bits/stdc.h
using namespace std;
const int N 1010;
int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};
char g[N][N];
int n, m;void dfs(int x, int y) {char t g[x][y];g[x][y] .;for (int i 0; i 8; i) {int a x dx[i], b y dy[i];if (a 0 || a n || b 0 || b m || g[a][b] .) continue;dfs(a, b);}t g[x][y]; // 这题貌似不需要恢复现场
}int main()
{cin n m;for (int i 0; i n; i)for (int j 0; j m; j)cin g[i][j];int ans 0;for (int i 0; i n; i) {for (int j 0; j m; j) {if (g[i][j] W) {dfs(i, j); ans;}}}printf(%d\n, ans);return 0;
}AcWing1098. 城堡问题
传送门
#include bits/stdc.h
using namespace std;
const int N 55;
#define x first
#define y second
using PII pairint, int;
int dx[4] {0, -1, 0, 1}, dy[4] {-1, 0, 1, 0}; // 西、北、东、南
int g[N][N], n, m;
bool st[N][N];
PII q[N * N];int bfs(int sx, int sy) {int hh 0, tt 0, area 0;q[0] { sx,sy };st[sx][sy] true;while (hh tt) {PII t q[hh ];for (int i 0; i 4; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b m || st[a][b]) continue;// 取出某个数的第i个二进制位然后与上1如果结果为1则表示有墙如果为0则表示没有墙// 比如11128它的二进制是1011第0位为1表示有西墙 第1位为1表示有北墙// 第2位为0表示没有东墙第3位为1表示有南墙if (g[t.x][t.y] i 1) continue;q[ tt] {a, b};st[a][b] true;} area;}return area;
}int main()
{scanf(%d%d, n, m);for (int i 0; i n; i)for (int j 0; j m; j)scanf(%d, g[i][j]);int cnt 0, area 0;for (int i 0; i n; i) {for (int j 0; j m; j) {if (!st[i][j]) {area max(area, bfs(i, j)); cnt;}}}printf(%d\n%d\n, cnt, area);return 0;
}AcWing1106. 山峰和山谷
传送门
#include bits/stdc.h
using namespace std;
const int N 1010;
#define x first
#define y second
using PII pairint, int;
int dx[8] {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] {-1, 0, 1, -1, 1, -1, 0, 1};
int h[N][N], n;
// has_higher是用来标记有没有比“当前(i,j)这个点所在的山脉”更高的山脉
// has_lower是用来标记有没有比“当前(i,j)这个点所在的山脉更低的山脉
bool st[N][N], has_higher, has_lower;
PII q[N * N];void bfs(int sx, int sy) {int hh 0, tt 0;q[0] {sx, sy};st[sx][sy] true;while (hh tt) {PII t q[hh ];for (int i 0; i 8; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b n) continue;if (h[a][b] ! h[t.x][t.y]) {h[a][b] h[t.x][t.y] ? has_higher true : has_lower true;} else {if (!st[a][b]) {q[ tt] {a, b};st[a][b] true;}}}}
}int main()
{scanf(%d, n);for (int i 0; i n; i)for (int j 0; j n; j)scanf(%d, h[i][j]);int peak 0, valley 0;for (int i 0; i n; i) {for (int j 0; j n; j) {if (!st[i][j]) {has_higher has_lower false;bfs(i, j);if (!has_higher) peak;if (!has_lower) valley;}}}printf(%d %d\n, peak, valley);return 0;
}最短路模型
AcWing1076. 迷宫问题
传送门
// 逆向搜索
#include bits/stdc.h
using namespace std;
const int N 1010;
#define x first
#define y second
using PII pairint, int;
int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};
PII pre[N][N], q[N * N];
int g[N][N], n;
bool st[N][N];void bfs(int sx, int sy) {int hh 0, tt 0;q[0] {sx, sy};st[sx][sy] true;while (hh tt) {PII t q[hh ];for (int i 0; i 4; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b n || g[a][b] || st[a][b]) continue;q[ tt] {a, b};st[a][b] true;pre[a][b] t;}}
}int main()
{scanf(%d, n);for (int i 0; i n; i)for (int j 0; j n; j)scanf(%d, g[i][j]);bfs(n - 1, n - 1); // 逆向搜索即从终点搜索到起点PII p(0, 0);while (1) { // 正向打印“逆向搜索得到的路径” 从起点打印到终点printf(%d %d\n, p.x, p.y);if (p.x n - 1 p.y n - 1) break;p pre[p.x][p.y];}return 0;
}// 正向搜索
#include bits/stdc.h
using namespace std;
const int N 1010;
#define x first
#define y second
using PII pairint, int;
int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};
PII pre[N][N], q[N * N];
int g[N][N], n;
bool st[N][N];void bfs(int sx, int sy) {int hh 0, tt 0;q[0] {sx, sy};st[sx][sy] true;while (hh tt) {PII t q[hh ];for (int i 0; i 4; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b n || g[a][b] || st[a][b]) continue;q[ tt] {a, b};st[a][b] true;pre[a][b] t;}}
}void show(int a, int b) { // 类似于后序遍历// if (a || b) show(pre[a][b].x, pre[a][b].y);// printf(%d %d\n, a, b);// 等价于if (!a !b) {puts(0 0);return ;}show(pre[a][b].x, pre[a][b].y);printf(%d %d\n, a, b);
}int main()
{scanf(%d, n);for (int i 0; i n; i)for (int j 0; j n; j)scanf(%d, g[i][j]);bfs(0, 0); // 正向搜索show(n - 1, n - 1); // 类似于后序遍历return 0;
}AcWing188. 武士风度的牛
传送门
// 写法1使用st[]判重数组
#include bits/stdc.h
using namespace std;
const int N 155;
#define x first
#define y second
using PII pairint, int;
int dx[8] {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] {1, 2, 2, 1, -1, -2, -2, -1};
int dist[N][N], n, m;
char g[N][N];
bool st[N][N];
PII q[N * N];int bfs(int sx, int sy) {memset(dist, -1, sizeof dist);int hh 0, tt 0;q[0] {sx, sy};st[sx][sy] true;dist[sx][sy] 0;while (hh tt) {PII t q[hh ];// if (g[a][b] H) return dist[t.x][t.y]; // 也可以在这里直接判断结果哦for (int i 0; i 8; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b m || st[a][b] || g[a][b] *) continue;if (g[a][b] H) return dist[t.x][t.y] 1;dist[a][b] dist[t.x][t.y] 1;q[ tt] {a, b};st[a][b] true;}}return -1;
}int main()
{int sx, sy;scanf(%d%d, m, n);for (int i 0; i n; i) {for (int j 0; j m; j) {cin g[i][j];if (g[i][j] K) sx i, sy j; }}printf(%d\n, bfs(sx, sy));return 0;
}// 写法2如果dist[i]-1则表示没有遍历过可以用来代替st[]判重数组
#include bits/stdc.h
using namespace std;
const int N 155;
#define x first
#define y second
using PII pairint, int;
int dx[8] {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] {1, 2, 2, 1, -1, -2, -2, -1};
int dist[N][N], n, m;
char g[N][N];
PII q[N * N];int bfs(int sx, int sy) {memset(dist, -1, sizeof dist);int hh 0, tt 0;q[0] {sx, sy};dist[sx][sy] 0;while (hh tt) {PII t q[hh ];for (int i 0; i 8; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b m || ~dist[a][b] || g[a][b] *) continue;if (g[a][b] H) return dist[t.x][t.y] 1;dist[a][b] dist[t.x][t.y] 1;q[ tt] {a, b};}}return -1;
}int main()
{int sx, sy;scanf(%d%d, m, n);for (int i 0; i n; i) {for (int j 0; j m; j) {cin g[i][j];if (g[i][j] K) sx i, sy j; }}printf(%d\n, bfs(sx, sy));return 0;
}AcWing1100. 抓住那头牛
传送门
// 写法1使用st[]判重数组
#include bits/stdc.h
using namespace std;
const int N 1e5 10;
int dist[N], q[N], n, k;
bool st[N];int bfs() {memset(dist, -1, sizeof dist);int hh 0, tt 0;q[0] n, dist[n] 0;st[n] true;while (hh tt) {int u q[hh ];if (u k) return dist[u];if (u - 1 0 !st[u - 1]) {dist[u - 1] dist[u] 1;q[ tt] u - 1;st[u - 1] true;}if (u 1 N !st[u 1]) {dist[u 1] dist[u] 1;q[ tt] u 1;st[u 1] true; }if (u * 2 N !st[2 * u]) {dist[2 * u] dist[u] 1;q[ tt] 2 * u;st[2 * u] true;}}return -1;
}int main()
{scanf(%d%d, n, k);printf(%d\n, bfs());return 0;
}// 写法2如果dist[i]-1则表示没有遍历过可以用来代替st[]判重数组
#include bits/stdc.h
using namespace std;
const int N 1e5 10;
int dist[N], q[N], n, k;int bfs() {memset(dist, -1, sizeof dist);int hh 0, tt 0;q[0] n, dist[n] 0;while (hh tt) {int u q[hh ];if (u k) return dist[u];if (u - 1 0 dist[u - 1] -1) {dist[u - 1] dist[u] 1;q[ tt] u - 1;}if (u 1 N dist[u 1] -1) {dist[u 1] dist[u] 1;q[ tt] u 1;}if (u * 2 N dist[2 * u] -1) {dist[2 * u] dist[u] 1;q[ tt] 2 * u;}}return -1;
}int main()
{scanf(%d%d, n, k);printf(%d\n, bfs());return 0;
}多源BFS
AcWing173 矩阵距离
传送门
#include bits/stdc.h
using namespace std;
const int N 1010;
#define x first
#define y second
using PII pairint, int;
int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};
int dist[N][N], n, m;
char g[N][N];
PII q[N * N];void bfs() {memset(dist, -1, sizeof dist);int hh 0, tt -1; // 注意tt初始化为-1而不是0哦// 把所有字符1都放进队列中并且设定距离为0 其实就等价于// 从虚拟源点向这些起点连一条距离为0的边 但是我们并没有真的把虚拟源点建立出来for (int i 0; i n; i) {for (int j 0; j m; j) {if (g[i][j] 1) {dist[i][j] 0; // 距离为0相当于 从虚拟源点向这些起点连一条距离为0的边q[ tt] {i, j}; // 将所有起点加入队列中}}}while (hh tt) {PII t q[hh ];for (int i 0; i 4; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b m || ~dist[a][b]) continue;dist[a][b] dist[t.x][t.y] 1;q[ tt] {a, b};}}
}int main()
{cin n m;for (int i 0; i n; i)for (int j 0; j m; j)cin g[i][j];bfs();for (int i 0; i n; i) {for (int j 0; j m; j) printf(%d , dist[i][j]);puts();}return 0;
}最小步数模型
AcWing1107. 魔板
传送门
#include bits/stdc.h
#define x first
#define y second
using namespace std;
string op[3] {87654321, 41236785, 17245368}; // 题意中这三种操作所对应的状态
// 外层的string表示当前状态
// pair中的char表示当前状态是由上一个状态经过哪种操作变换过来的, string表示上一个状态
unordered_mapstring, pairchar, string pre;
// string表示当前状态的字符串 int表示到达当前状态所用的最短步骤数
unordered_mapstring, int dist;string move(string s, int i) { // 对状态s执行第i种操作string ans;// 类似于BFS中偏移数组dx,dy的那种思想for (int j 0; j 8; j) ans s[op[i][j] - 1];return ans;
}int bfs(string S, string T) {if (S T) return 0;queuestring q;q.push(S);dist[S] 0;while (q.size()) {string u q.front(); q.pop();for (int i 0; i 3; i) { // 枚举这三种操作string v move(u, i);if (!dist.count(v)) {dist[v] dist[u] 1;pre[v] {A i, u};q.push(v);if (v T) return dist[v];}}}return -1;
}int main()
{string S 12345678, T;for (int i 0, x; i 8; i) {cin x;T x 0;}int step bfs(S, T);printf(%d\n, step);string ans;while (S ! T) {ans pre[T].x;T pre[T].y;}reverse(ans.begin(), ans.end());if (step 0) cout ans endl;return 0;
}双端队列广搜
双端队列广搜又称为01BFS。
AcWing175. 电路维修
传送门
// 写法1使用st判重数组
#include bits/stdc.h
using namespace std;
const int N 510;
using PII pairint, int;
#define x first
#define y second
// 某个点的左上、右上、右下、左下 四个方向的偏移量 注意哦dx dy ix iy cs都是顺时针方向即左上、右上、右下、左下
// 它们一定是要一一对应的不能写错不然for (int i 0; i 4; i)枚举的时候所得到的dx,dy,ix,iy,cs都不是对应的就会出错
int dx[4] {-1, -1, 1, 1}, dy[4] {-1, 1, 1, -1};
int ix[4] {-1, -1, 0, 0}, iy[4] {-1, 0, 0, -1};
// 这里是定义四宫格中的电线所应该的标准的形式即左上为\右上为/右下为\,左下为/
// 这样定义就可以让左上和右下直接相连右上和左下直接相连不用旋转所以不需要花费代价
char cs[5] \\/\\/;
int dist[N][N], n, m, T;
bool st[N][N];
char g[N][N];int bfs() {memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dequePII q;q.push_back({0, 0});dist[0][0] 0;while (q.size()) {PII t q.front(); q.pop_front();if (t.x n t.y m) return dist[n][m];if (st[t.x][t.y]) continue; // 扩展过了就直接跳过// 所有边的权重不同所以某些点可能需要被扩展多次即某个点可能多次入队// 这道题目可以看成是特殊的dijkstra算法在dijkstra算法中某些点可能会被多次扩展// 但第一次从优先队列中弹出的节点的距离一定就是最小值了所以需要在出队的时候来判重st[t.x][t.y] true;for (int i 0; i 4; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b m) continue;int u t.x ix[i], v t.y iy[i], w (g[u][v] ! cs[i]);if (dist[a][b] dist[t.x][t.y] w) {dist[a][b] dist[t.x][t.y] w;// w为0则插入到队头w为1则插入到队尾w 0 ? q.push_front({a, b}) : q.push_back({a, b});}}}return -1;
}int main()
{scanf(%d, T);while (T -- ) {scanf(%d%d, n, m);for (int i 0; i n; i) scanf(%s, g[i]);// n m为奇数则无解if ((n m) 1) puts(NO SOLUTION);else printf(%d\n, bfs());}return 0;
}// 写法2不使用st判重数组而且不需要说使用dist数组来替代st判重数组的含义就可以完全直接省略st判重数组
/*这题只是有点特殊这种做法并不适用于其他情况大多数题目都需要st判重数组而且可以使用dist数组来替代st判重数组的含义
只是对于01BFS的题目来说可以这么写完全省略st判重数组哦。
为什么01BFS可以直接省略st判重数组呢
原因其实01BFS使用了双端队列 (deque) 并结合了 Dijkstra 的思想对于每个节点只有当我们找到了一条到达该节点的更短路径时我们才会将其放入队列中。
通过检查dist数组我们实际上已经隐式地跟踪了这些信息如果我们找到的新路径没有比当前记录在dist中的路径更短
那么我们就可以忽略这个新路径就像我们已经访问过这个节点一样。注意这里并不是说通过判断dist ! INF来表达某个点是否已经访问过了
而是通过比较dist大小更新路径的方式来隐式表达某个点是否已经访问过了。
但是请注意去掉st判重数组可能会增加算法的运行时间尤其是在那些存在许多冗余路径的图中。
这是一个具体的例子这种方法可能并不适用于所有的 BFS 实现。
*/#include bits/stdc.h
using namespace std;
const int N 510;
using PII pairint, int;
#define x first
#define y second
int dx[4] {-1, -1, 1, 1}, dy[4] {-1, 1, 1, -1};
int ix[4] {-1, -1, 0, 0}, iy[4] {-1, 0, 0, -1};
char cs[5] \\/\\/;
int dist[N][N], n, m, T;
char g[N][N];int bfs() {memset(dist, 0x3f, sizeof dist);dequePII q;q.push_back({0, 0});dist[0][0] 0;while (q.size()) {PII t q.front(); q.pop_front();if (t.x n t.y m) return dist[n][m];for (int i 0; i 4; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b m) continue;int u t.x ix[i], v t.y iy[i], w (g[u][v] ! cs[i]);if (dist[a][b] dist[t.x][t.y] w) {dist[a][b] dist[t.x][t.y] w;w 0 ? q.push_front({a, b}) : q.push_back({a, b});}}}return -1;
}int main()
{scanf(%d, T);while (T -- ) {scanf(%d%d, n, m);for (int i 0; i n; i) scanf(%s, g[i]);if ((n m) 1) puts(NO SOLUTION);else printf(%d\n, bfs());}return 0;
}双向广搜
AcWing190. 字串变换
传送门
#include bits/stdc.h
using namespace std;
const int N 6;
string a[N], b[N], A, B;
int n;int extend(queuestring q, unordered_mapstring, int da, unordered_mapstring, int db, string a[], string b[]) {int d da[q.front()]; // 按层扩展而不是按点扩展 把同一层中的所有元素都扩展完while (!q.empty() da[q.front()] d) {string u q.front(); q.pop();for (int i 0; i n; i) {for (int j 0; j u.size(); j) {if (u.substr(j, a[i].size()) a[i]) {string v u.substr(0, j) b[i] u.substr(j a[i].size());// 如果当前v这个字符串的状态在qa中已经被遍历过了,则跳过if (da.count(v)) continue;// 如果当前从起点开始搜索的v这个字符串的状态已经被从终点开始搜索的遍历过了//这说明v这个字符串就是从起点开始搜索和从终点开始搜索的相遇点//类似于打隧道B已经打通了v此时只要A打破v那么就把隧道都打通了if (db.count(v)) return da[u] 1 db[v];da[v] da[u] 1;q.push(v);}}}}return 11;
}int bfs() {if (A B) return 0;// 队列qa来存储从起点拓展的状态,队列qb存储从终点拓展的状态queuestring qa, qb;// da表示从起点拓展到某一层用了多少步数 db表示从终点拓展到某一层用了多少步数unordered_mapstring, int da, db;qa.push(A), qb.push(B);da[A] db[B] 0;int step 0;// 如果出现某个队列为空说明这这两个队列没有交集这个图不是连通的// 就跟打隧道一样隧道为100米A打通了40米就为停了B打通了50米就为停了那么还有10米所以不可能打通while (!qa.empty() !qb.empty()) {int t;// 这里有个优化就是要优先考虑队列中状态个数少的if (qa.size() qb.size()) t extend(qa, da, db, a, b);else t extend(qb, db, da, b, a);if (t 10) return t;// step从0~9共10步因此只要此时step10则说明走了11步不能在10步以内完成if ( step 10) return -1;}return -1;
}int main()
{cin A B;// 因为这里并没有明确告诉转换规则由多少个所以需要根据输入的转换字符串来确定转换规则的个数while (cin a[n] b[n]) n;int t bfs();if (t -1) puts(NO ANSWER!);else printf(%d\n, t);return 0;
}A*
AcWing178. 第K短路
传送门
#include bits/stdc.h
using namespace std;
const int N 1010, M 2e5 10;
#define x first
#define y second
using PII pairint, int;
// 外层第一个int是f、pair中的第一个int是dw[i](即gdw[i]), 第二个int是点的编号
using PIII pairint, pairint, int;
int h[N], hs[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N], n, m, S, T, K;
bool st[N];void add(int h[], int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}void dijkstra() { // 求出从终点T到其他各点的最短距离作为h()函数memset(dist, 0x3f, sizeof dist);dist[T] 0;priority_queuePII, vectorPII, greaterPII q;q.push({0, T});while (q.size()) {PII t q.top(); q.pop();int u t.y;if (st[u]) continue;st[u] true;for (int i hs[u]; ~i; i ne[i]) {int v e[i];if (dist[v] dist[u] w[i]) {dist[v] dist[u] w[i];q.push({dist[v], v});}}}
}int A_star() {priority_queuePIII, vectorPIII, greaterPIII q;q.push({dist[S], {0, S}});while (q.size()) {PIII t q.top(); q.pop();int u t.y.y, d t.y.x; cnt[u];if (cnt[T] K) return d;for (int i h[u]; ~i; i ne[i]) {int v e[i];if (cnt[v] K) {// f() g() h(), 这里把g() d w[i], h() dist[v]int f d w[i] dist[v]; // 求出估价函数f()q.push({f, {d w[i], v}});}}}return -1;
}int main()
{memset(h, -1, sizeof h), memset(hs, -1, sizeof hs);scanf(%d%d, n, m);while (m -- ) {int a, b, c;scanf(%d%d%d, a, b, c);add(h, a, b, c), add(hs, b, a, c);}scanf(%d%d%d, S, T, K);// 由于题目要求每条最短路中至少要包含一条边if (S T) K;dijkstra();printf(%d\n, A_star());return 0;
}AcWing179 八数码
传送门
#include bits/stdc.h
using namespace std;
using PIS pairint, string;
int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};
char op[4] {u, r, d, l};
unordered_mapstring, int dist;
unordered_mapstring, pairstring, char pre;
string S, T 12345678x;int get(string s) {int ans 0;for (int i 0; i s.size(); i) {if (s[i] ! x) {int t s[i] - 1;ans abs(i / 3 - t / 3) abs(i % 3 - t % 3);}}return ans;
}void bfs() {priority_queuePIS, vectorPIS, greaterPIS q;q.push({get(S), S});dist[S] 0;while (q.size()) {auto t q.top(); q.pop();string s t.second;if (s T) break;int d dist[s], x, y;for (int i 0; i s.size(); i ) {if (s[i] x) {x i / 3, y i % 3;break;}}string str s;for (int i 0; i 4; i) {int a x dx[i], b y dy[i];if (a 0 a 3 b 0 b 3) {swap(s[x * 3 y], s[a * 3 b]);if (!dist.count(s) || dist[s] d 1) {dist[s] d 1;pre[s] {str, op[i]};q.push({dist[s] get(s), s});}swap(s[x * 3 y], s[a * 3 b]);}}}
}int main()
{string c, seq;while (cin c) {S c;if (c ! x) seq c;}int cnt 0;for (int i 0; i seq.size(); i)for (int j i 1; j seq.size(); j)if (seq[i] seq[j]) cnt;if (cnt 1) puts(unsolvable);else {bfs();string ans;while (S ! T) {ans pre[T].second;T pre[T].first;}reverse(ans.begin(), ans.end());cout ans endl;}return 0;
}DFS之连通性模型
AcWing1112. 迷宫
传送门
// DFS
#include bits/stdc.h
using namespace std;
const int N 110;
int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};
char g[N][N];
bool st[N][N];
int n, T, sx, sy, ex, ey;bool dfs(int x, int y) {if (g[x][y] #) return false;if (x ex y ey) return true;st[x][y] true;for (int i 0; i 4; i) {int a x dx[i], b y dy[i];if (a 0 || a n || b 0 || b n || st[a][b]) continue;if (dfs(a, b)) return true;}return false;
}int main()
{scanf(%d, T);while (T -- ) {memset(st, 0, sizeof st);scanf(%d, n);for (int i 0; i n; i) scanf(%s, g[i]);scanf(%d%d%d%d, sx, sy, ex, ey);if (g[sx][sy] # || g[ex][ey] #) {puts(NO);continue;}puts(dfs(sx, sy) ? YES : NO);}return 0;
}// BFS
#include bits/stdc.h
using namespace std;
const int N 110;
#define x first
#define y second
using PII pairint, int;
int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};
char g[N][N];
bool st[N][N];
PII q[N * N];
int n, T, sx, sy, ex, ey;bool bfs() {memset(st, 0, sizeof st);int hh 0, tt 0;q[0] {sx, sy};st[sx][sy] true;while (hh tt) {PII t q[hh ];if (t.x ex t.y ey) return true;for (int i 0; i 4; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b n || g[a][b] # || st[a][b]) continue;q[ tt] {a, b};st[a][b] true;}}return false;
}int main()
{scanf(%d, T);while (T -- ) {scanf(%d, n);for (int i 0; i n; i) scanf(%s, g[i]);scanf(%d%d%d%d, sx, sy, ex, ey);if (g[sx][sy] # || g[ex][ey] #) {puts(NO);continue;}puts(bfs() ? YES : NO);}return 0;
}AcWing1113. 红与黑
传送门
// DFS
#include bits/stdc.h
using namespace std;
const int N 25;
int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};
char g[N][N];
bool st[N][N];
int n, m;int dfs(int x, int y) {int cnt 1;st[x][y] true;for (int i 0; i 4; i) {int a x dx[i], b y dy[i];if (a 0 || a n || b 0 || b m || st[a][b] || g[a][b] ! .) continue;cnt dfs(a, b);}return cnt;
}int main()
{while (~scanf(%d%d, m, n), m || n) {memset(st, 0, sizeof st);for (int i 0; i n; i) scanf(%s, g[i]);int sx, sy;for (int i 0; i n; i) {for (int j 0; j m; j) {if (g[i][j] ) {sx i, sy j;break;}}}printf(%d\n, dfs(sx, sy));}return 0;
}// BFS
#include bits/stdc.h
using namespace std;
const int N 25;
#define x first
#define y second
using PII pairint, int;
int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};
char g[N][N];
bool st[N][N];
PII q[N * N];
int n, m;int bfs(int sx, int sy) {int hh 0, tt 0, cnt 1;q[0] {sx, sy};st[sx][sy] true;while (hh tt) {PII t q[hh ];for (int i 0; i 4; i) {int a t.x dx[i], b t.y dy[i];if (a 0 || a n || b 0 || b m || st[a][b] || g[a][b] ! .) continue; cnt;q[ tt] {a, b};st[a][b] true;}}return cnt;
}int main()
{while (~scanf(%d%d, m, n), m || n) {memset(st, 0, sizeof st);for (int i 0; i n; i) scanf(%s, g[i]);int sx, sy;for (int i 0; i n; i) {for (int j 0; j m; j) {if (g[i][j] ) {sx i, sy j;break;}}}printf(%d\n, bfs(sx, sy));}return 0;
}DFS之搜索顺序
AcWing1116. 马走日
传送门
#include bits/stdc.h
using namespace std;
const int N 10;
int dx[8] {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] {1, 2, 2, 1, -1, -2, -2, -1};
bool st[N][N];
int n, m, sx, sy, ans, T;void dfs(int x, int y, int cnt) {if (cnt n * m) { ans;return ;}st[x][y] true;for (int i 0; i 8; i) {int a x dx[i], b y dy[i];if (a 0 || a n || b 0 || b m || st[a][b]) continue;dfs(a, b, cnt 1);}st[x][y] false;
}int main()
{scanf(%d, T);while (T -- ) {ans 0;memset(st, 0, sizeof st);scanf(%d%d%d%d, n, m, sx, sy);dfs(sx, sy, 1);printf(%d\n, ans);}return 0;
}AcWing1117 单词接龙
传送门
#include bits/stdc.h
using namespace std;
const int N 25;
int g[N][N], used[N], ans, n;
string words[N];void dfs(string dragon, int last) {ans max(ans, (int)dragon.size()); used[last];for (int i 0; i n; i) if (g[last][i] 0 used[i] 2) dfs(dragon words[i].substr(g[last][i]), i);-- used[last];
}int main()
{scanf(%d, n);for (int i 0; i n; i) cin words[i];char c;cin c;for (int i 0; i n; i) {for (int j 0; j n; j) {string a words[i], b words[j];int lenA a.size(), lenB b.size();for (int k 1; k min(lenA, lenB); k) {if (a.substr(lenA - k, k) b.substr(0, k)) {g[i][j] k;break;}}}}for (int i 0; i n; i)if (words[i][0] c)dfs(words[i], i);printf(%d\n, ans);return 0;
}AcWing1118. 分成互质组
传送门
#include bits/stdc.h
using namespace std;
const int N 12;
// group数组其实它存储的是原序列中某个数的下标
// group[i][j]pos表示第i组中下标为j的那个数的位置,它在原序列中的下标是pos
int group[N][N],p[N], n, ans N;
// 判断原序列中的某个数是否已经被分好组了
bool st[N];inline int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}// check一下p[i]这个数是否与gp这个组内的数数互质
bool check(int gp[], int gc, int i) {for (int j 0; j gc; j)if (gcd(p[gp[j]], p[i]) ! 1)return false;return true;
}// 参数g表示第g组,gc表示第g组内的当前枚举到的下标,tc表示到目前为止所有组中一共有多少个元素了
// start表示从原序列的哪个下标开始枚举
void dfs(int g, int gc, int tc, int start) {if (g ans) return ;if (tc n) {ans g;return ;}bool ok true; // 判断是否需要新开一个组初始时true表示需要新开一个组for (int i start; i n; i) {// 如果下标i所对应的原序列中的那个数还没有被分好组并且当我们想要把这个数放入第g组时// 并且它与第g中的所有数字互质if (!st[i] check(group[g], gc, i)) {st[i] true; // 下标i所对应的原序列中的那个数已经被分好组了// 第g组中下标gc所指向的东西是原序列中刚加入这个组的那个数的下标group[g][gc] i;dfs(g, gc 1, tc 1, i 1);// 恢复现场st[i] false;ok false;}}// 表示需要新开一个组if (ok) dfs(g 1, 0, tc, 0);
}int main()
{scanf(%d, n);for (int i 0; i n; i) scanf(%d, p[i]);dfs(1, 0, 0, 0);printf(%d\n, ans);return 0;
}DFS之剪枝与优化
AcWing165 小猫爬山
传送门
#include bits/stdc.h
using namespace std;
const int N 20;
int c[N], bus[N], n, w, ans N;void dfs(int u, int cnt) {// 最优性剪枝if (cnt ans) return ;if (u n) {ans min(ans, cnt);return ;}// 对于第u只小猫,我们先遍历之前已经租用的这cnt辆缆车,看看它能被放入哪一辆车中// 如果都不能放进入则说明需要新开一辆缆车来安置这只小猫for (int i 1; i cnt; i) {if (bus[i] c[u] w) {bus[i] c[u];dfs(u 1, cnt);bus[i] - c[u];}}// 新开一辆车bus[ cnt] c[u];dfs(u 1, cnt);bus[cnt] 0;
}int main()
{scanf(%d%d, n, w);for (int i 1; i n; i) scanf(%d, c[i]);// 可行性剪枝重量从大到小排序sort(c 1, c 1 n, greaterint()); dfs(1, 0);printf(%d\n, ans);return 0;
}AcWing166 数独
传送门
#include bits/stdc.h
using namespace std;
const int N 9;
int ones[1 N], mp[1 N];
int row[N], col[N], cell[3][3];
char s[100];inline int lowbit(int x) {return x -x;
}void init() {for (int i 0; i N; i) row[i] col[i] (1 N) - 1;for (int i 0; i 3; i)for (int j 0; j 3; j)cell[i][j] (1 N) - 1;
}// 获取行、列、小的九宫格的交集的方案数 比如最终结果为100101010,则表示整数2、4、6、9还可以用
inline int get(int x, int y) {return row[x] col[y] cell[x / 3][y / 3];
}bool dfs(int cnt) {if (!cnt) return true;int x, y, minv 10; // minv记录最少的二进制中1的个数(因为1的个数越少说明状态数更少)for (int i 0; i N; i) {for (int j 0; j N; j) {if (s[i * 9 j] .) {int t ones[get(i, j)]; // 查询100101010有多少个1 if (t minv) {minv t;x i, y j;}}}}// 依次枚举(x,y)这个格子可以填的数 比如010010000则表示(x,y)这个格子可以填5和8for (int i get(x, y); i; i - lowbit(i)) {int t mp[lowbit(i)]; // 经过lowbit运算后还需要进一步mp// 开始填数修改状态row[x] - 1 t;col[y] - 1 t;cell[x / 3][y / 3] - 1 t;s[x * 9 y] t 1;// 未填位置少1继续递归下一个空位if (dfs(cnt - 1)) return true;// 恢复现场row[x] 1 t;col[y] 1 t;cell[x / 3][y / 3] 1 t;s[x * 9 y] .;}return false;
}int main()
{for (int i 0; i N; i) mp[1 i] i;for (int i 0; i 1 N; i)for (int j 0; j N; j)ones[i] i j 1;while (cin s, s[0] ! e) {init();int cnt 0; // cnt表示当前有多少个空位需要填写// 把原序列输入的东西转换到数独地图中处理好预局面for (int i 0, u 0; i N; i) {for (int j 0; j N; j, u) {if (s[u] ! .) {int t s[u] - 1;// 填入数字到数独地图中row[i] - 1 t;col[j] - 1 t;cell[i / 3][j / 3] - 1 t;}else { cnt;}}}dfs(cnt);cout s endl;}return 0;
}AcWing167. 木棒
传送门
#include bits/stdc.h
using namespace std;
const int N 70;
int c[N], n, s, per;
bool used[N]; // 标记某根小木棍是否已经被使用过了// u表示当前枚举的是第u组
// len表示当前枚举的第u组原始木棒时,这个木棒里面的那些已经拼凑好的木棍长度之和是len
// start表示枚举第u根原始木棒时 这个木棒中拼凑的起始木棍编号
bool dfs(int u, int len, int start) {// 有u组,每组内的木棍长度是per 如果u * per s, 则找到一个合法解perif (u * per s) return true;// 第u组已经处理完毕继续去处理第u1组if (len per) return dfs(u 1, 0, 0);for (int i start; i n; i) {if (used[i] || len c[i] per) continue;used[i] true;if (dfs(u, len c[i], i 1)) return true;used[i] false;// len0表示拼凑第一根小木棍就失败了// lenw[i]per表示拼凑最后一根小木棍失败了if (!len || len c[i] per) return false;int j i;// 如果把i这根小木棍放进这个模拟的原始木棒中不合法 那么就跳过所有木棍长度与i相等的木棍while (j n c[j] c[i]) j;i j - 1;}return false;
}int main()
{while (~scanf(%d, n), n) {memset(used, 0, sizeof used);s 0;for (int i 0; i n; i) {scanf(%d, c[i]);s c[i];}sort(c, c n, greaterint());per 1;while (1) {if (s % per 0 dfs(0, 0, 0)) {printf(%d\n, per);break;} per;}}return 0;
}AcWing168 生日蛋糕
传送门
#include bits/stdc.h
using namespace std;
const int N 25, INF 0x3f3f3f3f;
int minv[N], mins[N], R[N], H[N], n, m, ans INF;// u表示当前层 sumv记录的是第m层到第u-1层的体积和(不包括第u层的体积 因为它还没有被处理出来)
// sums记录的是第m层到第u-1层的面积和(不包括第u层的体积 因为它还没有被处理出来)
void dfs(int u,int sumv,int sums) {// u0表示第0层 说明第m层到第1层的蛋糕都已经被处理完了// 既然这m层蛋糕都处理完了 那么就可以记录最优解if(!u) {if (sumv n sums ans) anssums;return; }// 剪枝1当前体积和 剩余上面几层的最小体积和 总体积n 则回溯退出if (sumv minv[u] n) return;// 剪枝2当前面积和 剩余上面几层的最小面积和 最优解ans 则回溯退出if (sums mins[u] ans) return;// 剪枝3当前面积和 剩余面积(根据剩余体积进行公式换算) 最优解ans 则回溯退出if(sums 2 * (n - sumv) / R[u 1] ans) return;// 当前层的半径r的取值范围是[ u , min(R[u1]-1,(int)sqrt((n-sumv-minv[u-1])/u)) ]for (int r min(R[u 1] - 1, (int)sqrt((n - sumv - minv[u - 1]) / u)); r u; -- r) {//当前层的高度h的取值范围是[ u , min(H[u1]-1,(int)((n-sumv-minv[u-1])/(r*r))) ]for (int h min(H[u 1] - 1, (int)((n - sumv - minv[u - 1]) / (r * r))); h u ; -- h) {int t 0; // t记录的底面积// 如果当前层是最底层 即第m层 那么就可以计算出所有层的上表面积其实就等于第m层的底面积if (u m) t r * r;R[u] r, H[u] h; // 记录第u层的半径和高度// 递归第u-1层 sumvr*r*h是第m层到第u层的体积和(包括了第u层)// sums2*r*ht是第m层到第u层的面积和(包括了第u层) // 题目要求的面积侧面积2*r*h上表面积t 如果是第m层则tr*r 否则t0dfs(u - 1, sumv r * r * h, sums 2 * r * h t);}}
}int main()
{scanf(%d%d, n, m);// 预处理出前i层的最小体积和 前i层的最小面积和(严格来说是最小侧面积和 而不包括上表面积和)for (int i 1; i m; i) {minv[i] minv[i - 1] i * i * i;mins[i] mins[i - 1] 2 *i *i;}// 由于我们再式子中会用到min(R[u1]) m1层不存在,作为哨兵,减少边界情况的判断 R[m 1] H[m 1] INF;// 从最底层第m层开始深搜dfs(m, 0, 0);if (ans INF) puts(0);else printf(%d\n, ans);return 0;
}迭代加深
AcWing170. 加成序列
传送门
#include bits/stdc.h
using namespace std;
const int N 110;
int path[N], n, maxDep;bool dfs(int dep) {if (dep maxDep) return false;if (path[dep - 1] n) return true;// 如果在当前深度depth搜索不到答案时,就继续到下一个深度depth1去搜索,但是进入下一个深度时// 我们是又从第1层搜索到了第depth1层,每次进入下一层depth1时,都要把st数组清空// 不然上一层depth它搜索的过程从第1层到第depth层中的st数组的数据还会保留// 那么就会影响到下一层depth1它搜索的过程从第1层到第depth1层的st数组的数据了// 优化性剪枝1去重// 用来判断某个求和的数是否被多次计算判重比如1 2 3 4145和235那么5就会被计算2次bool st[N] {0};// 优化性剪枝2优先从大到小的数枚举因为从更大的数枚举更容易逼近n分支数更少for (int i dep - 1; i 0; -- i) {for (int j i; j 0; -- j) {int s path[i] path[j];if (s n || s path[dep - 1] || st[s]) continue;path[dep] s;st[s] true;if (dfs(dep 1)) return true;}}return false;
}int main()
{path[0] 1; // 整数1是固定会有的所以让path[0]1while (~scanf(%d, n), n) {maxDep 1; // 因为path[0]1即整数1这个数已经占据了一层深度所以初始maxDep1// 如果当前的这一层没有找到合法但则继续去寻找下一层while (!dfs(1)) maxDep;for (int i 0; i maxDep; i) printf(%d , path[i]);puts();}return 0;
}双向DFS
AcWing171. 送礼物
传送门
#include bits/stdc.h
using namespace std;
using LL long long;
// w数组用来存储一个集合中所有物品的可能取得到的重量
int g[50], w[1 25], n, m, k, ans, cnt;void dfs1(int u, int s) {if (u k) {w[cnt ] s;return;}if ((LL)s g[u] m) dfs1(u 1, s g[u]);dfs1(u 1, s);
}void dfs2(int u, int s) {if (u n) {int l 0, r cnt - 1;while (l r) {int mid l r 1 1;if (w[mid] (LL)s m) l mid;else r mid - 1;}if (w[l] (LL)s m) ans max(ans, w[l] s);return;}if ((LL)s g[u] m) dfs2(u 1, s g[u]);dfs2(u 1, s);
}int main()
{scanf(%d%d, m, n);for (int i 0; i n; i) scanf(%d, g[i]);sort(g, g n, greaterint());k n / 2 2; // 防止 n 1时出现死循环dfs1(0, 0);sort(w, w cnt);cnt unique(w, w cnt) - w;dfs2(k, 0);printf(%d\n, ans);return 0;
}IDA*
AcWing180 排书
传送门
#include bits/stdc.h
using namespace std;
const int N 20;
// q[]书的排列, w[][]4步以内书的排列
int q[N], w[5][N], n, T, maxDep; // 估价函数
int get() {int cnt 0; // 错误后继的数量for (int i 0; i n - 1; i) if (q[i 1] ! q[i] 1) cnt;// cnt/3向上取整的 写法 是(cnt2)/3return (cnt 2) / 3;
}// 迭代加深 dep是当前层 maxDep是深度限制
bool dfs(int dep) {// 超过最大深度限制 则立即回溯if (dep get() maxDep) return false;//估价函数为0 则到达了目标状态if (get() 0) return true;// 这里有点类似于区间DPfor (int len 1; len n; len) { // 枚举抽取其中连续的一段的长度for (int l 0; l len - 1 n; l) { // 枚举抽取的这段书的左端点int r l len - 1; // r是抽取的这段书的右端点for (int j r 1; j n; j) { // 枚举抽取的这段书应该插入到r后面的哪个位置memcpy(w[dep], q, sizeof q); // 先记录之前的状态int k l;for (int x r 1; x j; x) q[k ] w[dep][x];for (int x l; x r; x) q[k ] w[dep][x];// 向下一层递归if (dfs(dep 1)) return true;memcpy(q, w[dep], sizeof q); // 恢复之前的状态 恢复现场}}}// 搜完全部都搜不到 无解return false;
}int main()
{scanf(%d, T);while(T --) {scanf(%d, n);for (int i 0; i n; i) scanf(%d, q[i]);maxDep 0; // 最大深度限制while (maxDep 5 !dfs(0)) maxDep;if (maxDep 5) puts(5 or more);else printf(%d\n, maxDep);}return 0;
}AcWing181 回转游戏
传送门
#include bits/stdc.h
using namespace std;
const int N 30;
// 给图形中的每个方格一个标号
int op[8][7] {{0, 2, 6, 11, 15, 20, 22},{1, 3, 8, 12, 17, 21, 23},{10, 9, 8, 7, 6, 5, 4},{19, 18, 17, 16, 15, 14, 13},{23, 21, 17, 12, 8, 3, 1},{22, 20, 15, 11, 6, 2, 0},{13, 14, 15, 16, 17, 18, 19},{4, 5, 6, 7, 8, 9, 10}
};
// 将A到H的操作都编号为0到7, opposite[0]5 表示0的相反操作是5
int opposite[8] {5, 4, 7, 6, 1, 0, 3, 2};
// 中间8个格子的编号
int center[8] {6, 7, 8, 11, 12, 15, 16, 17};
// q[]记录题目中输入的数字, path[]记录方案
int q[N], path[100], maxDep; // 计算估价函数
int get() {int sum[4] {0};for (int i 0; i 8; i) {int x center[i]; sum[q[x]];}int k 0; // 找到中间8个方格中出现次数最多的那个数// 方格中的数字只能是1 2 3for (int i 1; i 3; i) k max(k, sum[i]);return 8 - k;
}// 循环移动的操作
void operate(int x) {int t q[op[x][0]];for (int i 0; i 6; i) q[op[x][i]] q[op[x][i 1]];q[op[x][6]] t;
}// 迭代加深 dep是当前搜索层 maxDep是深度限制 last是上一次的操作
bool dfs(int dep, int last) {if (dep get() maxDep) return false;if (get() 0) return true;// 依次按照字典序枚举A到H这8种操作for (int i 0; i 8; i) {// 当前i这个操作的逆向操作不等于上一次的操作if (opposite[i] ! last) {operate(i); // 执行i操作path[dep] i; // 记录当前层的操作是iif (dfs(dep1, i)) return true;// 恢复现场path[dep] 0;operate(opposite[i]);}}return false;
}int main()
{while(cin q[0], q[0]) {for (int i 1;i 24; i) scanf(%d,q[i]);maxDep 0; // 最大深度限制while (!dfs(0, -1)) maxDep;if (!maxDep) printf(No moves needed);else {for (int i 0; i maxDep; i) printf(%c,A path[i]);}// 最中间的8个格子最终都是相同的 编号是从6开始 那么输出q[6]即可printf(\n%d\n, q[6]);}return 0;
}
