Advertisement
i_love_rao_khushboo

Untitled

Aug 8th, 2022
751
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.04 KB | None | 0 0
  1. /* # Flood Fill Algorithm is a simple variant of BFS or DFS that can be used to label(colour) the various
  2.      connected components present in a graph.
  3.    # It is generally performed on implicit graphs(2D matrices).
  4.    # Starting from a particular cell we call DFS on the neighbouring cells to colour them.
  5.      Neighbours can be '4' (up, down, left, right) or '8' if include diagonals also.
  6. */
  7.  
  8. #include<bits/stdc++.h>
  9. using namespace std;
  10.  
  11. void print(vector<vector<char>> &v, int row, int col)
  12. {
  13.     for(int i=0; i<row; i++){
  14.         for(int j=0; j<col; j++){
  15.             cout<<v[i][j];
  16.         }
  17.        
  18.         cout<<"\n";
  19.     }
  20. }
  21.  
  22. // North, East, South, West of the current cell
  23. vector<int> dx{-1, 0, 1, 0};
  24. vector<int> dy{0, 1, 0, -1};
  25.  
  26. void floodFill(vector<vector<char>> &v, int i, int j, char c, char r, int row, int col)
  27. {
  28.     // base condition - matrix bounds
  29.     if(i<0 || i>=row || j<0 || j>=col) return;
  30.        
  31.     // figure boundary condition
  32.     if(v[i][j]!=c) return;
  33.    
  34.     // replacing the current cell
  35.     v[i][j]=r;
  36.     for(int k=0; k<4; k++)
  37.     {
  38.         // apply floodFill on the neighbouring cells recursively
  39.         floodFill(v, i+dx[k], j+dy[k], c, r, row, col);
  40.     }
  41. }
  42.  
  43. int main()
  44. {
  45.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  46.     srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  47.  
  48.     // #rows & #columns in the input matrix
  49.     int row, col; cin>>row>>col;
  50.     vector<vector<char>> v(row, vector<char>(col));
  51.     for(int i=0; i<row; i++){
  52.         for(int j=0; j<col; j++){
  53.             cin>>v[i][j];
  54.         }
  55.     }
  56.    
  57.     // co-ordinates from where to initiate the algo
  58.     int x, y;  cin>>x>>y;
  59.     // character which is to be replace by some other character
  60.     char curr, replacement; cin>>curr>>replacement;
  61.    
  62.     // no need of traversal if curr==replacement
  63.     if(curr!=replacement)
  64.         floodFill(v, x, y, curr, replacement, row, col);
  65.    
  66.     print(v, row, col);
  67.  
  68.     return 0;
  69. }
  70.  
  71. /*Sample I/P:
  72.  
  73. 15 30
  74. ..............................
  75. ...............#####..........
  76. ...............#...#..........
  77. .......#########...#######....
  78. ......###......######....###..
  79. .....##....................##.
  80. ....##......................##
  81. .....##....................##.
  82. ......##..................##..
  83. .......##................##...
  84. ........##..............##....
  85. .........###...........###....
  86. ...........####......####.....
  87. .............##########.......
  88. .........A..P..P..L..E........
  89. 8 20
  90. . K
  91.  
  92. SAMPLE O/P:
  93. ..............................
  94. ...............#####..........
  95. ...............#...#..........
  96. .......#########...#######....
  97. ......###KKKKKK######KKKK###..
  98. .....##KKKKKKKKKKKKKKKKKKKK##.
  99. ....##KKKKKKKKKKKKKKKKKKKKKK##
  100. .....##KKKKKKKKKKKKKKKKKKKK##.
  101. ......##KKKKKKKKKKKKKKKKKK##..
  102. .......##KKKKKKKKKKKKKKKK##...
  103. ........##KKKKKKKKKKKKKK##....
  104. .........###KKKKKKKKKKK###....
  105. ...........####KKKKKK####.....
  106. .............##########.......
  107. .........A..P..P..L..E........
  108.  
  109. */
  110.  
  111. // FOR IMPLEMENTATION USING "BFS" REFER: https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement