algorithms

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

main.cpp (2084B)


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