algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

old.cpp (2015B)


      1 #include <vector>
      2 #include <algorithm>
      3 #include <iostream>
      4 
      5 // - idea:
      6 //     - for each position:
      7 //         - dfs
      8 //             - each step returns the size of the connected component that's newly visited from the position (there will likely be cycles)
      9 //         - dfs:
     10 //             - go up,left,right,down if there's not a wall on that side
     11 //                 - we don't have to check bounds because walls are on edges.
     12 
     13 int searchFrom(std::vector<std::vector<int>>& grid, std::vector<bool>& visited, int y, int x) {
     14     int currentIdx = (y * grid[0].size()) + x;
     15     if(visited[currentIdx]) {
     16         return 0;
     17     }
     18     visited[currentIdx] = true;
     19 
     20     int res = 1;
     21     int current = grid[y][x];
     22 
     23     // North, East, South, West
     24     if((current & 0b1000) == 0) {
     25         res += searchFrom(grid,visited, y-1, x);
     26     }
     27 
     28     if((current & 0b0100) == 0) {
     29         res += searchFrom(grid,visited, y, x+1);
     30     }
     31 
     32     if((current & 0b0010) == 0) {
     33         res += searchFrom(grid,visited, y+1, x);
     34     }
     35 
     36     if((current & 0b0001) == 0) {
     37         res += searchFrom(grid,visited, y, x-1);
     38     }
     39     return res;
     40 }
     41 
     42 int main() {
     43     int rows,cols,current;
     44     std::cin >> rows;
     45     std::cin >> cols;
     46     
     47     std::vector<std::vector<int>> grid {};
     48     for(int y = 0; y < rows; ++y) {
     49         std::vector<int> cLs {};
     50         for(int x = 0; x < cols; ++x) {
     51             std::cin >> current;
     52             cLs.push_back(current);
     53         }
     54         grid.push_back(cLs);
     55     }
     56 
     57     std::vector<bool> visited (grid[0].size() * grid.size(), false);
     58     std::vector<int> result {};
     59 
     60     for(int y = 0; y < rows; ++y) {
     61         for(int x = 0; x < cols; ++x) {
     62             int res = searchFrom(grid,visited,y,x);
     63             if(res != 0) {
     64                 result.push_back(res);
     65             }
     66         }
     67     }
     68 
     69     std::sort(result.begin(), result.end());
     70     std::reverse(result.begin(), result.end());
     71 
     72     for(int i = 0; i < result.size(); ++i) {
     73         std::cout << result[i] << " ";
     74     }
     75 
     76     std::cout << std::endl;
     77 
     78 }