Count the islands: groups of 1s connected up, down, left or right. Scan every cell. Each time a 1 is found that no fill has reached, that is a new island: count it and flood fill it to 2 so the rest of the scan skips it.
Counting islands of 1s by flood filling each one as it is found.
(0, 0) is land no fill has touched: island 1. Flood fill from here so every cell of this island is sunk before the scan continues.
Island 1 starts at row 0 column 0.
Island 1. Pop (0, 0). 2 neighbours still land: (1, 0), (0, 1). Paint and queue them.
Cell 0, 0 is painted. 2 neighbours join the queue.
Island 1. Pop (1, 0). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 1, 0 is painted. 0 neighbours join the queue.
Island 1. Pop (0, 1). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 0, 1 is painted. 0 neighbours join the queue.
Island 1. The queue is empty: nothing reachable is left. 3 cells painted.
The queue is empty. 3 cells were painted.
(1, 3) is land no fill has touched: island 2. Flood fill from here so every cell of this island is sunk before the scan continues.
Island 2 starts at row 1 column 3.
Island 2. Pop (1, 3). 2 neighbours still land: (2, 3), (1, 4). Paint and queue them.
Cell 1, 3 is painted. 2 neighbours join the queue.
Island 2. Pop (2, 3). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 2, 3 is painted. 0 neighbours join the queue.
Island 2. Pop (1, 4). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 1, 4 is painted. 0 neighbours join the queue.
Island 2. The queue is empty: nothing reachable is left. 3 cells painted.
The queue is empty. 3 cells were painted.
(3, 0) is land no fill has touched: island 3. Flood fill from here so every cell of this island is sunk before the scan continues.
Island 3 starts at row 3 column 0.
Island 3. Pop (3, 0). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 3, 0 is painted. 0 neighbours join the queue.
Island 3. The queue is empty: nothing reachable is left. 1 cell painted.
The queue is empty. 1 cells were painted.
(3, 2) is land no fill has touched: island 4. Flood fill from here so every cell of this island is sunk before the scan continues.
Island 4 starts at row 3 column 2.
Island 4. Pop (3, 2). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 3, 2 is painted. 0 neighbours join the queue.
Island 4. The queue is empty: nothing reachable is left. 1 cell painted.
The queue is empty. 1 cells were painted.
4 islands. Every land cell was painted exactly once across all the fills, so the whole count is O(cells) even though it looks like a search inside a scan.
4 islands were counted.