Ежедневная часть (e) C++ # 170, Распространенная проблема на собеседовании: подсчет островов.
Сегодня мы рассмотрим распространенную задачу интервью C++: подсчет островов.
Дана карта в виде std::vector‹std::vector‹char››, где 'L' представляет землю, а 'W' представляет воды, вернуть количество островов на карте.
Остров представляет собой ортогонально (в четырех направлениях) соединенную область суши, полностью (ортогонально) окруженную водой.
Например, на приведенной выше карте у нас есть только один остров, так как никакие другие массивы суши не окружены полностью водой.
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/Y8o6ahK41.
Решение
Нам понадобятся две отдельные части функциональности.
- Нам нужно сканировать карту, чтобы обнаружить наземные пространства.
- Когда у нас есть участок суши, нам нужно определить полную протяженность этого массива суши и определить, является ли он островом.
Сухопутный массив — это остров, если мы не достигаем границы нашей карты во время нашего исследования. Важно отметить, что при поиске земельных пространств мы должны избегать мест, которые мы уже посетили во время нашего исследования (чтобы избежать двойного учета островов).
Чтобы исследовать острова, мы можем использовать поиск в глубину или в ширину; это решение основано на поиске в глубину. Пока мы полностью изучаем каждый остров и отслеживаем посещенные места, нам не нужно беспокоиться о двойном учете.
// depth-first search
bool island(int64_t i, int64_t j,
std::vector<std::vector<char>>& grid) {
// If we managed to reach out of bounds, this is not an island
if (i == -1 || i == std::ssize(grid) ||
j == -1 || j == std::ssize(grid[i]))
return false;
// If this space is not land, ignore
if (grid[i][j] != 'L')
return true;
// Mark this space as visited
grid[i][j] = 'V';
// We want all four cardinal directions to return true
// but need to avoid boolean short-circuiting.
// Even if this is not an island we want to mark all
// the land spaces as visited.
// The bellow code takes advantage of implicit bool->int
// conversion: 0 == false, 1 == true.
return (island(i-1,j,grid) + island(i+1,j,grid)
+ island(i,j-1,grid) + island(i,j+1,grid)) == 4;
}
int count_islands(std::vector<std::vector<char>> grid) {
int cnt = 0;
// For every space
for (int64_t i = 0; i < std::ssize(grid); ++i)
for (int64_t j = 0; j < std::ssize(grid[i]); ++j)
// If it is an unvisited land space,
// check if it is an island.
if (grid[i][j] == 'L' && island(i,j,grid))
++cnt;
return cnt;
}
