写着玩,别当真
BFS
从起点向可以到达的地方一层一层延展,何尝不是一种暴力
万物皆暴力[/doge]
因此,他有一种“最短”性质hh
走迷宫求距离版
把起点先入队列,由起点开始向外拓展,每个可以到达的地方的距离都被标出了hh
8 7 6 5 4
7 -1 5 -1 3
6 5 4 3 2
7 -1 -1 -1 1
8 9 10 -1 0
例如这个,起点在右下角,终点在左上角(事实上你可以求任意一点到另一点的距离,原理都一样)
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int dist[N][N];
int g[N][N];
PII q[N*N];
PII mer[N][N];
int n,m;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
void bfs()
{
q[0] = {n,m};
memset(dist,-1,sizeof dist);
dist[n][m] = 0;
int hh = 0,tt = 0;
while(hh <= tt)
{
auto t = q[hh++];
for(int i = 0;i < 4;i++)
{
int a = t.fi+dx[i],b = t.se+dy[i];
if(a < 1 || b < 1 || a > n || b > m) continue;
if(dist[a][b] != -1) continue;
if(g[a][b] == 1) continue;
dist[a][b] = dist[t.fi][t.se]+1;
mer[a][b] = t;
q[++tt] = {a,b};
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
cin >> g[i][j];
bfs();
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++)
printf("%5d",dist[i][j]);
cout << endl;
求路径
走迷宫一般要知道路上怎么走,于是就有了求路径的问题
求的方法也很简单hh
因为懒得再开个数组使得正着输出,所以直接把出入口换一下hh
把出口先搞进队列去,以它为起点开始向外拓展,多一个PII数组用来把每一步的t存下来,拓展到起点后总会有一条存下来的从终点到起点的道路,新建一个PII存入起点,让它自己去递归就行
# include <bits/stdc++.h>
using namespace std;
# define fi first
# define se second
typedef pair<int,int> PII;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
const int N = 1010;
int g[N][N];
PII pre[N][N];
int n;
void bfs(int xx,int yy)
{
memset(pre,-1,sizeof pre);
queue<PII> q;
q.push({xx,yy});
pre[xx][yy] = {0,0};
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0;i < 4;i++)
{
int a = t.fi + dx[i],b = t.se + dy[i];
if(a < 0 || b < 0 || a>=n || b >= n) continue;
if(g[a][b])continue;
if(pre[a][b].fi!= -1) continue;//判重
q.push({a,b});
pre[a][b] = t;
}
}
}
int main()
{
cin >> n;
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
cin >> g[i][j];
bfs(n-1,n-1);
PII end(0,0);
while(1)
{
cout << end.fi << ' ' << end.se << endl;
if(end.fi == n-1 && end.se == n-1) break;
end = pre[end.fi][end.se];
}
}
上头俩组合一起后
上头俩组合一起后,就有点上头
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int dist[N][N];
int g[N][N];
PII q[N*N];
PII mer[N][N];
int n,m;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
void bfs()
{
q[0] = {n,m};
memset(dist,-1,sizeof dist);
dist[n][m] = 0;
//memset(mer,-1,sizeof mer);
int hh = 0,tt = 0;
while(hh <= tt)
{
auto t = q[hh++];
for(int i = 0;i < 4;i++)
{
int a = t.fi+dx[i],b = t.se+dy[i];
if(a < 1 || b < 1 || a > n || b > m) continue;
if(dist[a][b] != -1) continue;
if(g[a][b] == 1) continue;
//if(mer[a][b].fi != -1) continue;判重作用,职能重复
dist[a][b] = dist[t.fi][t.se]+1;
mer[a][b] = t;
q[++tt] = {a,b};
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
cin >> g[i][j];
bfs();
PII ed(1,1);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++)
printf("%5d",dist[i][j]);
cout << endl;
}
// while(1)
// {
// cout << ed.fi << ' ' << ed.se << endl;
// if(ed.fi == n && ed.se == m) break;
// ed = mer[ed.fi][ed.se];
// }
}
有句话说得好,我不能请假,不然就会被老板发现我可有可无
这里我注释掉了两句话,就是随便玩玩时发现可有可无,直接给fire了hh
这句话起的是防止重复的作用,比较前俩都比较单纯,说干啥就干啥,求路径的是一点距离的都不搞,没有这个就只能另辟蹊径判重喽。
这说明有时候吧代码组装一下也许会有新发现hh