fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4. #include <tuple>
  5. #include <unordered_set>
  6.  
  7. using namespace std;
  8.  
  9. struct Result
  10. {
  11.     unsigned long Border;
  12.     unsigned long Rperimeter;
  13.     unsigned long Fperimeter;
  14. };
  15.  
  16. // Utility class
  17. class Task120
  18. {
  19. protected:
  20.     const vector<string>& Field;
  21.     const unsigned long  Width;
  22.     const unsigned long  Height;
  23.  
  24. protected:
  25.  
  26.     unsigned int IsEnemy(int i, int j, char type)
  27.     {
  28.         if (i >=0 && i < Height && j >= 0 && j < Width) {
  29.             return (Field[i][j] != type ? 1 : 0);
  30.         }
  31.  
  32.         return 0;
  33.     }
  34.  
  35.     unsigned int OuterCount(int i, int j)
  36.     {
  37.         return
  38.             (unsigned int)(i == 0) +
  39.             (unsigned int)(j == 0) +
  40.             (unsigned int)(i == Height-1) +
  41.             (unsigned int)(j == Width-1);
  42.     }
  43.  
  44. public:
  45.     Task120(const vector<string>& field)
  46.         : Field(field)
  47.         , Width(field[0].size())
  48.         , Height(field.size())
  49.     {}
  50.  
  51.     virtual Result solve() = 0;
  52. };
  53.  
  54. // Простое решение за O(N^2) . Посещаем все ячейки и для каждой ячейки
  55. // отмечаем принадлежит ли она периметру и/или линии фронта. Естественно
  56. // учитываем сколько граней отвечают этим условиям. Дальше - простая арифметика
  57. class Task120_Quadratic : public Task120
  58. {
  59. public:
  60.     Task120_Quadratic(const vector<string>& field)
  61.         : Task120(field)
  62.     {}
  63.  
  64.     Result solve() override
  65.     {
  66.         unsigned long  border = 0, outer = 0;
  67.         char type = Field[0][0];
  68.  
  69.         for (int i = 0; i < Height; ++i) {
  70.             for (int j = 0; j < Width; ++j) {
  71.                 if (Field[i][j] == type) {
  72.                     outer += OuterCount(i, j);
  73.                     border +=
  74.                         IsEnemy(i - 1, j, Field[i][j]) +
  75.                         IsEnemy(i + 1, j, Field[i][j]) +
  76.                         IsEnemy(i, j - 1, Field[i][j]) +
  77.                         IsEnemy(i, j + 1, Field[i][j]);
  78.                 }
  79.             }
  80.         }
  81.  
  82.         const auto total = 2*(Width + Height);
  83.  
  84.         if (type == 'R') {
  85.             return {border, outer + border, (total - outer) + border};
  86.         } else {
  87.             return {border, (total - outer) + border , outer + border};
  88.         }
  89.  
  90.     }
  91. };
  92.  
  93.  
  94. struct PairHash
  95. {
  96.     size_t operator ()(const pair<int,int>& p) const
  97.     {
  98.         return (unsigned int)p.first * 1000 + (unsigned int)p.second;
  99.     }
  100. };
  101.  
  102. // Чуть более сложное, но и потенциально более быстрое решение. Можно заметить, что
  103. // если линия фронта пересекает поле от грани до грани то ее длина вполне может
  104. // быть линейной. Во всяком случае в предыдущем решении мы просматривали точки которые
  105. // однозначно не могли нас заинтересовать (внутренние точки областей). Было бы хорошо если
  106. // алгоритм старался следовать границе между областями и просматривал бы только точки на линии фронта
  107. // или точки принадлежащие только периметру. Собственно мы сдесь это и делаем. Начинаем с точки (0,0)
  108. // т.к она точно нас интересует (принадлежит периметру) и используя очередь "интересных вершин" вдоль
  109. // периметра и линии фронта.
  110. // Тут есть один вырожденный случай. Это когда одна область полностью лежит внутри другой ("котел","бублик").
  111. // Очевидно что в таком случае алгоритм не найдет линию фронта. В этом случае приходится в массиве найти первую
  112. // точку принадлежащию противнику и повторить алгоритм в этой точке (эта точка будет граничной).
  113. // После чего результаты скомпоновать.
  114. // Сложность O(N^2) в худшем случае, но есть подозрение что где-то в среднем он O(n+m)
  115.  
  116. class Task120_Opt : public Task120
  117. {
  118. private:
  119.     unordered_set<pair<int,int>, PairHash> visited;
  120.     unsigned long  border = 0, outer = 0;
  121.  
  122. private:
  123.  
  124.     bool IsOutOfBounds(int i, int j) {
  125.         return
  126.         i < 0 ||
  127.         j < 0 ||
  128.         i >= Height ||
  129.         j >= Width;
  130.     }
  131.  
  132.     bool IsSuitable(int i, int j, char type, unsigned int& b, unsigned int& o)
  133.     {
  134.         if (!IsOutOfBounds(i,j) && Field[i][j] == type && !visited.count(make_pair(i, j))) {
  135.             b = IsEnemy(i-1, j, Field[i][j]) +
  136.                           IsEnemy(i+1, j, Field[i][j]) +
  137.                           IsEnemy(i, j-1, Field[i][j]) +
  138.                           IsEnemy(i, j+1, Field[i][j]);
  139.             o =  OuterCount(i,j);
  140.  
  141.             return true;
  142.         }
  143.         return false;
  144.     }
  145.  
  146.     void TryAdd(std::deque<pair<int,int>>& q, int i, int j, char type)
  147.     {
  148.         unsigned int b = 0;
  149.         unsigned int o = 0;
  150.         if (IsSuitable(i, j, type, b, o)) {
  151.             border += b;
  152.             outer += o;
  153.             q.emplace_back(i, j);
  154.             visited.insert(make_pair(i, j));
  155.         }
  156.     }
  157.  
  158. public:
  159.     Task120_Opt(const vector<string>& field)
  160.         : Task120(field)
  161.     {}
  162.  
  163.  
  164.     Result RunBorderSearch(int i, int j)
  165.     {
  166.         const auto total = 2*(Width+Height);
  167.  
  168.         std::deque<pair<int,int>> q;
  169.  
  170.         q.emplace_back(i,j);
  171.  
  172.         border += IsEnemy(i-1, j, Field[i][j]) +
  173.                   IsEnemy(i+1, j, Field[i][j]) +
  174.                   IsEnemy(i, j-1, Field[i][j]) +
  175.                   IsEnemy(i, j+1, Field[i][j]);
  176.  
  177.         outer +=  OuterCount(i,j);
  178.  
  179.         visited.insert(make_pair(i,j));
  180.  
  181.         auto type = Field[i][j];
  182.  
  183.         while (!q.empty()) {
  184.             int i,j;
  185.             tie<int,int>(i,j) = q.front();
  186.             q.pop_front();
  187.  
  188.             TryAdd(q, i-1, j ,type);
  189.             TryAdd(q, i+1, j, type);
  190.             TryAdd(q, i, j-1, type);
  191.             TryAdd(q, i, j+1, type);
  192.         }
  193.  
  194.         if (type == 'R') {
  195.             return {border, outer + border, (total - outer) + border};
  196.         } else {
  197.             return {border, (total - outer) + border, outer + border};
  198.         }
  199.     }
  200.  
  201.     Result solve()
  202.     {
  203.         auto result = RunBorderSearch(0,0);
  204.  
  205.         if (result.Border == 0) {
  206.             // slow path
  207.  
  208.             int ei = 0,ej = 0;
  209.  
  210.             for (int i = 0; i < Field.size(); ++i) {
  211.                 auto it = Field[i].find(Field[0][0] == 'F' ? 'R' : 'F');
  212.                 if (it != std::string::npos) {
  213.                     ei = i;
  214.                     ej = (int)it;
  215.                     break;
  216.                 }
  217.             }
  218.  
  219.             border = 0;
  220.             outer = 0;
  221.  
  222.             auto result1 = RunBorderSearch(ei, ej);
  223.  
  224.             return {
  225.                 result1.Border,
  226.                 result.Rperimeter + result1.Border,
  227.                 result1.Fperimeter
  228.                 };
  229.         }
  230.  
  231.         return result;
  232.     }
  233. };
  234.  
  235. int main() {
  236.  
  237.     {
  238.         auto result = Task120_Quadratic({"RR","RF"}).solve();
  239.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  240.         result = Task120_Opt({"RR","RF"}).solve();
  241.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  242.     }
  243.  
  244.     {
  245.         auto result = Task120_Quadratic({"RRRRRRR","RRRRRRR","RRRRRRR","RRRFRRR","RRRRRRR","RRRRRRR","RRRRRRR"}).solve();
  246.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  247.         result = Task120_Opt({"RRRRRRR","RRRRRRR","RRRRRRR","RRRFRRR","RRRRRRR","RRRRRRR","RRRRRRR"}).solve();
  248.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  249.     }
  250.  
  251.     {
  252.         auto result = Task120_Quadratic({"FFFFFFF","FFFFFFF","FFFFFFF","FFFRFFF","FFFFFFF","FFFFFFF","FFFFFFF"}).solve();
  253.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  254.         result = Task120_Opt({"FFFFFFF","FFFFFFF","FFFFFFF","FFFRFFF","FFFFFFF","FFFFFFF","FFFFFFF"}).solve();
  255.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  256.     }
  257.  
  258.     {
  259.         auto result = Task120_Quadratic({"FFF","FRF","FRF"}).solve();
  260.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  261.         result = Task120_Opt({"FFF","FRF","FRF"}).solve();
  262.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  263.     }
  264.  
  265.     {
  266.         auto result = Task120_Quadratic({"FFF","FRF","FRF","FRF"}).solve();
  267.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  268.         result = Task120_Opt({"FFF","FRF","FRF","FRF"}).solve();
  269.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  270.     }
  271.  
  272.     {
  273.         auto result = Task120_Quadratic({"FFF","FRF","FRF","FRF","FRF"}).solve();
  274.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  275.         result = Task120_Opt({"FFF","FRF","FRF","FRF","FRF"}).solve();
  276.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  277.     }
  278.  
  279.     {
  280.         auto result = Task120_Quadratic({"FFFFF","FFFFF","FFFFF","FFRFF","FFRFF","FFRFF","FFRFF"}).solve();
  281.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  282.         result = Task120_Opt({"FFFFF","FFFFF","FFFFF","FFRFF","FFRFF","FFRFF","FFRFF"}).solve();
  283.         cout << result.Border << " " << result.Rperimeter << " " << result.Fperimeter << endl;
  284.     }
  285.  
  286.  
  287.     return 0;
  288. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 8 4
2 8 4
4 32 4
4 32 4
4 4 32
4 4 32
5 6 16
5 6 16
7 8 20
7 8 20
9 10 24
9 10 24
9 10 32
9 10 32
https://ideone.com/FYvkax
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!