Python вопросы с собеседований

⚡️ Задачи на Python с использованием dfs + bfs



Дана двоичная матрица размера n x n, где 1 представляет сушу, а 0 представляет воду.



Остров — это 4-направленно связанная группа 1, не связанная ни с какими другими 1. В сетке ровно два острова.



Вы можете изменить 0 на 1, чтобы соединить два острова в один остров.



Возвращает наименьшее количество нулей, которое нужно перевернуть, чтобы соединить два острова.



1. Для начала я предлагаю найти 1-ый остров в матрице, с помощью обхода в глубину (dfs), если мы нашли элемент 1-го острова, тогда меняем значение в двумерной матрице на 2. Для экономии времени мы будем заранее заполнять очередь для будущего обхода в ширину (bfs).



n = len(grid)

queue = []



def dfs(x, y):

if x > 0 or x >= n or 0 > y or y >= n or grid[x][y] != 1:

return

grid[x][y] = 2

queue.append([x, y, 0])

dfs(x - 1, y)

dfs(x + 1, y)

dfs(x, y - 1)

dfs(x, y + 1)



# Перебираем двумерный массив, пока не найдем первый элемент суши

flag = False

for i in range(n):

for j in range(n):

if grid[i][j]:

dfs(i, j)

flag = True

break

if flag:

break



2. С помощью обхода в ширину мы найдем кратчайший путь до 2-го острова, для этого мы заполнили очередь координатами элементов 1-го острова.



# Чтобы убрать больше количество условных операторов

# я буду использовать цикл for, в котором я буду перебирать

# все возможные варианты дальнейшего пути



dirct = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while len(queue) != 0:

# step - расстояние до 2-го острова

x, y, step = queue[0][0], queue[0][1], queue[0][2]

queue.pop(0)

for dx, dy in dirct:

x1, y1 = x + dx, y + dy

if 0 > x1 or x1 >= n or 0 > y1 or y1 >= n:

continue

if grid[x1][y1] == 1:

return step # ответ на задачу

if grid[x1][y1] == 0:

grid[x1][y1] = 2

queue.append([x1, y1, step + 1])



Весь код:



class Solution(object):

def shortestBridge(self, grid):

n = len(grid)

queue = []

def dfs(x, y):

if 0 > x or x >= n or 0 > y or y >= n or grid[x][y] != 1:

return

grid[x][y] = 2

queue.append([x, y, 0])

dfs(x - 1, y)

dfs(x, y - 1)

dfs(x + 1, y)

dfs(x, y + 1)



flag = False

for i in range(n):

for j in range(n):

if grid[i][j]:

dfs(i, j)

flag = True

break

if flag:

break

dirct = [(0, 1), (1, 0), (-1, 0), (0, -1)]

while len(queue) != 0:

x, y, step = queue[0][0], queue[0][1], queue[0][2]

queue.pop(0)

for dx, dy in dirct:

x1, y1 = x + dx, y + dy

if 0 > x1 or x1 >= n or 0 > y1 or y1 >= n:

continue

if grid[x1][y1] == 1:

return step

if grid[x1][y1] == 0:

grid[x1][y1] = 2

queue.append([x1, y1, step + 1])



@python_job_interview