Advertisement
El_GEMMY

floodFill (Assiut)

Oct 13th, 2022
721
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.72 KB | None | 0 0
  1. // Those who cannot remember the past are
  2. // condemned to repeat it (use DP -_-)
  3. // - George Santayana
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8.  
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11.  
  12. #define all(v) v.begin(), v.end()
  13. #define rall(v) v.rbegin(), v.rend()
  14. #define ll long long
  15. #define ull unsigned long long
  16. #define MOD 1000000007
  17. #define PI acos(-1)
  18. #define ceil(a, b) (((a) / (b)) + ((a) % (b) ? 1 : 0))
  19. #define imin INT_MIN
  20. #define imax INT_MAX
  21. #define llmax LLONG_MAX
  22. #define llmin LLONG_MIN
  23. #define inf 2000000000
  24. #define nl '\n'
  25. #define ppcnt __builtin_popcount
  26. #define ppcntll __builtin_popcountll
  27. #define clz __builtin_clz
  28. #define clzll __builtin_clzll
  29. #define ctz __builtin_ctz
  30. #define ctzll __builtin_ctzll
  31. #define modulo(a, b, mod) ((((a) % (mod)) * ((b) % (mod))) % (mod))
  32. #define cnte(v, x) count(all(v), (x))
  33. #define mine(v) min_element(all(v))
  34. #define maxe(v) max_element(all(v))
  35. #define updmin(a, b) a = min(a, b)
  36. #define updmax(a, b) a = max(a, b)
  37. #define findmod(x, m) x = ((x) % (m) + (m)) % m
  38. #define getmod(x, m) ((x) % (m) + (m)) % (m)
  39. #define debug(x) cout << "x: " << (x) << nl;
  40. #define debug2(x, y) cout << "x: " << (x) << " y: " << y << nl;
  41. #define ordered_set tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_int_update>
  42. #define ordered_map tree<int, int, less<>, rb_tree_tag, tree_order_statistics_int_update>
  43.  
  44. //vector<int> dx = {0, 0, 1, -1, 1, 1, -1, -1}, dy = {1, -1, 0, 0, 1, -1, 1, -1};
  45. vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
  46.  
  47. template<typename T = int>
  48. istream &operator>>(istream &in, vector<pair<int, int>> &v) {
  49.     for (auto &[x, y]: v) in >> x >> y;
  50.     return in;
  51. }
  52.  
  53. template<typename T = int>
  54. istream &operator>>(istream &in, vector<T> &v) {
  55.     for (T &i: v) in >> i;
  56.     return in;
  57. }
  58.  
  59. template<typename T = int>
  60. ostream &operator<<(ostream &out, const vector<T> &v) {
  61.     for (const T &x: v)
  62.         out << x << ' ';
  63.     return out;
  64. }
  65.  
  66. template<typename T = pair<int, int>>
  67. ostream &operator<<(ostream &out, const vector<pair<int, int>> &v) {
  68.     for (auto &[x, y]: v) {
  69.         out << x << ' ' << y << nl;
  70.     }
  71.     return out;
  72. }
  73.  
  74. void Start_Crushing() {
  75.     ios_base::sync_with_stdio(false);
  76.     cin.tie(nullptr);
  77.     cout.tie(nullptr);
  78. #ifndef ONLINE_JUDGE
  79.     freopen("input.txt", "r", stdin);
  80.     freopen("output.txt", "w", stdout);
  81. #endif
  82. }
  83.  
  84. void solve(){
  85.     int n, m; cin >> n >> m;
  86.  
  87.     auto grid = vector<vector<char>>(n, vector<char>(m));
  88.     cin >> grid;
  89.  
  90.     vector<vector<bool>> vis(n, vector<bool>(m, false));
  91.  
  92.     auto valid = [&](int x, int y){
  93.         return x >= 0 and y >= 0 and x < n and y < m and grid[x][y] != '*' and not vis[x][y];
  94.     };
  95.  
  96.     function<int(int, int)> find_path = [&](int x, int y){
  97.         vis[x][y] = true;
  98.         int ret = 1;
  99.  
  100.         for(int d = 0; d < 4; d++){
  101.             int new_x = x + dx[d], new_y = y + dy[d];
  102.             if(valid(new_x, new_y))
  103.                 ret += find_path(new_x, new_y);
  104.         }
  105.         return ret;
  106.     };
  107.  
  108.     int x, y; cin >> x >> y;
  109.     cout << find_path(--x, --y);
  110. }
  111.  
  112. void set_file(string &file_name) {
  113.     freopen((file_name + ".in").c_str(), "r", stdin);
  114.     freopen((file_name + ".out").c_str(), "w", stdout);
  115. }
  116.  
  117. int main() {
  118.     Start_Crushing();
  119.  
  120. //    string file_name = "avia";
  121. //    set_file(file_name);
  122.     int t = 1;
  123. //    /*Multiple test cases?*/ cin >> t;
  124.     while (t--) {
  125.         solve();
  126.         if (!t)
  127.             break;
  128.         cout << nl;
  129.     }
  130.  
  131. //    for(int tc = 1; tc <= t; tc++){
  132. ////        cout << "Case " << tc << ": ";
  133. //        solve();
  134. //        if(tc != t)
  135. //            cout << nl;
  136. //    }
  137.  
  138.     return 0;
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement