Islands II

Questions 1 to 5 of 6

1. 1. Predict the output. This program counts islands after each position on a 2 by 3 grid, using the lesson's islandCounts. ``cpp #include <array> #include <iostream> #include <utility> #include <vector> class DisjointSet { public: explicit DisjointSet(int n) : parent_(n), size_(n, 1) { for (int i = 0; i < n; ++i) parent_[i] = i; } int find(int x) { while (parent_[x] != x) { parent_[x] = parent_[parent_[x]]; x = parent_[x]; } return x; } bool unite(int a, int b) { int ra = find(a); int rb = find(b); if (ra == rb) return false; if (size_[ra] < size_[rb]) std::swap(ra, rb); parent_[rb] = ra; size_[ra] += size_[rb]; return true; } private: std::vector<int> parent_; std::vector<int> size_; }; std::vector<int> islandCounts(int rows, int cols, const std::vector<std::pair<int, int>>& positions) { constexpr std::array<int, 4> kDr{-1, 1, 0, 0}; constexpr std::array<int, 4> kDc{0, 0, -1, 1}; DisjointSet dsu(rows * cols); std::vector<char> is_land(rows * cols, 0); std::vector<int> answer; int islands = 0; for (auto [r, c] : positions) { int id = r * cols + c; if (is_land[id]) { answer.push_back(islands); continue; } is_land[id] = 1; ++islands; for (int k = 0; k < 4; ++k) { int nr = r + kDr[k]; int nc = c + kDc[k]; if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; int nid = nr * cols + nc; if (!is_land[nid]) continue; if (dsu.unite(id, nid)) --islands; } answer.push_back(islands); } return answer; } void print(const std::vector<int>& v) { for (int x : v) std::cout << x << ' '; std::cout << '\n'; } int main() { print(islandCounts(2, 3, {{0, 0}, {0, 2}, {1, 1}, {0, 1}, {1, 2}})); } ``

   1 2 3 2 11 2 3 1 21 2 3 1 11 2 2 1 1
2. 2. Predict the output. This is the lesson's program with one change: the column upper-bound test (nc >= cols) is removed from the neighbour loop. main runs one grid. ``cpp #include <array> #include <iostream> #include <utility> #include <vector> class DisjointSet { public: explicit DisjointSet(int n) : parent_(n), size_(n, 1) { for (int i = 0; i < n; ++i) parent_[i] = i; } int find(int x) { while (parent_[x] != x) { parent_[x] = parent_[parent_[x]]; x = parent_[x]; } return x; } bool unite(int a, int b) { int ra = find(a); int rb = find(b); if (ra == rb) return false; if (size_[ra] < size_[rb]) std::swap(ra, rb); parent_[rb] = ra; size_[ra] += size_[rb]; return true; } private: std::vector<int> parent_; std::vector<int> size_; }; std::vector<int> islandCounts(int rows, int cols, const std::vector<std::pair<int, int>>& positions) { constexpr std::array<int, 4> kDr{-1, 1, 0, 0}; constexpr std::array<int, 4> kDc{0, 0, -1, 1}; DisjointSet dsu(rows * cols); std::vector<char> is_land(rows * cols, 0); std::vector<int> answer; int islands = 0; for (auto [r, c] : positions) { int id = r * cols + c; if (is_land[id]) { answer.push_back(islands); continue; } is_land[id] = 1; ++islands; for (int k = 0; k < 4; ++k) { int nr = r + kDr[k]; int nc = c + kDc[k]; if (nr < 0 || nr >= rows || nc < 0) continue; int nid = nr * cols + nc; if (!is_land[nid]) continue; if (dsu.unite(id, nid)) --islands; } answer.push_back(islands); } return answer; } void print(const std::vector<int>& v) { for (int x : v) std::cout << x << ' '; std::cout << '\n'; } int main() { print(islandCounts(2, 3, {{1, 0}, {0, 2}})); } ``

   1 21 12 22 1
3. 3. The grid has 3 rows and 3 columns, and each cell gets the flat index row * cols + col. What is the flat index of cell (1, 2)?

   7245
4. 4. A new land cell touches two land neighbours, and each one is in a different island. What is the net change in the island count from this one new cell?

   +10-1-2
5. 5. Which statements about islandCounts in this lesson are true? Pick all that apply.

   Pick every answer that is true.

   A position that is already land leaves the count unchanged, because the early continue skips the count updateTwo land cells that touch only at a corner are joined into one islandThe count goes down by one for each neighbour where unite returns true, and not for a neighbour already in the same islandThe four neighbour offsets include the diagonals, so diagonal land cells join islands too