AKSZ-BFS
2024-06-02 17:35:16
发布于：广东
42阅读
0回复
0点赞
广度优先搜索
模板
#include<bits/stdc++.h>
using namespace std;
const int maxn = 45;
int n, m;
char s[maxn][maxn];
//方向数组
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int vis[maxn][maxn]; //每个点不重复
//状态 在哪个点，目前使用步数
//结构体定义状态
struct node{
int x, y; //目前走到(x, y)这个点上
int step;
};
void bfs(){
//维护一个队列 -> 扩展状态
queue<node> q; //状态队列
//先让出发点入队
q.push(node{0, 0, 0}); //将0, 0, 0状态入队
vis[0][0] = 1;
//队列非空，更新状态
while(!q.empty()){
node tmp = q.front(); //取出队列头
q.pop(); //出队
if(tmp.x == n - 1 && tmp.y == m - 1){
cout << tmp.step << endl;
return; //第一个找到
}
for(int i = 0; i < 4; i++){
int tx = tmp.x + dx[i]; //下一步x坐标
int ty = tmp.y + dy[i]; //下一步y坐标
if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue; //越界跳过
if(vis[tx][ty]) continue; //每个点访问一次
if(s[tx][ty] == '#') continue; //遇到障碍跳过
vis[tx][ty] = 1; //表示已访问
q.push(node{tx, ty, tmp.step + 1}); //入队状态
}
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> s[i][j];
bfs();
return 0;
}
单调性
B站关注Regenfallen
隐式图
看不出来 但可以化为图
康拓展开
int v[1145], fc[1145];
int kt(int t){
for(int i = 8; i >= 0; i--){
v[i] = t % 10;
t /= 10;
}
int ans = 0;
for(int i = 0; i < 9; i++){
int rev = 0; //找逆序对
for(int j = i + 1; j < 9; j++){
rev += v[i] > v[j];
}
ans += rev * fc[8 - i]; //对应的阶乘
}
return ans; //转化为康拓展开数
}
void init(){
for(int i = 1; i <= 8; i++){
int t = 1;
for(int j = 1; j <= i; j++){
t *= j;
}
fc[i] = t;
}
}
## 双端队列
```cpp
deqeu<int> q;
q.size(); //大小
q.empty(); //判空
q.push_back(); //在队列头加元素
q.push_front(); //在队列尾加元素
q.pop_back(); //删头
q.pop_back(); //删尾
__int128
快读函数
__int128 read(){
char arr[30];
__int128 res = 0;
scanf("%s", arr);
for(int i = 0; i < strlen(arr); i++){
res *= 10;
res += arr[i] - '0';
}
return res;
}
快写函数
void print(__int128 num){
if(num > 9){
print(num / 10);
}
putchar(num % 10 + '0');
}
字符输入
int a = -1, b = -1, c = -1, d = -1, e = -1;
int t = sscanf(s, "%d.%d.%d.%d:%d", &a, &b, &c, &d, &e);
有帮助，赞一个