本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。
💓博主csdn个人主页:小小unicorn
⏩专栏分类:算法从入门到精通
🚚代码仓库:小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识
献给阿尔吉侬的花束:
算法原理:
用 a[N][N] 接收地图。
dis[N][N] 存储到每个点的路径长度。
从起点出发,广度优先遍历地图:
起点入队。
如果队列非空,一直执行下面语句:
- 队头出队。
- 遍历队头的上下左右四个方向:如果是 ‘.’ 走过去,并且该位置入队,该点对应的dis值更新为队头的dis + 1,该点更新为’#',表示走过了。如果是 ‘#’ 不做处理,如果是 ‘E’,走到了终点,输出该点对应的 dis 值。
如果队列为空,还没有找到终点,则无法到达,输出 oop!。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 210;
char a[N][N];
int dis[N][N];
void bfs(PII start)
{
queue<PII> q;
q.push(start);//队头队,对应步骤1
while(!q.empty())
{
PII u = q.front();
q.pop();
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0 ,-1};
for(int i = 0; i < 4; i++)//遍历四个方向,对应步骤2
{
int x = u.first + dx[i];
int y = u.second + dy[i];
if(a[x][y] == '#') continue;//如果是'#',不做任何处理
if(a[x][y] == '.')//如果是 '.',更新对应内容
{
dis[x][y] = dis[u.first][u.second] + 1;
a[x][y] = '#';
q.push({x, y});
}
if(a[x][y] == 'E')//如果是'E',找到了,输出
{
cout << dis[u.first][u.second] + 1 << endl;
return;
}
}
}
cout << "oop!" << endl;//没有找到
}
int main()
{
int t;
cin >> t;
while(t--)
{
memset(a, '#', sizeof(a));//初始化地图,各个点都是墙。
memset(dis, 0, sizeof(dis));//初始化dis
int n,m;
PII start;
cin >> n >> m;
for(int i = 1; i <= n; i++)//从第一行存储地图,因为四周都是墙,bfs时,可以不做越界判断
{
for(int j = 1; j <= m; j++)//从第一;列存储地图,因为四周都是墙,bfs时,可以不做越界判断
{
cin >> a[i][j];
if(a[i][j] == 'S')//记录下起点位置。
start.first = i, start.second = j, a[i][j] = '#';
}
}
bfs(start);
}
}
说明一下,地图初始化为全是墙,然后把地图存储在a[1][1] ~ a[n][m]后,地图四周会被墙包围,所以 bfs 的时候,不用做地图越界处理了。
红与黑
算法原理:
深度优先遍历算法。
对于某个点执行如下算法:
-
从该点出发,如果可以往上走就往上走,对上方点递归执行该算法。
-
从该点出发,如果可以往右走就往右走,对右方点递归执行该算法。
-
从该点出发,如果可以往下走就往下走,对下方点递归执行该算法。
-
从该点出发,如果可以往左走就往左走,对左方点递归执行该算法。
#include <cstring>
#include <iostream>
using namespace std;
const int N = 25;
int n, m;
char g[N][N];//存储地板
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//上右下左四个方向
int dfs(int x, int y)//深度优先遍历
{
int cnt = 1;
g[x][y] = '#';
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) continue;
if (g[a][b] != '.') continue;
cnt += dfs(a, b);//如果可以走向某一个方向,对该方向上的点递归
}
return cnt;
}
int main()
{
while (cin >> m >> n, n || m)
{
for (int i = 0; i < n; i ++ ) cin >> g[i];//一次读入一行
int x, y;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == '@')
{
x = i;
y = j;
}
cout << dfs(x, y) << endl;
}
return 0;
}
交换瓶子
算法原理:
暴力枚举
1、通过观察可以发现,我们每一个数都必须回到它自己的位置上,比如 1 必须在第一位,2 必须在第二位上
2、那么我们就可以这样操作,由于每个数必须回到自己的位置,直接从 1 枚举到 n n n ,如果当前位置的数不等于它的下标,那么我们就必须要把它给替换掉
3、设当前位置为 i i i 的话,那么我们就从 i + 1 i+1 i+1 开始往后枚举,直到找到对应的 a[ j j j] 和我们的 i i i 相等,那么我们就把上个数交换,把交换次数++
4、容易证明这个算法的正确性,由于每个数必须回到原来的位置,所以我们这样子操作不会出现多于的步骤,因为每次操作都是必须的,即使这个算法看起来很麻烦
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=10010;
int n;
int a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int sum=0;
for(int i=1;i<=n;i++)
{
if(a[i]!=i)//直接遍历,如果不是自身的话,我们必然要交换,所以不会出现多于的操作
{
for(int j=i+1;j<=n;j++)
if(a[j]==i)
swap(a[i],a[j]);
sum++;
}
}
printf("%d\n",sum);
return 0;
}
完全二叉树的权值
算法原理:
前置:完全二叉树性质
对于第 i i i 层,保证存在 2 i − 1 2^{i-1} 2i−1 个结点的满二叉树。
题目思路:
对于每一层的和,我们可以用 h h h 数组进行存储:
h 1 h_1 h1 = ∑ i = 2 1 − 1 2 1 − 1 ( a i ) \sum\limits^{2^{1}-1}_{i=2^{1-1}}(a_i) i=21−1∑21−1(ai)
h 2 h_2 h2 = ∑ i = 2 2 − 1 2 2 − 1 ( a i ) \sum\limits^{2^{2}-1}_{i=2^{2-1}}(a_i) i=22−1∑22−1(ai)
h 3 h_3 h3 = ∑ i = 2 3 − 1 2 3 − 1 ( a i ) \sum\limits^{2^{3}-1}_{i=2^{3-1}}(a_i) i=23−1∑23−1(ai)
h 4 h_4 h4 = ∑ i = 2 4 − 1 2 4 − 1 ( a i ) \sum\limits^{2^{4}-1}_{i=2^{4-1}}(a_i) i=24−1∑24−1(ai)
…
是不是发现突然很简单?对于每个 h i h_i hi,我们可以求 ∑ j = 2 i − 1 2 i − 1 ( a j ) \sum\limits^{2^{i}-1}_{j=2^{i-1}}(a_j) j=2i−1∑2i−1(aj) 就行啦!
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x7ffffff;
int n;
int a[1 << 17], h[17];//2^17 > 10^5
signed main() {
scanf ("%lld", &n);
for (int i = 1; i <= n; i ++)
scanf ("%lld", a + i);
//读入 ai,因为 n 的大小是 10^5, 所以用 scanf 这类较快的读入方式。
int i = 1, j = 0;
while (i <= n) {
++ j;
while (i < pow (2, j)) {//从 2^(j-1) 循环到 2^j-1
h[j] += a[i ++];
}
}
int maxx = -INF, res = 0;//找最大
for (i = 1; i <= j; i ++)
if (h[i] > maxx)
maxx = h[i],
res = i;
printf ("%lld\n", res);
return 0;
}
地牢大师
算法原理:
分析
-
该迷宫为立体,故需要三维数组构建迷宫模型
-
要求第一次搜到的点即为答案,则考虑BFS
-
记录
S
和E
的位置,S
为搜索开始的点,E
为搜索结束点 -
搜索过程中的每个位置需要向六个方向偏移,需要[偏移量]数组
-
偏移点需满足的要求:不越界,未走过,不能是墙
#
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int l,r,c; //迷宫参数
int px,py,pz,ex,ey,ez; //pi为S的位置,ei为E的位置
char mp[N][N][N]; //记录迷宫
int ans[N][N][N]; //存储答案
bool vis[N][N][N]; //记录该点是否走过的状态
struct point{ //点的坐标
int x,y,z;
};
queue<point> st; //搜索队列
int dx[]={1,-1,0,0,0,0},dy[]={0,0,1,-1,0,0},dz[]={0,0,0,0,1,-1}; //偏移量数组
int bfs(){
while(!st.empty()){ //当队头不为空时,扩展搜索队头
auto p=st.front();
for(int i=0;i<6;i++){
int m_x=p.x+dx[i],m_y=p.y+dy[i],m_z=p.z+dz[i]; //偏移之后的点的坐标
if(m_x<=l&&m_y<=r&&m_z<=c&&m_x>=1&&m_y>=1&&m_z>=1&&!vis[m_x][m_y][m_z]&&mp[m_x][m_y][m_z]!='#'){ //判断条件
vis[m_x][m_y][m_z]=1; //更新该点走过的状态
ans[m_x][m_y][m_z]=ans[p.x][p.y][p.z]+1; //更新偏移后的点距离S的步骤
if(mp[m_x][m_y][m_z]=='E') return ans[m_x][m_y][m_z]; //搜到E直接返回答案
st.push({m_x,m_y,m_z}); //将该点入队,继续扩展搜索
}
}
st.pop(); //队头扩展搜索完毕后出队
}
return 0; //所有的点扩展搜索完后若还未返回搜到E,说明无解
}
int main(){
while(cin>>l>>r>>c&&l&&r&&c){ //多实例读入
//还原数据
memset(ans,0,sizeof(ans));
memset(mp,0,sizeof(mp));
memset(vis,0,sizeof(vis));
while(st.size()){
st.pop();
}
//读入迷宫
for(int i=1;i<=l;i++){
for(int j=1;j<=r;j++){
for(int k=1;k<=c;k++){
cin>>mp[i][j][k];
if(mp[i][j][k]=='S') px=i,py=j,pz=k; //
if(mp[i][j][k]=='E') ex=i,ey=j,ez=k; //
}
}
}
vis[px][py][pz]=1; //标记S已经走过
st.push({px,py,pz}); //S点入队
int cnt=bfs(); //调用搜索,将从S点开始搜索
if(cnt!=0) printf("Escaped in %d minute(s).\n",cnt);
else cout<<"Trapped!"<<endl;
}
return 0;
}
全球变暖
算法原理
题目一看就是“连通块问题”,是基础搜索。用DFS或BFS都行:遍历一个连通块(找到这个连通块中所有的’#‘,并标记已经搜过,不用再搜);再遍历下一个连通块…;遍历完所有连通块,统计有多少个连通块。文章来源:https://www.toymoban.com/news/detail-852287.html
回到题目,什么岛屿不会被完全淹没?若岛中有个陆地(称为高地),它周围都是陆地,那么这个岛不会被完全淹没。
用DFS或BFS搜出有多少个岛(连通块),并且在搜索时统计那些没有高地的岛(连通块)的数量,就是答案。
因为每个像素点只用搜一次且必须搜一次,所以复杂度是
O
(
n
2
)
O(n^2)
O(n2)的,不可能更好了。文章来源地址https://www.toymoban.com/news/detail-852287.html
#include<bits/stdc++.h>
using namespace std;
int n;
char a[1010][1010]; //地图
int vis[1010][1010]={0}; //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag; //用于标记这个岛中是否被完全淹没
void dfs(int x, int y)
{
vis[x][y] = 1; //标记这个'#'被搜过。注意为什么可以放在这里
if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')
flag = 1; //上下左右都是陆地,不会淹没
for(int i = 0; i < 4; i++){ //继续DFS周围的陆地
int nx = x + d[i][0], ny = y + d[i][1];
//if(nx>=1 && nx<=n && ny>=1 && ny<=n && vis[nx][ny]==0 && a[nx][ny]=='#') //题目说边上都是水,所以不用这么写了
if(vis[nx][ny]==0 && a[nx][ny]=='#') //继续DFS未搜过的陆地,目的是标记它们
dfs(nx,ny);
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> a[i][j];
int ans = 0 ;
for(int i = 1; i <= n; i++) //DFS所有像素点
for(int j = 1; j <= n; j++)
if(a[i][j]=='#' && vis[i][j]==0)
{
flag = 0;
dfs(i,j);
if(flag == 0) //这个岛全部被淹
ans++; //统计岛的数量
}
cout<<ans<<endl;
return 0;
}
到了这里,关于[第五章]图论&&BFS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!