Софтуерно Инженерство
Loading...
+ Нов въпрос
jicata avatar jicata Trainer 7 Точки

За дъното:

Като дъно (дъна) може да използваме същите, които използвахме в задачата за намиране на всички пътища в лабиринт(видеото го има качено в инстанцията на курса). Едно възможно дъно е излизане от матрицата. 

За новите зони:

Съвсем отделно от цялата рекурсивна логика на задачата можем просто да си направим един метод който да намира първата свободна клетка в наш'та матрица. Като съответно всички полета които сме обходили чрез рекурсивният метод трябва да бъдат отбелязани като обходени.

Cheers!

 

2
07/04/2016 18:39:05
tilchev92 avatar tilchev92 Trainer 128 Точки

Моето решение май както винаги е излишно усложнено (ползва DFS/BFS), но заповядай ако ти е полезно.

Когато посетя клетка в дадена област я маркирам с буква (клетките от една област са с една буква). Метода за обхождане на група го викам само като срещна клетка която е празна -> ' '. Реално не ползвам рекурсия, но пък проверявам всяка клетка от матрицата.

2
07/04/2016 21:35:55
mishomihaylov avatar mishomihaylov 67 Точки

Здравей!

Предлагам ти и моето решение. Идеята зад него е, че имаме един метод (FindAreas), който обхожда цялата матрица за да намери някаква празна клетка. След като я намери вика рекурсивен метод (TransverseArea) с DFS и започва да запълва от където е минал и брои колко клетки е обходил/запълнил. Дъното тук е, когато се опита да излезе от матрицата или намери стена ('*'). Така намира дадена area. Връща се във FindAreas и продължава да търси за празни клетки. Когато търсенето приключи се извеждат резултатите.

--- Source Code ---

1
08/04/2016 10:13:27
Vladix avatar Vladix 75 Точки

Здравейте,

Разгледах решенията ви на тази задачка и логиката горе-долу е еднаква на всички. И аз се справих с проблема по същия начин, обикаляме през цялата матрица и ако попаднем на празно място почваме маркиране на текущото поле и след това продължаваме да си итерираме през матрицата. Само че по този начи сложността ни се увеличава, защото имаме повтарящи се итерации. Интересно ми е да разбера дали някой е успял да измисли по - хитро решение (ако съществува такова) на проблема нещо линейно (O(n)) и ако може да го сподели.

Поздрави 

0