Golang | LeetCode

Задача: 499. The Maze III
Сложность: hard

В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может катиться вверх, вниз, влево или вправо, пока не столкнется со стеной, затем выбрать новое направление. В лабиринте также есть отверстие, куда мячик упадет, если закатится в него.

Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо).
Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно).

Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

👨‍💻

Алгоритм:

1⃣

Инициализация и вспомогательные функции
Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной.

2⃣

Запуск алгоритма Дейкстры
Инициализируйте очередь с начальной позицией мяча, где элементы с меньшим расстоянием имеют высокий приоритет, а при равных расстояниях выбирайте минимальную строку пути. Создайте структуру seen для отслеживания посещенных узлов.

3⃣

Поиск кратчайшего пути
Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible".

😎

Решение:

package main

import (
  "container/heap"
)

type State struct {
  row, col, dist int
  path           string
}

type PriorityQueue []*State

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist || (pq[i].dist == pq[j].dist && pq[i].path < pq[j].path) }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*State)) }
func (pq *PriorityQueue) Pop() interface{} {
  old := *pq
  n := len(old)
  item := old[n-1]
  *pq = old[:n-1]
  return item
}

var directions = [4][2]int{{0, -1}, {-1, 0}, {0, 1}, {1, 0}}
var textDirections = []string{"l", "u", "r", "d"}

func findShortestWay(maze [][]int, ball, hole []int) string {
  m, n := len(maze), len(maze[0])
  pq := &PriorityQueue{}
  heap.Init(pq)
  heap.Push(pq, &State{ball[0], ball[1], 0, ""})
  seen := make([][]bool, m)
  for i := range seen {
    seen[i] = make([]bool, n)
  }

  for pq.Len() > 0 {
    curr := heap.Pop(pq).(*State)
    if seen[curr.row][curr.col] {
      continue
    }
    if curr.row == hole[0] && curr.col == hole[1] {
      return curr.path
    }
    seen[curr.row][curr.col] = true

    for i := 0; i < 4; i++ {
      dy, dx := directions[i][0], directions[i][1]
      currRow, currCol, dist := curr.row, curr.col, 0
      for currRow+dy >= 0 && currRow+dy < m && currCol+dx >= 0 && currCol+dx < n && maze[currRow+dy][currCol+dx] == 0 {
        currRow += dy
        currCol += dx
        dist++
        if currRow == hole[0] && currCol == hole[1] {
          break
        }
      }
      heap.Push(pq, &State{currRow, currCol, curr.dist + dist, curr.path + textDirections[i]})
    }
  }
  return "impossible"
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post