/AeroNetTestApp

AeorNet test application for interview

Primary LanguageJava

Алгоритм решения задачи:

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

2. Далее, используя алгоримт Дейкстры, для каждого мяча мы должны найти все кратчайшие возможные пути, ведущие от нашего мяча до дырки с соответствующим номером.

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

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