Advertisement
Guest User

bfs sample problem

a guest
May 30th, 2015
265
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.16 KB | None | 0 0
  1. #include<vector>
  2. #include<stdio.h>
  3. #include<iostream>
  4. #include<queue>
  5.  
  6. using namespace std;
  7.  
  8. char grid[1010][1010];
  9. int vis[1010][1010];
  10. int n,m;
  11. int dx[4]={0,0,1,-1};
  12. int dy[4]={-1,1,0,0};
  13.  
  14. void bfs(int srcx,int srcy)
  15. {
  16. int i,vx,vy,ux,uy;
  17. vis[srcx][srcy]=1;
  18.  
  19. queue< pair<int,int> > Q;
  20. Q.push( make_pair(srcx,srcy) );
  21. while(!Q.empty())
  22. {
  23. ux=Q.front().first;
  24. uy=Q.front().second;
  25. Q.pop();
  26.  
  27. for(int k=0;k<4;k++)
  28. {
  29. vx=ux+dx[k];
  30. vy=uy+dy[k];
  31. if(vx>=0 && vx<n && vy>=0 && vy<m && vis[vx][vy]==0)
  32. {
  33. vis[vx][vy]=vis[ux][uy]+1;
  34. Q.push(make_pair(vx,vy));
  35. }
  36. }
  37. }
  38. }
  39.  
  40.  
  41. int main()
  42. {
  43.  
  44.  
  45. freopen("in.txt","r",stdin);
  46. int i,j,k,i2,j2;
  47. cin>>n;
  48. n=2*n-1;
  49. m=n;
  50. bfs(n/2,n/2);
  51.  
  52.  
  53. for(i=0;i<n;i++)
  54. {
  55. for(j=0;j<m;j++)
  56. {
  57. cout<<vis[i][j];
  58. }
  59. cout<<endl;
  60. }
  61.  
  62. return 0;
  63. }
  64. ///dfs http://pastebin.com/T0GyaHQX
  65. ///shortest path using dfs http://pastebin.com/HEtHBfrR
  66. ///bfs http://pastebin.com/bAaeTuCm
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement