Обычно, когда нам нужно решить проблему с 2D-матрицей, в которой мы должны найти путь или найти в нем области, мы обычно думаем о теории графов, поиске в глубину (DFS) или поиске в первую очередь на дыхании (BFS).
Наиболее распространенная проблема - это проблема, в которой мы должны найти размер острова в 2D-матрице, где вода представлена как 0, а земля представлена 1. Затем образуется остров, соединяя соседние земли по горизонтали или вертикали; например, следующая матрица имеет 2 острова:
[ 1 1 1 1 0 ] <- Island number 1 [ 0 0 0 0 0 ] [ 0 0 0 0 0 ] [ 0 0 0 1 1 ] <- Island number 2
Один из способов решения этой проблемы - это DFS метод обхода, при котором каждый посещаемый узел должен быть установлен как «0», чтобы пометить его как посещаемый участок. Таким образом, участок земли учитывается только один раз на каждой итерации (это означает, что посещение одного участка земли рекурсивно для всех соседних земель в матрице.), Скажем, первый посещенный участок земли используется для подсчета количества островов матрица имеет.
Давайте проверим несколько распространенных проблем, которые можно решить с помощью DFS техники.
200. Количество островов [LeetCode]
Given anm x n2D binary gridgridwhich represents a map of'1's (land) and'0's (water), return the number of islands. Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
В качестве отправной точки мы должны пройти по матрице от позиции [0, 0] до остановки до конца матрицы; если мы найдем участок земли, необходимо будет проложить маршрут из слотов смежности.
public int numIslands(int[][] grid) {
int ans = 0;
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
if (grid[row][col] == 1) { // Land in matrix
DFS(grid, row, col); // Check for adjacent slots
ans++;
}
}
}
return ans;
}
Для функции DFS достаточно будет посетить только те слоты, которые не являются водой и которые находятся в пределах матрицы.
public void DFS(int[][] grid, int row, int col) {
if (row >= grid.length || row < 0 ||
col >= grid[0].length || col < 0 ||
grid[row][col] == 0) { // Check boundaries
return;
}
int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
grid[row][col] = 0; // Land visited, mark as water
for (int[] d : directions) { // Visit: left, right, top, bottom
DFS(grid, row + d[0], col + d[1]);
}
}
694. Количество отдельных островов [LeetCode]
Given a non-empty 2D arraygridof 0's and 1's, an island is a group of1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.
Теперь, когда мы знаем, как подсчитать количество островов, мы можем разработать решение для определения количества различных островов. Все, что нам нужно сделать, это добавить механизм для отслеживания всех островов, найденных с помощью решения предыдущей проблемы.
Например, мы можем сохранить только схему формирования острова в Set, чтобы вернуть его размер только в конце.
public int numDistinctIslands(int[][] grid) {
int ans = 0;
Set<String> set = new HashSet<String>(); // Set for patterns
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
if (grid[row][col] == 1) {
StringBuilder sb = new StringBuilder();
DFS(grid, row, col, sb, "."); // Wild card pattern
set.add(sb.toString()); // Save island pattern
}
}
}
return set.size(); // Num of different patterns
}
Теперь будет достаточно лишь немного изменить функцию DFS, используемую ранее, с целью сохранения записи всех шаблонов островов в матрице; шаблоны построены с использованием числа 1 и отличительного символа.
....
for (int[] d : directions) {
sb.append(str); // Save previous pattern
DFS(grid, row + d[0], col + d[1], sb,
String.valueOf(d[0] + d[1])); // Define a new pattern,
sb.append("."); // Differentiating character
}
...
695. Максимальная площадь острова [LeetCode]
Given a non-empty 2D arraygridof 0's and 1's, an island is a group of1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.) Input: grid = [ ["1","1","0","1","1"], ["1","0","0","1","1"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 5
Для этой проблемы мы все еще можем использовать те же функции, за исключением того, что нужно внести небольшие изменения, чтобы найти остров с максимальной площадью. Достаточно будет просто вести учет посещенных участков островов, всегда сохраняя самые крупные. В этом случае временный счетчик должен инициализироваться каждый раз, когда посещается новый элемент матрицы, который всегда является началом нового острова.
...
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
if (grid[row][col] == 1) { // Initialize new island size
ans = Math.max(DFS(grid, row, col, 0), ans); // Save max
}
}
}
return ans;
}
Обратите внимание на то, что функция DFS примерно такая же, однако было добавлено возвращаемое значение и найден максимальный размер для текущего острова.
public int DFS(int[][] grid, int row, int col, int ans) {
if (row >= grid.length || row < 0 ||
col >= grid[0].length || col < 0 ||
grid[row][col] == 0) {
return ans;
}
ans++; // Increase the current max size
grid[row][col] = 0;
int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
for (int[] d : directions) {
ans = Math.max(DFS(grid, row + d[0], col + d[1], ans), ans);
} // Save the current max size to be returned
return ans;
}
В рамках практики читателя остается решение других подобных, но более сложных задач, используя использованную технику DFS.
305. Количество островов II [LeetCode]
You are given an empty 2D binary gridgridof sizem x n. The grid represents a map where0's represent water and1's represent land. Initially, all the cells ofgridare water cells (i.e., all the cells are0's). Return an array of integersanswerwhereanswer[i]is the number of islands after turning the cell(ri, ci)into a land.
