C# (C Sharp) programming

💡Задача "Самый короткий мост"



Условие: на вход подается матрица, в которой 1 - суша, 0 - вода.



Остров представляет из себя совокупность частей суши, соединенных в четырех направлениях. На решетке существуют только два острова.



Можно изменить 0 на 1 для соединения двух островов в один.



Необходимо посчитать количество смен нулей на единицу для соединения двух островов.



Пример:



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

Вывод: 1



Объяснение:



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

Вывод: 2



Решенние:



public class Solution {

public IList<int> SpiralOrder(int[][] matrix) {

List<int> lst = new();

int m = matrix.Length;

int n = matrix[0].Length;

int max = (int)Math.Ceiling(Math.Min(m,n)/2.0);

for(int index=0; index< max; index++){

if(m - index * 2 == 1 || n - index * 2 == 1) {

for(int i=index; i<m-index; i++)

for(int j= index; j<n-index; j++)

lst.Add(matrix[i][j]);

continue;

}



for(int i=index; i<n-index-1; i++)

lst.Add(matrix[index][i]);

for(int i=index;i<m-index-1; i++)

lst.Add(matrix[i][n-1-index]);

for(int i=n-1-index; i>index; i--)

lst.Add(matrix[m-1-index][i]);

for(int i=m-1-index; i>index; i--)

lst.Add(matrix[i][index]);

}



return lst;

}

}



Временная сложность:

O(mn)



Пространственная сложность:

O(nm)



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



@csharp_ci