Advertisement
Korotkodul

N5 5

Oct 25th, 2022
738
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int, int>
  11. #define pb(x) push_back(x)
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v) {
  17.     for (auto x : v) cout << x << ' ';
  18.     cout << "\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v) {
  22.     for (auto x : v) cout << x << ' ';
  23.     cout << "\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v) {
  28.     for (auto x : v) cv(x);
  29.     cout << "\n";
  30. }
  31.  
  32. void cvb(vector <bool> v) {
  33.     for (bool x : v) cout << x << ' ';
  34.     cout << "\n";
  35. }
  36.  
  37. void cvs(vector <string>  v) {
  38.     for (auto a : v) {
  39.         cout << a << "\n";
  40.     }
  41. }
  42.  
  43. void cvp(vector <pii> a) {
  44.     for (auto p : a) {
  45.         cout << p.first << ' ' << p.second << "\n";
  46.     }
  47.     cout << "\n";
  48. }
  49.  
  50. bool sh = 1;
  51.  
  52. void cvch(vector <vector <char> > a) {
  53.     for (auto v: a) {
  54.         for (auto i: v) {
  55.             cout << i;
  56.         } cout << "\n";
  57.     } cout << "\n";
  58. }
  59.  
  60.  
  61. vector <vector <bool> > was;
  62.  
  63.  
  64. int n, m, inf = 2e9;
  65.  
  66.  
  67. vector <vector <int> > mtr;
  68.  
  69. struct rct {
  70.     int x1, x2, y1, y2;
  71.     void upd(int i, int j, int n, int m) {
  72.         int yi = n - 1 - i;
  73.         int xj = j;
  74.         if (sh) {
  75.             //cout << "i j = " << i << ' ' << j << "\n";
  76.             //cout << "yi xj = " << yi << ' ' << xj << "\n";
  77.         }
  78.         x1 = min(x1, xj);
  79.         x2 = max(x2, xj);
  80.         y1 = min(y1, yi);
  81.         y2 = max(y2, yi);
  82.     }
  83.  
  84.     void see() {
  85.         cout << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << "\n";
  86.     }
  87. };
  88.  
  89. rct now; //for dfs
  90.  
  91. bool canto(int i, int j) {
  92.     return i >= 0 && i < n && j >= 0 && j < m && mtr[i][j] == 1 && !was[i][j];
  93. }
  94.  
  95. void dfs(int i, int j) {
  96.     was[i][j] = 1;
  97.     now.upd(i, j, n, m);
  98.     vector <int> di = {-1, 0, 1, 0}, dj = {0, 1, 0, -1};
  99.     for (int to = 0; to < 4; ++to) {
  100.         int toi = i + di[to], toj = j + dj[to];
  101.         if (canto(toi, toj)) {
  102.             dfs(toi, toj);
  103.         }
  104.     }
  105. }
  106.  
  107. rct getrec(vector <vector <int> > a) {
  108.     rct res = {inf, -1, inf, -1};
  109.     if (sh) {
  110.         cout << "GETREC\n";
  111.     }
  112.     for (int i = 0; i < n; ++i) {
  113.         for (int j = 0; j < n; ++j) {
  114.             if (a[i][j] == 0) {
  115.                 res.upd(i, j, n, n);
  116.             }
  117.         }
  118.         if (sh) {
  119.             //cout << "I = " << i << "\n";
  120.             //cout << "res\n";
  121.             //res.see();
  122.             //cout << "\n";
  123.         }
  124.     }
  125.     return res;
  126. }
  127.  
  128. bool in(rct rec, int i, int j) {
  129.     int xj = j;
  130.     int yi = n - 1 - i;
  131.     bool r =  xj >= rec.x1
  132.     && xj <= rec.x2
  133.     && yi >= rec.y1
  134.     && yi <= rec.y2;
  135.     if (r == 1) {
  136.         cout << "\nCHECK IN\n";
  137.         cout << "i j = " << i << ' ' << j << "\n";
  138.         cout << "rec\n";
  139.         rec.see();
  140.         cout << "yi xj = " << yi << ' ' << xj << "\n";
  141.     }
  142.  
  143.     return r;
  144. }
  145.  
  146. bool noout(vector <vector <int> > a, int clr, rct rec) {
  147.     //n m global ok???
  148.     for (int i = 0; i < n; ++i) {
  149.         for (int j = 0; j < m; ++j) {
  150.             if (a[i][j] == clr) {
  151.                 if (!in(rec, i, j)) {
  152.                     return 0;
  153.                 }
  154.             }
  155.         }
  156.     }
  157.     return 1;
  158. }
  159. bool gen = 0;
  160.  
  161.  
  162. void getmtr(vector <vector <int> > a) {
  163.     rct rec = getrec(a);
  164.     if (sh) {
  165.         cout << "rec\n";
  166.         rec.see();
  167.     }
  168.     int lx = rec.x2 - rec.x1 + 1;
  169.     int ly = rec.y2 - rec.y1 + 1;
  170.  
  171.     mtr.resize(ly, vector <int> (lx, 99));
  172.     int fri = n - rec.y2;
  173.     int toi = fri + ly - 1;
  174.     fri--;
  175.     toi--;
  176.     int frj = rec.x1;
  177.     int toj = rec.x2;
  178.  
  179.     if (sh) {
  180.         cout << "fri toi = " << fri << ' ' << toi << "\n";
  181.         cout << "frj toj = " << frj << ' ' << toj << "\n";
  182.     }
  183.  
  184.     int x = -1;
  185.     for (int i = fri; i <= toi; ++i) {
  186.         x++;
  187.         int y = -1;
  188.         for (int j = frj; j <= toj; ++j) {
  189.             y++;
  190.             mtr[x][y] = a[i][j];
  191.         }
  192.     }
  193.     n = ly;
  194.     m = lx;
  195.     //new, n m for needed matrix
  196. }
  197.  
  198.  
  199. /*
  200. 13
  201. .............
  202. .............
  203. .............
  204. ..#######....
  205. ..#######....
  206. ..###........
  207. ..###........
  208. ..###........
  209. ..###........
  210. ..#######....
  211. ..#######....
  212. .............
  213. .............
  214. */
  215.  
  216. bool Csee = 0;
  217. bool Hsee = 0;
  218. /*
  219. 10
  220. ..........
  221. ..##...#..
  222. ..##...#..
  223. ..##...#..
  224. ..##...#..
  225. ..######..
  226. ..##...#..
  227. ..##...#..
  228. ..........
  229. ..........
  230.  
  231. 10
  232. ..........
  233. ..##...#..
  234. ..##...#..
  235. ..##...#..
  236. ..##...#..
  237. ..######..
  238. ..##...#..
  239. ..##...#..
  240. ..........
  241. ..........
  242. */
  243.  
  244. bool cmp(rct a, rct b) {
  245.     return a.y1 < b.y1 || a.y1 == b.y1 && a.x1 < b.x1;
  246.     //a - left down, b - right up
  247. }
  248.  
  249. bool O(rct a, rct b) {
  250.     if (sh) {
  251.         cout << "a b\n";
  252.         a.see();
  253.         b.see();
  254.     }
  255.     bool ox = b.x1 > a.x1 && b.x2 < a.x2;
  256.     bool oy = b.y1 > a.y1 && b.y2 < a.y2;
  257.     return ox && oy;
  258. }
  259.  
  260. bool C(rct a, rct b) {
  261.     bool ox = b.x1 > a.x1 && b.x2 == a.x2;
  262.     bool oy = b.y1 > a.y1
  263.     && b.y2 < a.y2;
  264.     return ox && oy;
  265. }
  266.  
  267. bool L(rct a, rct b) {
  268.     bool ox = b.x1 > a.x1
  269.     && b.x2 == a.x2;
  270.     bool oy = b.y1 > a.y1
  271.     && b.y2 == a.y2;
  272.     return ox && oy;
  273. }
  274.  
  275. void OCL(rct a, rct b) {
  276.     if (sh) {
  277.         cout << "OCL\n";
  278.     }
  279.     if (O(a, b)) {
  280.         cout << 'O';
  281.         exit(0);
  282.     }
  283.     if (C(a, b)) {
  284.         cout << 'C';
  285.         exit(0);
  286.     }
  287.     if (L(a, b)) {
  288.         cout << 'L';
  289.         exit(0);
  290.     }
  291.     cout << 'X';
  292.     exit(0);
  293. }
  294.  
  295.  
  296. void HP(rct a, rct b, rct c) {
  297.  
  298. }
  299. /*
  300. 2
  301. #.
  302. ##
  303.  
  304. 3
  305. ###
  306. #.#
  307. ###
  308.  
  309.  
  310. 5
  311. #####
  312. #..##
  313. #..##
  314. #####
  315. #####
  316. */
  317.  
  318.  
  319. int main() {
  320.     /*ios::sync_with_stdio(0);
  321.     cin.tie(0);
  322.     cout.tie(0);*/
  323.     //cin >> n;
  324.     //m = n;
  325.     if (Csee) {
  326.         vector <vector <char> > raw(13, vector <char> (13, '.'));
  327.         for (int i = 3; i <= 4; ++i) {
  328.             for (int j = 2; j <= 8; ++j) {
  329.                 raw[i][j] = '#';
  330.             }
  331.         }
  332.         for (int i = 5; i <= 8; ++i) {
  333.             for (int j = 2; j <= 4; ++j) {
  334.                 raw[i][j] = '#';
  335.             }
  336.         }
  337.         for (int i = 9; i <= 10; ++i) {
  338.             for (int j = 2; j <= 8; ++j) {
  339.                 raw[i][j] = '#';
  340.             }
  341.         }
  342.         cvch(raw);
  343.     }
  344.     if (Hsee) {
  345.         vector <vector <char> > raw(10, vector <char> (10, '.'));
  346.         for (int i = 1; i <= 7; ++i) {
  347.             for (int j = 2; j <= 3; ++j) {
  348.                 raw[i][j] = '#';
  349.             }
  350.             raw[i][7] = '#';
  351.         }
  352.         for (int j = 2; j <= 7; ++j) {
  353.             raw[5][j] = '#';
  354.         }
  355.         cvch(raw);
  356.     }
  357.  
  358.     cin >> n;
  359.     m = n;
  360.     vector <vector <int> > a(n, vector <int> (n, 99));
  361.     for (int i = 0; i < n; ++i) {
  362.         for (int j = 0; j < n; ++j) {
  363.             char k;
  364.             cin >> k;
  365.             if (k == '#') {
  366.                 a[i][j] = 0;
  367.             } else {
  368.                 a[i][j] = 1;
  369.             }
  370.         }
  371.     }
  372.     getmtr(a);
  373.     if (sh) {
  374.         cout << "mtr\n";
  375.         cvv(mtr);
  376.         cout << "n m = " << n << ' ' <<  m << "\n";
  377.     }
  378.     was.assign(n, vector <bool> (m, 0));
  379.     vector <rct> alrec;
  380.     for (int i = 0; i < n; ++i) {
  381.         for (int j = 0; j < m; ++j) {
  382.             if (mtr[i][j] == 1 && !was[i][j]) {
  383.                 now = {inf, -1, inf, -1};
  384.                 dfs(i, j);
  385.                 alrec.push_back(now);
  386.             }
  387.         }
  388.     }
  389.  
  390.     if (sh) {
  391.         cout << "alrec\n";
  392.         for (auto r: alrec) {
  393.             r.see();
  394.         }
  395.     }
  396.  
  397.     for (int i = 0; i < n; ++i) {
  398.         for (int j = 0; j < m; ++j) {
  399.             for (auto rec: alrec) {
  400.                 if (mtr[i][j] != 1 && in(rec, i, j)) {
  401.                     if (sh) {
  402.                         cout << "bad i j = " << i << ' ' << j << "\n";
  403.                     }
  404.                     cout << 'X';
  405.                     exit(0);
  406.                 }
  407.             }
  408.         }
  409.     }
  410.  
  411.     int recsz = alrec.size();
  412.     if (recsz > 2) {
  413.         cout << 'X';
  414.         exit(0);
  415.     }
  416.     if (recsz == 0) {
  417.         cout << 'I';
  418.         exit(0);
  419.     }
  420.     sort(alrec.begin(), alrec.end(), cmp);
  421.     if (sh) {
  422.         cout << "alrec sorted\n";
  423.         for (auto r: alrec) {
  424.             r.see();
  425.         }
  426.     }
  427.     if (recsz == 1) {
  428.         OCL({0, m - 1, 0, n - 1}, alrec[0]);
  429.         exit(0);
  430.     }
  431.     HP({0, m - 1, 0, n - 1}, alrec[0], alrec[1]);
  432.  
  433. }
  434.  
  435. /*
  436.  
  437. 4
  438. .##.
  439. .#..
  440. .##.
  441. ....
  442.  
  443. 4
  444. .##.
  445. .##.
  446. .##.
  447. ....
  448.  
  449. 2
  450. #.
  451. ##
  452.  
  453. 3
  454. ###
  455. #.#
  456. ###
  457.  
  458.  
  459. 13
  460. .............
  461. .............
  462. .............
  463. ..#######....
  464. ..#######....
  465. ..###........
  466. ..###........
  467. ..###........
  468. ..###........
  469. ..#######....
  470. ..#######....
  471. .............
  472. .............
  473.  
  474. 3
  475. ###
  476. #.#
  477. ###
  478.  
  479. /*
  480. 13
  481. .............
  482. .............
  483. .............
  484. ..#######....
  485. ..#######....
  486. ..###........
  487. ..###.#......
  488. ..###........
  489. ..###........
  490. ..#######....
  491. ..#######....
  492. .............
  493. .............
  494. */
  495.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement