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 }