Advertisement
MiinaMagdy

11094 - Continents

Mar 15th, 2023
541
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.95 KB | None | 0 0
  1. /*
  2. +---------------------------------------------+
  3. |                                             |
  4. |  Copytright, MinaMagdy, 02/03/2023 (16:34)  |
  5. |                                             |
  6. +---------------------------------------------+
  7. */
  8. /*
  9.         .@@@@@@@@   @@@                                              @@       @@
  10.     ,@@@@@@     @@ .@@@      @@    @@@        @@@%@@@@.   @@@        @@  @@  @@@@/      @@@
  11.     /& @@@@    @@@ *@@@     @@@#  @@@&@@@    @@@@@@@#&@@ @@@%&,      @@ @@@@  @@@@    @@@&
  12.         @@@  .@@@   /@%@     @@@  @@@@   @@& .@@@         @@&&&@      @@ @@@@  >@@@@ @@@@
  13.         %@@@@@@&     /&&&     %@&  @&@     @& @&@&         &&@#%@%.   &@@ &@&#   %@@@@@@
  14.         @@@@@        /@&%@%&@@@&@  @&&    ,@@ @@&&@@&@@@   &@@ /@@&/  @@, @@@/    %@@@@
  15.         @@@.         *@@@@#,  @@@  @@@   ,@@  @@@.         @@@   @@@@@@@  %@@/   @@@@@@%
  16.         @@@          *@@%     @@@   @@@@@@#    @@@@@@@@@@  @@@    ,@@@@    @@& .@@@  @@@@
  17.         &@@,          @@%      @@                          @@@                 @@      @@@
  18.                                                             &*
  19. */
  20. #include <bits/stdc++.h>
  21. #include <ext/pb_ds/assoc_container.hpp>
  22. #include <ext/pb_ds/tree_policy.hpp>
  23. #include <ext/rope>
  24.  
  25. using namespace __gnu_cxx;
  26. using namespace std;
  27. using namespace __gnu_pbds;
  28. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  29. #define multi_ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
  30. #define ceil(w, m) (((w) / (m)) + ((w) % (m) ? 1 : 0))
  31. #define endl "\n"
  32. #define NumOfDig(w) log10(w) + 1
  33. #define MOD 1000000007
  34. #define INF 2000000000
  35. #define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
  36. #define all(s) s.begin(), s.end()
  37. #define rall(s) s.rbegin(), s.rend()
  38. #define sz(x) int(x.size())
  39. #define init(x, c) memset(x, c, sizeof(x))
  40. #define getlineCh(s, c) getline(cin >> ws, s, c)
  41. #define TC int testcases = 1; cin >> testcases; for (ll test = 1; test <= testcases; test++)
  42. // --------------------------->         GEOMETRY         <---------------------------    
  43. #define EPS 1e-15
  44. #define PI acos(-1)
  45. #define X real()
  46. #define Y imag()
  47. #define angle(a) atan2(a.Y, a.X)
  48. #define vec(a, b) point((b) - (a))
  49. #define length(a) hypot(a.Y, a.X)
  50. #define normalize(a) (a) / length(a)
  51. #define dot_prod(a, b) real(conj(a) * (b))
  52. #define cross_prod(a, b) imag(conj(a) * (b))
  53. #define lengthSqr(p) dot_prod(p, p)
  54. #define rotateO(p, ang) p * exp(point(0, ang))
  55. #define rotateA(p, about, ang) rotateO(vec((about), (p)), ang) + (about)
  56. #define reflicatO(v, m) conj(v / m) * m
  57. #define reflicatA(v, about, m) conj(vec(about, v) / vec(about, m)) * vec(about, m) + about
  58.  
  59. typedef long long ll;
  60. typedef long double ld;
  61. typedef unsigned long long ull;
  62. typedef complex<double> point;
  63.  
  64. /**
  65.  * @author MiinaMagdy
  66.  * @remark Time limit - memory limit (EFFICIENCY)
  67.  * @remark (OVERFLOW) long long
  68.  * @remark freopen() file
  69.  * @remark (CORNER) test case
  70.  * @remark division by (ZERO) || Out of array's (RANGE)
  71.  * @remark use logarithm if you want to compare two products
  72.  * @remark Brute Force means try all possible solutions remember (MAXPOINT - CodeChef)
  73.  * @remark '/0' takes all input in getline string
  74.  * @remark pass vector by reference to avoid tle
  75.  * @remark assign vector instade of resize to avoid rte
  76.  */
  77.  
  78. void phoenix()
  79. {
  80.     ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  81.     #ifndef ONLINE_JUDGE
  82.         freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  83.     #endif
  84.     Time
  85. }
  86.  
  87. double fix_360(double radian) {
  88.     while (radian < 0) radian += 2 * PI;
  89.     while (radian > 2 * PI) radian -= 2 * PI;
  90.     return radian;
  91. }
  92.  
  93. double to_degree(double radian) {
  94.     return radian * 180 / PI;
  95. }
  96.  
  97. bool is_collinear(point a, point b, point c) {
  98.     return fabs(cross_prod(b - a, c - a)) <= EPS;
  99. }
  100.  
  101. int dcmp(double a, double b) {
  102.     return fabs(a - b) <= EPS ? 0 : (a > b ? 1 : -1);
  103. }
  104.  
  105. bool on_ray(point a, point b, point c) {
  106.     if (!is_collinear(a, b, c)) {
  107.         return false;
  108.     }
  109.     return dcmp(dot_prod(b - a, c - a), 0) == 1;
  110. }
  111.  
  112. // closest distance from point c to line a-b
  113. double distToLine(point a, point b, point c) {
  114.     double dist = cross_prod(vec(a, b), vec(a, c)) / length(vec(a, b));
  115.     return fabs(dist);
  116. }
  117.  
  118. // distance from point p2 to segment p0-p1
  119. ld distToSegment(point p0, point p1, point p2) {
  120.     double d1, d2;
  121.     point v1 = p1 - p0, v2 = p2 - p0;
  122.     if ((d1 = dot_prod(v1, v2)) <= 0) {
  123.         return length(vec(p0, p2));
  124.     }
  125.     if ((d2 = dot_prod(v1, v1)) <= d1) {
  126.         return length(vec(p2, p1));
  127.     }
  128.  
  129.     double t = d1 / d2;
  130.     return length(vec(p0 + t * v1, p2));
  131. }
  132.  
  133. bool intersectSegments(point a, point b, point c, point d, point & intersect) {
  134.   double d1 = cross_prod(a - b, d - c), d2 = cross_prod(a - c, d - c), d3 = cross_prod(a - b, a - c);
  135.   if (fabs(d1) < EPS)
  136.     return false;  // Parllel || identical
  137.  
  138.   double t1 = d2 / d1, t2 = d3 / d1;
  139.   intersect = a + (b - a) * t1;
  140.  
  141.   if (t1 < -EPS || t2 < -EPS || t2 > 1 + EPS)
  142.     return false;  //e.g ab is ray, cd is segment ... change to whatever
  143.   return true;
  144. }
  145.  
  146. // pair<double, point> findCircle(point a, point b, point c) {
  147. //     point v1 = b - a, v2 = b - c;
  148. //     point m1 = (a + b) * 0.5, m2 = (b + c) * 0.5;
  149. //     point pv1 = point(v1.imag(), -v1.real()), pv2 = point(v2.imag(), -v2.real());
  150. //     point end1 = m1 + pv1, end2 = m2 + pv2, center;
  151. //     intersectSegments(m1, end1, m2, end2, center);
  152. //     return {length(vec(center, a)), center};
  153. // }
  154.  
  155. bool cin_point(point &p) {
  156.     double x = -INF, y = -INF;
  157.     cin >> x >> y;
  158.     p = {x, y};
  159.     return x != -INF or y != -INF;
  160. }
  161.  
  162. int n, m;
  163. vector<vector<char>> grid;
  164.  
  165. char land;
  166.  
  167. bool valid(int i, int j) {
  168.     return 0 <= i && i < n && 0 <= j && j < m && grid[i][j] == land;
  169. }
  170.  
  171. int floodfill(int i, int j) {
  172.     if (!valid(i, j)) return 0;
  173.     grid[i][j] = land^1;
  174.     return 1 + floodfill(i + 1, j) + floodfill(i - 1, j) + floodfill(i, (j + 1) % m) + floodfill(i, (j - 1 + m) % m);
  175. }
  176.  
  177. int main(void)
  178. {
  179.     phoenix();
  180.     int testcase = 1;
  181.     // cin >> testcase;
  182.     while (testcase)
  183.     {
  184.         cin >> n >> m;
  185.         if (n == 0 && m == 0) break;
  186.         grid.resize(n, vector<char>(m));
  187.         for (int i = 0; i < n; i++) {
  188.             for (int j = 0; j < m; j++) {
  189.                 cin >> grid[i][j];
  190.             }
  191.         }
  192.         int x, y;
  193.         cin >> x >> y;
  194.         land = grid[x][y];
  195.         vector<int> ans;
  196.         ans.push_back(floodfill(x, y));
  197.         for (int i = 0; i < n; i++) {
  198.             for (int j = 0; j < m; j++) {
  199.                 if (grid[i][j] == land) {
  200.                     ans.push_back(floodfill(i, j));
  201.                 }
  202.             }
  203.         }
  204.         sort(ans.begin() + 1, ans.end());
  205.         if (sz(ans) < 2) ans.push_back(0);
  206.         cout << ans.back() << endl;
  207.         n = 0, m = 0;
  208.     }
  209.     return 0;
  210. }
Tags: C++ UVA
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement