Где приземлится мяч. Решение задачи.

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

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.

class Solution:
    def findBall(self, grid: List[List[int]]) -> List[int]:
        N = len(grid[0])-1
        output = list(range(N+1))
        for i in range(len(grid)):
            for index,pos in enumerate(output):
                if pos == -1 :
                    continue
                if ((pos == 0 and grid[i][pos]==-1) or
                    (pos == N and grid[i][pos] == 1)):
                    output[index] = -1
                elif grid[i][pos] == 1 and grid[i][pos]+grid[i][pos+1]!=0:
                    output[index]+=1
                elif grid[i][pos] == -1 and grid[i][pos]+grid[i][pos-1] !=0:
                    output[index]-=1
                else:
                    output[index] = -1
        return output