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 }