Python 3: BFS timeout issue, need help
Can any one tell why this code is timing out. It works fine for smaller input however it seems to be taking lot of time for a bigger input. What am I missing he
Can any one tell why this code is timing out. It works fine for smaller input however it seems to be taking lot of time for a bigger input. What am I missing here?\nYour input is highly appreciated.\n```\nclass Solution:\n    def __init__(self):\n        self.offsets = [(1,0),(-1,0),(0,1),(0,-1)]\n    def cutOffTree(self, forest: List[List[int]]) -> int:\n        # traverse the forest \n        # get all trees to be cut\n        n = len(forest)\n        m = len(forest[0])\n        treesToBeCut = []\n        for i in range(n):\n            for j in range(m):\n                if forest[i][j] > 1:\n                    treesToBeCut.append((i, j, forest[i][j]))\n        \n        # sort these trees to be cut in ascending order \n        # shortest first and the longest one last \n        treesToBeCut.sort(key=lambda x: x[2])\n        #print(treesToBeCut)\n        \n        # use this BFS to find the shortest path to all the \n        # trees, two at a time starting from 0, 0\n        \n        # start from the begining and go through\n        # all the trees that needs to be cut in the ascending order\n        src_x = src_y = totalDist = 0\n        for cur_x, cur_y, h in treesToBeCut:\n            d = self.bfs(forest, src_x, src_y, cur_x, cur_y, n, m)\n            if d < 0:\n                # if there is no path between source cell to target cell\n                return -1\n            \n            # add the distance to total distance\n            totalDist += d\n            \n            # change the source cell to to be current cell\n            src_x = cur_x\n            src_y = cur_y\n            \n        return totalDist\n    \n    # to find the shortest distance between any two nodes\n    # we will use BFS\n    def bfs(self, forest, src_x, src_y, target_x, target_y, n, m):\n        print((src_x, src_y), (target_x, target_y))\n        q = collections.deque([(src_x, src_y)])\n        seen = set()\n        level = 0\n        while q:\n            s = len(q)\n            for i in range(s):\n                cur_x, cur_y = q.popleft()\n                # if current cell is the target cell\n                if cur_x == target_x and cur_y == target_y:\n                    return level\n\n                # mark current node as visited\n                seen.add((cur_x, cur_y))\n\n                # find all the neighbours\n                for rowOffSet, colOffSet in self.offsets:\n                    nx = cur_x + rowOffSet\n                    ny = cur_y + colOffSet\n\n                    # if not valid do nothing \n                    if nx < 0 or nx >= n or ny < 0 or ny >= m or forest[nx][ny] == 0 or (nx, ny) in seen:\n                        continue\n\n                    # add the valid unseen node to the queue and increase the level\n                    q.append((nx, ny))\n                    \n            # increment level\n            level += 1\n        \n        # when there is no path between source and target cells\n        return -1\n        \n```
[]