fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. int main()
  6. {
  7.     std::vector<std::string> lines;
  8.     for(;;)
  9.     {
  10.         std::string line;
  11.         std::cin >> line;
  12.         lines.push_back(std::move(line));
  13.         if(std::cin.eof()) break;
  14.  
  15.     }
  16.     int width = lines[0].size();
  17.     int height = lines.size();
  18.  
  19.     std::vector<std::vector<char>> input(width, std::vector<char>(height));
  20.  
  21.     for(int y = 0; y < height; ++y)
  22.     {
  23.         for(int x = 0; x < width; ++x)
  24.         {
  25.             input[x][y] = lines[y][x];
  26.         }
  27.     }
  28.  
  29.     std::vector<std::vector<int>> possibilities(width, std::vector<int>(height, 0));
  30.  
  31.     for(int y = 0; y < height - 1; ++y) //filling where 2x2 square fits
  32.     {
  33.         for(int x = 0; x < width - 1; ++x)
  34.         {
  35.             if(input[x][y] == '1' && input[x + 1][y] == '1' && input[x][y + 1] == '1' && input[x + 1][y + 1] == '1')
  36.             {
  37.                 possibilities[x][y] = 1;
  38.             }
  39.         }
  40.     }
  41.  
  42.     for(int y = 0; y < height; ++y) //printing for debug
  43.     {
  44.         for(int x = 0; x < width; ++x)
  45.         {
  46.             std::cout << possibilities[x][y] << ' ';
  47.         }
  48.         std::cout << '\n';
  49.     }
  50.  
  51.     std::cout << '\n';
  52.  
  53.     for(int y = 0; y < height; ++y) //counting neighbours
  54.     {
  55.         for(int x = 0; x < width; ++x)
  56.         {
  57.             if(possibilities[x][y] == 0) continue;
  58.             int minX = -1;
  59.             int minY = -1;
  60.             int maxX = 1;
  61.             int maxY = 1;
  62.             if(x <= 0) minX = 0;
  63.             if(y <= 0) minY = 0;
  64.             if(x >= width - 1) maxX = 0;
  65.             if(y >= height - 1) maxY = 0;
  66.             for(int xx = minX; xx <= maxX; ++xx)
  67.             {
  68.                 for(int yy = minY; yy <= maxY; ++yy)
  69.                 {
  70.                     if(xx == 0 && yy == 0) continue;
  71.                     if(possibilities[xx + x][yy + y] > 0) ++possibilities[x][y];
  72.                 }
  73.             }
  74.         }
  75.     }
  76.  
  77.     for(int y = 0; y < height; ++y) //printing for debug
  78.     {
  79.         for(int x = 0; x < width; ++x)
  80.         {
  81.             std::cout << possibilities[x][y] << ' ';
  82.         }
  83.         std::cout << '\n';
  84.     }
  85.  
  86.     std::cout << '\n';
  87.  
  88.     struct Element
  89.     {
  90.         int value;
  91.         int x;
  92.         int y;
  93.     };
  94.     std::vector<Element> sortedElements;
  95.     for(int y = 0; y < height; ++y) //printing for debug
  96.     {
  97.         for(int x = 0; x < width; ++x)
  98.         {
  99.             if(possibilities[x][y] > 0) sortedElements.push_back(Element {possibilities[x][y], x, y});
  100.         }
  101.     }
  102.     std::sort(sortedElements.begin(), sortedElements.end(), [](const Element & lhs, const Element & rhs) -> bool {return lhs.value < rhs.value;});
  103.     /*
  104.     for(int y = 0; y < height; ++y) //taking values with lesser neighbours
  105.     {
  106.         for(int x = 0; x < width; ++x)
  107.         {
  108.             if(possibilities[x][y] == 0) continue;
  109.             int minX = -1;
  110.             int minY = -1;
  111.             int maxX = 1;
  112.             int maxY = 1;
  113.             if(x <= 0) minX = 0;
  114.             if(y <= 0) minY = 0;
  115.             if(x >= width - 1) maxX = 0;
  116.             if(y >= height - 1) maxY = 0;
  117.             bool inSolution = true;
  118.             for(int xx = minX; xx <= maxX; ++xx)
  119.             {
  120.                 for(int yy = minY; yy <= maxY; ++yy)
  121.                 {
  122.                     if(xx == 0 && yy == 0) continue;
  123.                     if(possibilities[xx + x][yy + y] == 0) continue;
  124.                     if(possibilities[x][y] > possibilities[xx + x][yy + y])
  125.                     {
  126.                         inSolution = false;
  127.                         xx = maxX + 1; //to break out of two loops
  128.                         break;
  129.                     }
  130.                 }
  131.             }
  132.             if(inSolution)
  133.             {
  134.                 for(int xx = minX; xx <= maxX; ++xx)
  135.                 {
  136.                     for(int yy = minY; yy <= maxY; ++yy)
  137.                     {
  138.                         if(xx == 0 && yy == 0) continue;
  139.                         possibilities[xx + x][yy + y] = 0;
  140.                     }
  141.                 }
  142.             }
  143.         }
  144.     }
  145.     */
  146.     for(auto& element : sortedElements)
  147.     {
  148.         int x = element.x;
  149.         int y = element.y;
  150.         if(possibilities[x][y] == 0) continue;
  151.         int minX = -1;
  152.         int minY = -1;
  153.         int maxX = 1;
  154.         int maxY = 1;
  155.         if(x <= 0) minX = 0;
  156.         if(y <= 0) minY = 0;
  157.         if(x >= width - 1) maxX = 0;
  158.         if(y >= height - 1) maxY = 0;
  159.         bool inSolution = true;
  160.         for(int xx = minX; xx <= maxX; ++xx)
  161.         {
  162.             for(int yy = minY; yy <= maxY; ++yy)
  163.             {
  164.                 if(xx == 0 && yy == 0) continue;
  165.                 if(possibilities[xx + x][yy + y] == 0) continue;
  166.                 if(possibilities[x][y] > possibilities[xx + x][yy + y])
  167.                 {
  168.                     inSolution = false;
  169.                     xx = maxX + 1; //to break out of two loops
  170.                     break;
  171.                 }
  172.             }
  173.         }
  174.         if(inSolution)
  175.         {
  176.             for(int xx = minX; xx <= maxX; ++xx)
  177.             {
  178.                 for(int yy = minY; yy <= maxY; ++yy)
  179.                 {
  180.                     if(xx == 0 && yy == 0) continue;
  181.                     possibilities[xx + x][yy + y] = 0;
  182.                 }
  183.             }
  184.         }
  185.     }
  186.  
  187. 	int count = 0;
  188.     for(int y = 0; y < height; ++y) //printing for debug
  189.     {
  190.         for(int x = 0; x < width; ++x)
  191.         {
  192.             std::cout << possibilities[x][y] << ' ';
  193.             if(possibilities[x][y] > 0) ++count;
  194.         }
  195.         std::cout << '\n';
  196.     }
  197. 	std::cout << '\n' << "Count: " << count;
  198.  
  199.     return 0;
  200. }
  201.  
Success #stdin #stdout 0s 3240KB
comments (?)
stdin
copy 
100011
011111
111111
110111
100011
100011
stdout
copy 
0 0 0 0 1 0 
0 1 1 1 1 0 
1 0 0 1 1 0 
0 0 0 0 1 0 
0 0 0 0 1 0 
0 0 0 0 0 0 

0 0 0 0 3 0 
0 3 4 6 5 0 
2 0 0 6 5 0 
0 0 0 0 4 0 
0 0 0 0 2 0 
0 0 0 0 0 0 

0 0 0 0 3 0 
0 0 4 0 0 0 
2 0 0 0 5 0 
0 0 0 0 0 0 
0 0 0 0 2 0 
0 0 0 0 0 0 

Count: 5
https://ideone.com/Wq1xRo
language:
C++14 (gcc 8.3)
created:
10 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!