首页 > 代码库 > 关于用BFS求环的数量
关于用BFS求环的数量
简单说说的话就是循环里面套bfs....
oj 1196......
#include<iostream> #include<string> #include<cstring> #include<cstring> #include<cstring> using namespace std; int dx[9],dy[9]; int top=0; struct ww { int x,y,c,v; }q[10000000]; int big[1000002],small[1000002]; int f[1001][1001]={}; int map[1001][1001]; int main() { int ans=0,bns=0; dx[1]=1; dy[1]=0; dx[2]=1; dy[2]=1; dx[3]=1; dy[3]=-1; dx[4]=0; dy[4]=1; dx[5]=0; dy[5]=-1; dx[6]=-1; dy[6]=0; dx[7]=-1; dy[7]=1; dx[8]=-1; dy[8]=-1; int n; cin>>n; int w=0; for(int i=1;i<=n;i++) for(int u=1;u<=n;u++) cin>>map[i][u]; int head=1; for(int i=1;i<=n;i++) for(int u=1;u<=n;u++) { if(f[i][u]==0) { f[i][u]=1; q[++top].x=i,q[top].y=u,q[top].c=++w,q[top].v=map[i][u]; for(;head<=top;head++) { int x,y; for(int i=1;i<=8;i++) { if(i>8)break; x=q[head].x+dx[i],y=q[head].y+dy[i]; if(x<=0||y<=0){continue;} if(x>n||y>n){continue;} if(map[x][y]<q[head].v)big[w]=1; if(map[x][y]>q[head].v){small[w]=1;} if(map[x][y]==q[head].v&&f[x][y]==0){f[x][y]=1,q[++top].x=x,q[top].y=y,q[top].v=q[head].v;} } } if(big[w]==1&&small[w]==0){ans++;} if(big[w]==0&&small[w]==1){bns++;} if(big[w]==0&&small[w]==0){ans++,bns++;} } } cout<<ans<<‘ ‘<<bns<<endl; return 0; }
这题看上去好像蛮简单的...但是打了近两个小时...
好吧其实是因为打得时候并没有什么思路...
所以打了3个版本..
原本想先用dfs查一下有多少个环(因为觉得bfs查环加判断会矛盾(hao ba jiu shi zi ji tai ruo))....
dfs打好以后突然发现bfs并不矛盾.....
然后danteng的是方向数组打错了...瞪了大半天才查出来...
还有一点值得注意的是..continue 是可以执行for的后缀操作的..
嗯..就这些
关于用BFS求环的数量
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。