目录

奇怪的电梯

马的遍历

 PERKET（个人认为很抽象）

---

奇怪的电梯

P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路，还是用的bfs，建立一个结构体类型的队列，一个存当前的电梯层数，一个存当前走的步数

还要建一个bool类型的数组标记当前电梯层数是否走过

完整代码

#include <bits/stdc++.h>
const int N = 210;
int n,a,b;
int g[N];
int ans;
bool vis[N]{};
struct node
{int lou;int step;
};
void bfs()
{std::queue<node> q;q.push({a,0});while(!q.empty()){node tmp=q.front();q.pop();int cur_low=tmp.lou,cur_step=tmp.step;if(cur_low==b){std::cout<<cur_step;return;}if(cur_low+g[cur_low]<=n&&vis[cur_low+g[cur_low]]==false){q.push({cur_low+g[cur_low],cur_step+1});vis[cur_low+g[cur_low]]=true;}if(cur_low-g[cur_low]>=1&&vis[cur_low-g[cur_low]]==false){q.push({cur_low-g[cur_low],cur_step+1});vis[cur_low-g[cur_low]]=true;}}std::cout<<-1;
}
int main()
{std::cin >> n >> a >> b;for(int i = 1;i <= n;i ++){std::cin >> g[i];}bfs();return 0;
}

马的遍历

P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：用bfs，八个坐标，依次遍历 ，没有搜索到的点就输出-1

超时代码：

#include <bits/stdc++.h>
const int N = 410;
int n,m,x,y;
int g[N][N];
bool vis[N][N]{};
int rr[10]={-1,-2,-2,-1,1,2,2,1};
int cc[10]={-2,-1,1,2,2,1,-1,-2};
struct node
{int r,c,step;
};
void bfs(int ii,int jj)
{std::queue<node> q;q.push({x,y,0});memset(vis,false,sizeof(vis));while(!q.empty()){node tmp=q.front();q.pop();int cur_r=tmp.r,cur_c=tmp.c,cur_step=tmp.step;if(cur_r==ii&&cur_c==jj){std::cout<<cur_step<<" ";return;}for(int i = 0;i < 8;i ++){int next_r=cur_r+rr[i];int next_c=cur_c+cc[i];if(next_r>=1&&next_r<=n&&next_c>=1&&next_c<=m&&vis[next_r][next_c]==false){q.push({next_r,next_c,cur_step+1});vis[next_r][next_c]=true;}}}std::cout<<-1<<" ";
}
int main()
{std::cin >> n >> m >> x >> y;for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){bfs(i,j);}std::cout<<"\n";}return 0;
}

 

因为每次都要进一次bfs，所以时间复杂度就提高了

所以只需要进一次bfs,用一个二维数组记录到达每个点的步数（因为要走下一个点必然会经过当前这个点）

ac代码

#include <bits/stdc++.h>
const int N = 410;
int n,m,x,y;
int g[N][N];
bool vis[N][N]{};
int rr[10]={-1,-2,-2,-1,1,2,2,1};
int cc[10]={-2,-1,1,2,2,1,-1,-2};
int ans[N][N];
struct node
{int r,c,step;
};
void bfs()
{memset(ans,-1,sizeof(ans));std::queue<node> q;q.push({x,y,0});memset(vis,false,sizeof(vis));vis[x][y]=true;while(!q.empty()){node tmp=q.front();q.pop();int cur_r=tmp.r,cur_c=tmp.c,cur_step=tmp.step;ans[cur_r][cur_c]=cur_step;for(int i = 0;i < 8;i ++){int next_r=cur_r+rr[i];int next_c=cur_c+cc[i];if(next_r>=1&&next_r<=n&&next_c>=1&&next_c<=m&&vis[next_r][next_c]==false){q.push({next_r,next_c,cur_step+1});vis[next_r][next_c]=true;}}}
}
int main()
{std::cin >> n >> m >> x >> y;bfs();for(int i = 1;i <= n;i ++){for(int j = 1;j <= m;j ++){std::cout<<ans[i][j]<<" ";}std::cout<<"\n";}return 0;
}

 

 PERKET（个人认为很抽象）

P2036 [COCI 2008/2009 #2] PERKET - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：这道题用dfs，枚举选和不选两种状态，取最小值

完整代码

#include <bits/stdc++.h>
const int N = 15;
int a[N],b[N];
int n,ans=999999999;
void dfs(int i,int x,int y)//编号，酸度，甜度
{if(i>n){if(x==1&&y==0)return;ans=std::min(std::abs(x-y),ans);return;}dfs(i+1,x*a[i],y+b[i]);dfs(i+1,x,y);
}
int main()
{std::cin >> n;for(int i = 1;i <= n;i ++){std::cin >> a[i] >> b[i];}dfs(1,1,0);std::cout<<ans<<"\n";return 0;
}