广度优先搜索 及其 杂题
2026-07-20 20:55:32
发布于：广东
107阅读
0回复
0点赞
最短路的数量
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[200010];
int d[200010];//起点到达 i 点最短路径
long long mod = 1e9 + 7;
long long cnt[200010];
int main(){
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=1;i<=n;i++)d[i] = -1;
queue<int> q;
q.push(1);
d[1] = 0;
cnt[1] = 1;
while(q.size()){
int u = q.front();
q.pop();
for(int i=0;i<g[u].size();i++){
int ne = g[u][i];
if(d[ne]==-1){
d[ne] = d[u] + 1;
cnt[ne] = cnt[u];//继承
q.push(ne);
}else if(d[ne] == d[u] + 1){
cnt[ne] = (cnt[ne] + cnt[u]) % mod; //累加
}
}
}
cout<<cnt[n];
return 0;
}
小苹果
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
int n;
cin>>n;
int day = 0,ans = 0;
while(n>0){
day++;
if(n%3==1){
if(ans == 0)ans = day;
}
n-=(n+3-1)/3;
}
cout<<day<<" "<<ans;
fclose(stdin);
fclose(stdout);
}
#include<bits/stdc++.h>
using namespace std;
bool vis[1000001];
int main(){
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++)vis[i] = true;// 标记所有苹果存在
// day 最终天数 ans 第n苹果 天数
int day = 1 , ans = 0;
int x = n;//剩下多少苹果
while(x>0){
int id = 0;//吃的苹果编号
for(int i=1;i<=n;i++){
if(vis[i]==true){
id++;
if(id%3==1){
x--;
vis[i] = false;
if(i==n){
ans = day;
}
}
}
}
day++;
}
cout<<day-1<<" "<<ans;
fclose(stdin);
fclose(stdout);
}
圣殿符文的奥秘
#include<bits/stdc++.h>
using namespace std;
struct stu{
int x,y;
};
bool vis[1005][1005];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int main(){
freopen("trap.in","r",stdin);
freopen("trap.out","w",stdout);
int n,m;
cin>>n>>m;
char a[1005][1005];
vector<stu> p;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin>>a[i][j];
if(a[i][j] == 'E'){
p.push_back({i,j});
}
}
}
queue<stu> q;
q.push({1,1});
vis[1][1] = 1;
while(!q.empty()){
stu u = q.front();
q.pop();
for(int i = 0;i<4;i++){
int nx = u.x+dx[i];
int ny = u.y+dy[i];
if(nx>n||nx<1||ny>m||ny<1){
continue;
}
if(a[nx][ny] == '#'){
continue;
}
if(vis[nx][ny] == 1){
continue;
}
q.push({nx,ny});
vis[nx][ny] = 1;
}
}
int cnt = 0;
for(int i = 0;i<p.size();i++){
if(vis[p[i].x][p[i].y] == 1){
cnt++;
}
}
cout<<cnt;
fclose(stdin);
fclose(stdout);
return 0;
}
暗影迷宫的「猎杀」时刻
#include<bits/stdc++.h>
using namespace std;
struct stu{
int x,y;
};
bool vis[1005][1005];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int main(){
freopen("trap.in","r",stdin);
freopen("trap.out","w",stdout);
int n,m;
cin>>n>>m;
char a[1005][1005];
vector<stu> p;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin>>a[i][j];
if(a[i][j] == 'E'){
p.push_back({i,j});
}
}
}
queue<stu> q;
q.push({1,1});
vis[1][1] = 1;
while(!q.empty()){
stu u = q.front();
q.pop();
for(int i = 0;i<4;i++){
int nx = u.x+dx[i];
int ny = u.y+dy[i];
if(nx>n||nx<1||ny>m||ny<1){
continue;
}
if(a[nx][ny] == '#'){
continue;
}
if(vis[nx][ny] == 1){
continue;
}
q.push({nx,ny});
vis[nx][ny] = 1;
}
}
int cnt = 0;
for(int i = 0;i<p.size();i++){
if(vis[p[i].x][p[i].y] == 1){
cnt++;
}
}
cout<<cnt;
fclose(stdin);
fclose(stdout);
return 0;
}
区间7倍数
#include<iostream>
using namespace std;
// 最长的区间 sum = 0
int cnt[7]; // 存余数为i的前缀最小下标
int main(){
freopen("mx.in", "r", stdin);
freopen("mx.out", "w", stdout);
int n;
cin >> n;
for(int i=0;i<=6;i++)cnt[i] = -1;
int sum = 0,mx = 0;//求前缀
cnt[0] = 0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
sum+=x;
sum%=7;
if(cnt[sum]!=-1)mx = max(mx,i - cnt[sum]);
if(cnt[sum]==-1)cnt[sum] = i;
}
cout << mx;
fclose(stdin);
fclose(stdout);
return 0;
}
有帮助，赞一个