2025年NEUQ-ACM预备队必做题

NEUQ-ACM预备队必做题P1135 奇怪的电梯 bfs 注意下边界 和 queue 的使用 include bits stdc h define f i x y for int i x i lt y i define ll long long class flour public bits

大家好,我是讯享网,很高兴认识大家。

P1135 奇怪的电梯

bfs 注意下边界,和queue的使用

#include<bits/stdc++.h> #define f(i,x,y) for(int (i)=(x);(i)<=(y);++(i)) #define ll long long class flour{ public: int id,step; flour(int xx,int yy){id=xx,step=yy;} flour& operator=(const flour& xx) { this->id=xx.id; this->step=xx.step; } }; int con[205]; int a,b,n,c[205]; const int operate[3]={0,-1,1}; using namespace std; int bfs() { queue<flour> x; x.push((flour){a,0}); while(!x.empty()) { flour f=x.front(); x.pop(); if(f.id==b) return f.step; f(i,1,2) { int id1=f.id+c[f.id]*operate[i]; if(id1>=1&&con[id1]==0) { con[id1]=1; x.push((flour){id1,f.step+1}); } } } return -1; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); memset(con,0,sizeof(0)); cin>>n>>a>>b; f(i,1,n)//方便统一,第一个位置是初始位置。 cin>>c[i]; cout<<bfs(); return 0; } 

讯享网

 P1443 马的遍历

bfs


讯享网

讯享网#include <bits/stdc++.h> #define f(i,x,y) for(int (i)=(x);(i)<=(y);++(i)) #define ll long long using namespace std; class location{ public: int x,y,step; location(int xx,int yy,int zz){ this->x=xx; this->y=yy; this->step=zz; return; } location(){ this->step=0; } }; int con[450][450]; const int operate[8][2]={1,-2, 1,2, 2,1, 2,-1, -1,-2, -1,2, -2,1, -2,-1}; int main(){ int n; location begin,boundary; cin>>boundary.x>>boundary.y>>begin.x>>begin.y; f(i,1,boundary.x) f(j,1,boundary.y) con[i][j]=-1; con[begin.x][begin.y]=0; queue<location> ho; ho.push(begin); while(!ho.empty()){ location a=ho.front(); ho.pop(); f(i,0,7){ location b(a.x+operate[i][0],a.y+operate[i][1],a.step+1); if(b.x>0&&b.y>0&&b.x<=boundary.x&&b.y<=boundary.y) if(con[b.x][b.y]==-1){ con[b.x][b.y]=b.step; ho.push(b); } } } f(i,1,boundary.x){ f(j,1,boundary.y) printf("%-5d",con[i][j]); cout<<'\n'; } return 0; } 

P3958 [NOIP2017 提高组] 奶酪

注意距离计算用平方

#include<bits/stdc++.h> #define f(i,x,y) for(int (i)=(x);(i)<=(y);++(i)) #define ll long long using namespace std; class location{ public: ll x,y,z; }a[]; int con[]; ll dis(location a,location b) { return (ll)(a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)*1.0+(a.z-b.z)*(a.z-b.z)*1.0; } bool bbfs(const ll xx,const ll n,const ll h,const ll r) { memset(con,0,sizeof(con)); con[xx]=1; queue<location> qu; qu.push(a[xx]); while(!qu.empty()) { location noww=qu.front(); if(h<=noww.z+r) return true; qu.pop(); f(i,1,n) if(con[i]==0) if(dis(noww,a[i])<=4*r*r) { qu.push(a[i]); con[i]=1; } } return false; } void bfs(const ll n,const ll h,const ll r){ queue<location> que; f(i,1,n) if(r>=a[i].z) if(bbfs(i,n,h,r)) { cout<<"Yes"; return; } cout<<"No"; return; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); ll T; cin>>T; while(T--){ ll n; ll h,r; cin>>n>>h>>r; f(i,1,n) cin>>a[i].x>>a[i].y>>a[i].z; bfs(n,h,r); if(T!=0) cout<<'\n'; } return 0; } 

P1162 填涂颜色

从边界bfs

讯享网#include<bits/stdc++.h> #define f(i,x,y) for(int (i)=(x);(i)<=(y);++(i)) #define ll long long using namespace std; int a[31][31],n; int con[31][31];//表示有没有查过 int op[4][2]={1,0, -1,0, 0,1, 0,-1 }; void bfs(int x, int y){ if (x < 1 || x > n || y < 1 || y > n || con[x][y] != 0 || a[x][y] == 1) { return; } con[x][y] = 2; for(int i = 0; i < 4; ++i) { bfs(x + op[i][0], y + op[i][1]); } } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; f(i,1,n) f(j,1,n) { cin>>a[i][j]; if(a[i][j]==1) con[i][j]=1; } // 从边界开始搜索 f(i,1,n) { bfs(1, i); bfs(n, i); bfs(i, 1); bfs(i, n); } // 填充内部区域 f(i, 1, n) { f(j, 1, n) { if (a[i][j] == 0 && con[i][j] == 0) { a[i][j] = 2; } } } // 输出结果 f(i,1,n){ f(j,1,n) cout<<a[i][j]<<" "; cout<<'\n'; } return 0; } 

小讯
上一篇 2025-03-08 20:06
下一篇 2025-02-20 23:53

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/114381.html