C# (C Sharp) programming

🖥 Задача с leetcode. Max Area of Island



Максимальная площадь острова



Сложность: Средняя



Условие задачи: Условие задачи:



Дан двумерный массив размера m x n. "1" отвечает за сушу, "0" - за океан. Необходимо опеределить максмимальную площадь острова из островов, расположенных на карте.



Островом считается территория, образованная из "1", расположенных сверху, справа, снизу и слева относительно друг друга.





Пример:



Ввод: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]



Вывод: 6



Ввод: grid = [[0,0,0,0,0,0,0,0]]



Вывод: 0



Решение



public class Solution {

public int MaxAreaOfIsland(int[][] grid)

{

var best = 0;

var travelled = new bool[grid.Length][];



for (var i = 0; i < grid.Length; i++)

travelled[i] = new bool[grid[i].Length];



for (var i = 0; i < grid.Length; i++)

for (var j = 0; j < grid[0].Length; j++)

if (grid[i][j] == 1 && !travelled[i][j])

{

var q = ExploreIsland(grid, i, j, travelled);

best = Math.Max(best, q);

}



return best;

}



private int ExploreIsland(int[][] grid, int i, int j, bool[][] travelled)

{

if (i < 0 || j < 0 || i >= travelled.Length || j >= travelled[0].Length) return 0;

if (grid[i][j] == 0 || travelled[i][j]) return 0;



travelled[i][j] = true;



var north = ExploreIsland(grid, i + 1, j, travelled);

var west = ExploreIsland(grid, i, j - 1, travelled);

var east = ExploreIsland(grid, i, j + 1, travelled);

var south = ExploreIsland(grid, i - 1, j, travelled);



return north + west + east + south + 1;

}

}



Временная сложность : O(n^2*m^2)

Пространственная сложность: O(n∗m)





Пишите свое решение в комментариях👇



@cpluscsharp