Explanation

Start by using floodfill from Stockholm to see how many #s Vidar can reach. The landmass is the size of the visited set, as the visited set only consists of #s that can be reached from Stockholm. We call the set of all #s that are reachable from Stockholm the main connected component.

If a query is adjacent to the main connected component, meaning the query is reachable from Stockholm, the main connected component expands. Additionally, there is a chance that the query connects the main connected component to another connected component. Thus, we floodfill again if a query is adjacent to the main connected component.

Floodfill skips past #s that are already visited so it is guaranteed that every time we run floodfill, only new #s will be seen.

Implementation

Time Complexity: $\mathcal{O} (U + RC)$

Copy
#include <bits/stdc++.h>

using namespace std;

set<pair<int, int>> visited;

// first denotes the character and second denotes if it is reachable from S
vector<vector<pair<char, bool>>> grid;

void floodfill(int r, int c) {

Copy
import java.io.*;
import java.util.*;

public class sverigekartan {
	static Set<Integer> visited = new HashSet<>();
	static char[][] grid;
	static boolean[][] reachable;

	static int encode(int r, int c) { return r * grid[0].length + c; }

Copy
import sys

sys.setrecursionlimit(1000000)


def floodfill(r, c, grid, visited):
	if (
		r < 0
		or c < 0
		or r >= len(grid)