Вие сте турист, който се подготвя за предстоящ поход. Даден ви е heights, 2D масив с размер rows x columns, където heights[row][col] представлява височината на клетка (row, col). Вие се намирате в горната лява клетка, (0, 0), и се надявате да пътувате до долната дясна клетка, (rows-1, columns-1) (т.е. 0-индексирана). Можете да се движите нагоре, надолу, наляво или надясно и искате да намерите маршрут, който изисква минимум усилия.

Усилието на маршрут е максималната абсолютна разликавъв височините между две последователни клетки на маршрута.

Върнете минималното усилие, необходимо за пътуване от горната лява клетка до долната дясна клетка.

Пример 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

Пример 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

Пример 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.

Ограничения:

  • rows == heights.length
  • columns == heights[i].length
  • 1 <= rows, columns <= 100
  • 1 <= heights[i][j] <= 106

Наивният BFS не работи, защото посещавате възела само веднъж и следователно разглеждате само един от многото пътища. Второ, наивният BFS ще ви даде пътя с минимално посетени възли. В този проблем обаче можем ясно да видим, че optimal path != path with minimal length. (Вижте Пример 3)

Когато даден въпрос пита за нещо, свързано с най-краткия път, винаги обмисляйте как BFS може да помогне, защото това е, което BFS прави. След няколко минути размисъл обаче бързо осъзнавам, че обикновен наивен BFS няма да работи.

Преди да продължим по-нататък, ето псевдокода на наивния BFS:

queue = []
visited = set()
while queue:
	me = queue.popleft()
	for every neighbor of me:
		if neighbor not in visited:
			visited.add(neighbor)
			queue.append(neighbor)

Помислете за първия тестов случай. Ако завъртите вашите съседи по следния начин: [[0,1], [1,0], [-1,0], [0, -1]] (бутате своя десен съсед първо към опашката), тогава ще намерите пътя по-долу преди други възможни пътища (забележете, че първият ход на пътя е отидете надясно).

Това е страхотно. Въпреки че това не е оптималният път, поне сте намерили път до дестинацията и знаете, че effort тук е 3. Сега можете да потърсите други по-добри пътища, нали? За съжаление, в наивния BFS, вие посещавате възел само веднъж. Това означава, че освен ако не нулирате набора visited, не можете да намерите друг път до дестинацията. Не забравяйте, че досега самата дестинация вече е маркирана като посетена, нали? Така че няма да го посетите отново.

Интересното е, че ако зациклите вашите съседи в следния ред [[1,0], [0,1], [-1,0], [0, -1]] (избутвате вашия долу съсед първи на опашката), тогава ще намерите оптималния път.

Така че редът на повторение на съседа има значение. Но чакай малко! това вече не е обхватът на BFS!

В BFS редът на зацикляне на съседите никога не трябва да влияе на отговора.

BFS трябва да намери най-краткия път, независимо от това как итерирате вашите съседи. Вярно е, че нашият BFS е намерил пътя с минимална дължина (т.е. и двата горни пътя посещават 4 възела). Нашият BFS обаче не може да разграничи effort от двата пътя по-горе. И така, наивният BFS не би работил за този проблем. Трябва да модифицираме нашия глупав BFS.

За щастие сме близо. На този етап знам, че логиката за посещение на възел е объркана; Не мога просто да посетя възел веднъж и да го нарека ден, трябва да го посетя повече от веднъж. Къде в кода отговаря дали да посетя възел или не?

Това е вярно:

if neighbor not in visited:
	# visit neighbor

Така че трябва да променим логиката и начина, по който съхраняваме посетеното състояние на BFS. как? Е, задайте този въпрос.

Кога бих си направил труда да посетя възел за втори път?

Отговорът е

когато сме намерили по-добър път (т.е. по-ниска цена)

И този отговор трябва да е достатъчен, за да ми даде намек, че вместо посетен набор, трябва да съхраним цена в речника. Следователно модифицираният BFS трябва да изглежда по следния начин:

queue = []
cost = {} # dictionary, instead of a set
while queue:
	me = queue.popleft()
	for every neighbor of me:
		new_cost = compute_cost()
		if new_cost < cost[neighbor]: # better path!
			cost[neighbor] = new_cost
			queue.append(neighbor)

И този модифициран BFS всъщност е това, което прави Dijkstra :).

Коментирайте времевата сложност. ;-)