[DSA] Домашно Linear Data Structures - 14 Задача - Labyrinth


3

Условие:

* We are given a labyrinth of size N x N. Some of its cells are empty (0) and some are full (x). We can move from an empty cell to another empty cell if they share common wall. Given a starting position (*) calculate and fill in the array the minimal distance from this position to any other cell in the array. Use "u" for all unreachable cells.

Преди да задам въпроса си имахте превиди, че задачата не е завършена и номерирането НЕ работи :)

Та - ето кода:

GitHub

Въпроса ми е, как бихте номерирали наследниците си при BFS-a ? Пробвах няколко начина, но никой от тях не ми хареса, така, че бих се радвал за 2ро мнение :)

Логиката за BFS-a е в:

public static void BreathFirstSearch(string[,] labyrinth, Point startingPoint)



Отговори



0

Моето решение представлява, общо взето изменение на задачата за намиране на път в лабиринт.

Минавам рекурсивно по всички достъпни клетки в лабиринта и им слагам някакви стойности представляващи инкриментираният им съсед, от който съм дошъл. Най-накрая обхождам лабиринта, за да видя дали няма недостъпени клетки, ако има ги пълня с 'u', и отпечатвам лабиринта на конзолата.


от iliyan.tanev (517 точки)


0
Разминава се от примера колега ;-) Няма да го бъде така май.

от Ivaylo (696 точки)

0
Просто моето минава по малко по-различни пътища, които пак са възможни, за това се различава. Иначе е валидно. :)

от iliyan.tanev (517 точки)


1

Заповядайте и моята имплементация: CLICK. Ползвам BFS, като в опашката си държа Tuple<int, int, int>, който индикира настоящ ред, настояща колона, настояща вълна (може би трябваше да си изкарам една структура MatrixCoords, но това са алгоритми :D). 


от vlad_karamfilov (4595 точки)


0

Моето решение използва Queue<MatrixItem> мисля че така е най правилно като ООП и КПК, като MatrixItem има int x, inty, и int value - вземам го след като съм преверил дали е първоначално клетката с "0".




0

Решение

Маркирам всички заети клетки с -1 ( не го правя като метод за да не претрупвам кода - просто приемам, че така са ми дадени данните).

Първо откривам стартовата позиция с методa FindStartCoords()

После за всяка от 4те посоки извиквам DFS метода Solve като му подавам координатите и stepcounter - последния пази какво ще се запише в клетката, ако тя е празна или стойността ще бъде по-малка от тази която вече е в самата клетка.


от dzhenko (3893 точки)


0

Ето и едно решение от мен с BFS реализиран с опашка, разбира се.

На фона на задачите по JS тези от DSA са истинско предизвикателство и доставят голямо удовослствие като ги реши човек. Точно за тази задача се притеснявах, че ще е много бавна, но за мое учудване работи дори при размер на лабиринта 100/100.


от wnvko (3123 точки)


0

Source

Стандартен DFS + Backtracking. Масивът от стрингове не е най-ефективният от към ресурси вариант, но не ми се занимаваше да го преправям, а и така изглежда по-прегледно.


от stinger907 (307 точки)


0

Тук малко се увлякох и направих да се вижда как алгоритъма обхожда лабиринта - клетките, които посещава светват в червено :) Така много добре се вижда обхождането в ширина.

Labyrinth


от neutrino (3376 точки)