abinash_hstu

BFS 2D Grid aka Floodfill

Jan 16th, 2016
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<queue>
  5. #include<utility>
  6. #define mp make_pair
  7. #define x first
  8. #define y second
  9. #define D 4
  10. using namespace std;
  11.  
  12. typedef pair<int, int> pii;
  13.  
  14. int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 direction
  15. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  16. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight direction
  17. int d[100][100],R,C;
  18. void BFS2D(int x,int y)
  19. {
  20.     int gc,gr;
  21.     memset(d,-1,sizeof(d));
  22.     queue<pii>Q;
  23.     Q.push(mp(x,y));
  24.     d[x][y]=0;
  25.     while(!Q.empty())
  26.     {
  27.         pii u=Q.front();
  28.         Q.pop();
  29.         for(int i=0; i<D; i++)
  30.         {
  31.             gr=u.x+dx[i];
  32.             gc=u.y+dy[i];
  33.             if(gr>=0&&gr<R&&gc>=0&&gc<C&&d[gr][gc]==-1)
  34.             {
  35.                 Q.push(mp(gr,gc));
  36.                 d[gr][gc]=d[u.x][u.y]+1;
  37.             }
  38.         }
  39.     }
  40. }
  41. int main()
  42. {
  43.     int x,y,i,j;
  44.     scanf("%d%d",&R,&C);//2D Grid Size
  45.     scanf("%d%d",&x,&y);//source position
  46.     BFS2D(x,y);
  47.     for(i=0;i<R;++i){
  48.         for(j=0;j<C;++j)
  49.           printf("%2d ",d[i][j]);
  50.         printf("\n");
  51.     }
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment