counting_rooms_1192.cpp (1269B)
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 5 class Tile { 6 public: 7 int i; 8 int j; 9 std::vector<Tile> neighbors() const { 10 return {Tile{i-1,j}, Tile{i+1,j}, Tile{i,j-1}, Tile{i,j+1}}; 11 } 12 }; 13 14 class Map { 15 public: 16 int n; 17 int m; 18 19 Map(int i, int j) : n{i}, m{j}, c(n*m, 0) {} 20 int color(Tile t) const { return inbound(t) ? c[ind(t)] : -1; } 21 void setcolor(Tile t, int k) { if (inbound(t)) c[ind(t)] = k; } 22 bool wall(Tile t) const { return !inbound(t) || c[ind(t)] == -1; } 23 void setwall(Tile t) { if (inbound(t)) setcolor(t, -1); } 24 private: 25 std::vector<int> c; 26 27 size_t ind(Tile t) const { return m*t.i + t.j; } 28 bool inbound(Tile t) const { 29 return t.i >= 0 && t.i < n && t.j >= 0 && t.j < m; 30 } 31 }; 32 33 Map readmap() { 34 int n, m; 35 std::string s; 36 std::cin >> n >> m; 37 Map map(n, m); 38 for (int i = 0; i < n; i++) { 39 std::cin >> s; 40 for (int j = 0; j < m; j++) 41 if (s[j] == '#') 42 map.setwall(Tile{i, j}); 43 } 44 return map; 45 } 46 47 void visit(Map& m, Tile t, int c) { 48 m.setcolor(t, c); 49 for (auto u : t.neighbors()) 50 if (m.color(u) == 0) 51 visit(m, u, c); 52 } 53 54 int main() { 55 auto m = readmap(); 56 int c{0}; 57 for (int i = 0; i < m.n; i++) 58 for (int j = 0; j < m.m; j++) 59 if (m.color(Tile{i, j}) == 0) 60 visit(m, Tile{i, j}, ++c); 61 std::cout << c << "\n"; 62 }