学习视频：18-深搜的剪枝策略练习_哔哩哔哩_bilibili
Q：找数字
#include<iostream>
#include<cstring>
using namespace std;
int n;
bool ok;
void dfs(int num, int cnt) {if (cnt >= 19) {return;}if (ok) {return;}if (num % n == 0) {ok = true;cout << num;return;}dfs(num * 10 + 0, cnt + 1);dfs(num * 10 + 1, cnt + 1);
}int main() {cin >> n;dfs(1, 1);return 0;
}
Q：全排列
#include<iostream>
#include<vector>
using namespace std;
int n;
int m = 1;
int a[12];
vector<int> temp;
bool vis[12];
void dfs(int c) {if (c == n) {for (int i = 0; i < temp.size(); i++) {cout << temp[i];}cout << '\n';return;}for (int i = 1; i <= n; i++) {if (!vis[i]) {vis[i] = true;temp.push_back(i);dfs(c + 1);temp.pop_back();vis[i] = false;}}}int main() {cin >> n;for (int i = 1; i <= n; i++) {a[i] = i;m *= i;}cout << '\n';cout << m << endl;dfs(0);return 0;
}
/*
4
*/
Q：蒜头军的旅游计划
#include<iostream>
#include<vector>
using namespace std;
int n;
int city[20][20];
bool vis[20];
int sum = 150000;
void dfs(int pos, int cnt, int s) {if (s >= sum) {return;}if (cnt == n) {s += city[pos][1];if (s < sum)sum = s;return;}for (int i = 1; i <= n; i++) {if (i != pos && !vis[i]) {vis[i] = true;dfs(i, cnt + 1, s + city[pos][i]);vis[i] = false;}}}
int main() {cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> city[i][j];}}vis[1] = true;dfs(1, 1, 0);cout << sum << endl;return 0;
}
/*
4
0 1 1 1
1 0 2 1
5 5 0 6
1 1 3 0
*/
Q：正方形
#include<iostream>
#include<vector>
using namespace std;
int n;
int goal;
int p[25];
bool ok;
bool vis[25];
void dfs(int cnt, int len) {if (cnt == 4) {ok = true;return;}if (ok) {return;}if (len > goal) {return;}if (len == goal) {dfs(cnt + 1, 0);return;}for (int i = 0; i < n; i++) {if (!vis[i]) {vis[i] = true;dfs(cnt, len + p[i]);vis[i] = false;}}}int main() {cin >> n;int sum = 0;for (int i = 0; i < n; i++) {cin >> p[i];sum += p[i];}if (sum % 4 == 0) {goal = sum / 4;dfs(0, 0);if (ok)cout << "Ok" << endl;elsecout << "No" << '\n';}else {cout << "No" << endl;}return 0;
}
/*
4
1 1 1 1
*/
Q：因数最多的数
太难了，听不懂
Q：置换的玩笑
#include<iostream>
#include<string>
using namespace std;
string s;
int ch[60];
int n;
bool ok;
bool vis[60];
void dfs(int u,int cnt) {if (ok)return;if (u == s.size()) {for (int i = 0; i < n; i++) {cout << ch[i] << " ";}cout << '\n';ok = true;return;}int x = s[u] - '0';if (x < n && !vis[x]) {ch[cnt] = x ;vis[x] = true;dfs(u + 1, cnt + 1);vis[x] = false;}if (u >= s.size() - 1)return;x = x * 10 + s[u + 1] - '0';if (x <= n && !vis[x]) {ch[cnt] = x ;vis[x] = true;dfs(u + 2, cnt + 1);vis[x] = false;}
}int main() {cin >> s; n = s.size() <= 9 ? s.size() : (s.size() - 9) / 2 + 9;dfs(0, 0);return 0;
}
/*
4111109876532
*/
Q：Betsy的旅行
#include<iostream>
using namespace std;
int n;
int ans = 0;
bool vis[8][8];
int dir[4][2] = { {0,1},{0,-1},{-1,0},{1,0} };
void dfs(int x, int y, int step) {if (x == n - 1 && y == 0) {if (step == n * n)ans++;return;}if (step >= n * n)return;vis[x][y] = true;for (int i = 0; i < 4; i++) {int fx = x + dir[i][0];int fy = y + dir[i][1];if (fx >= 0 && fx < n && fy >= 0 && fy < n && !vis[fx][fy]) {dfs(fx, fy, step + 1);}}vis[x][y] = false;
}
int main() {cin >> n;dfs(0, 0, 1);cout << ans << endl;return 0;
}
Q：方块消消乐
不会，放弃
————————————————————————————————
学习视频：19-广度优先搜索视频讲解_哔哩哔哩_bilibili
S：数据结构——队列
先进先出，队首出，队尾插入
操作：push入队、pop出队、empty是否空、size元素个数、front访问队首元素
引用：
#include<queue>
queue<int> q;手动清空：
while(!p.empty()){p.pop();
}使用:
#include<iostream>
#include<queue>
using namespace std;
int main() {queue<string> q;q.push("hanxiaolu");q.push("tianmeng");while (!q.empty()) {cout << q.front() << '\n';q.pop();}return 0;
}
Q:报数游戏
#include<iostream>
#include<queue>
using namespace std;
int main() {int n, m;cin >> n >> m;queue<int> q;int a = 1;for (int i = 0; i < n; i++) {q.push(i + 1);}int tmp;while (q.size() > 1) {if (a == 5) {q.pop();a = 1;}else {tmp = q.front();q.pop();q.push(tmp);a++;}}cout << q.front();return 0;
}
S:
广度优先搜索BFS
求最短路的经常用BFS
Q:迷宫游戏
#include<iostream>
#include<queue>
using namespace std;
int n, m;
char maze[10][10];
bool vis[10][10];
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
struct node {int x, y, d;node(int xx, int yy, int dd) {x = xx;y = yy;d = dd;}
};
bool in(int x, int y) {return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs(int sx, int sy) {queue<node> q;q.push(node(sx, sy, 0)); //先放进去一个初始的节点vis[sx][sy] = true;while (!q.empty()) { //循环条件是不空node now = q.front(); //定义新节点后删除q.pop();for (int i = 0; i < 4; i++) { //遍历四个方向int fx = now.x + dir[i][0];int fy = now.y + dir[i][1];if (in(fx, fy) && !vis[fx][fy] && maze[fx][fy] != '*') {//条件筛选if (maze[fx][fy] == 'T') { //终止条件return now.d + 1;}else { //继续放小的vis[fx][fy] = true;q.push(node(fx, fy, now.d + 1));}}}return -1;
}
int main() {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> maze[i];}int x, y;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (maze[i][j] == 'S')x = i, y = j; }}cout << bfs(x, y) << '\n';return 0;
}
/*
5 6
....S*
.**...
.*..*.
*..**.
.T....
*/
Q：一维坐标的移动
#include<iostream>
#include<queue>
using namespace std;
queue<pair<int,int>> q;
bool vis[5005];int main() {int n, A, B, now, step;cin >> n >> A >> B;q.push(make_pair(A, 0));//结构体也可以vis[A] = true;while (!q.empty()) {now = q.front().first;step = q.front().second;q.pop();if (now == B) { //终止条件cout << step;break;}if (now + 1 <= n && !vis[now + 1]) {//下一个没有访问过并且未越界q.push(make_pair(now + 1, step + 1));vis[now + 1] = true;}if (now - 1 >= 0 && !vis[now - 1]) {q.push(make_pair(now - 1, step + 1));vis[now - 1] = true;}if (now * 2 <= n && !vis[now * 2]) {q.push(make_pair(now * 2, step + 1));vis[now * 2] = true;}}return 0;
}
