Implement island counting with BFS and DFS

Question

You are given an m x n grid of characters where '1' represents land and '0' represents water. Count the number of distinct islands (connected land regions). Two land cells belong to the same island if they share a side — up, down, left, or right. Cells that touch only at a corner (diagonally) are not connected and count as separate islands.

For example, the grid below contains 3 islands:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

1. Primary solution. Implement countIslands(grid) using any approach you like, running in O(m·n) time. Explain why it is correct and analyze its time and space complexity.
2. Explicit BFS version. Re-implement the count using an explicit breadth-first search (an iterative queue, no recursion). State its time and space complexity and compare the trade-offs against your first solution.
3. Edge cases. Make sure the solution behaves correctly on: an empty grid (null / 0 rows / 0 columns), an all-water grid, a single-cell grid, a grid that is entirely land, and very large grids. Confirm that diagonally-touching land cells are treated as separate islands.
4. Testing. Describe (or write) tests that validate the solution on several nontrivial cases, including the examples above.
5. Follow-up. Briefly describe how your solution would change if diagonal (8-directional) adjacency also counted as connected.