DFS and BFS solutions in python
Convert the problem into tree traversing\nThe question is actually equivalent to a tree traverse problem.\nConsider the start point as the root, the children of
## Convert the problem into tree traversing\nThe question is actually equivalent to a tree traverse problem.\nConsider the start point as the root, the children of which are the in-board coordinates out of all 8 possible positions. The out-of-board positions are pruned. \nLet `p(K, r, c)` be the in-board possiblity that Knight starts at `(r, c)` and moves `K` steps.\nExample:\n ```\n K = 2, N = 3, r = 0, c = 0\nStart:\n\t\t\t\t\t\t\t\t\t\t\t\t\tK 0 0\n\t\t\t\t\t\t\t\t\t\t\t\t\t0 0 0\n\t\t\t\t\t\t\t\t\t\t\t\t\t0 0 0\n\t\t\t\t\t\t\t\t\t\t\t\tp(2, 0, 0)\n\t\t\t\t\t\t\t\t\n1st Move:\n\t\t\t\t\t\t\t\t\t0 0 0                               0 0 0\n\t\t\t\t\t\t\t\t\t0 0 0                               0 0 K\n\t\t\t\t\t\t\t\t\t0 K 0                               0 0 0\n\t\t\t\t\t\t\t\tp(1, 2, 1)                           p(1, 1, 2)\n\n2nd Move:\n\t\t\t\t\t\t\tK 0 0            0 0 K           K 0 0        0 0 0\n\t\t\t\t\t\t\t0 0 0            0 0 0           0 0 0        0 0 0\n\t\t\t\t\t\t\t0 0 0            0 0 0           0 0 0        K 0 0\n\t\t\t\t\t\t\t  (1)             (2)             (3)          (4)\n\t\t\t\t   \t\tp(0, 0, 0)        p(0, 0, 2)      p(0, 0, 0)    p(0, 2, 0)\n\n```\t  \n> The last move has four children, hence the in-board posibility would be `p(2, 0, 0) = 4 * (1/8)^2`.\n> Therefore, all we need to do is to count how many nodes there are in the last level, say `count`. The in-board possibility would be `count * (1 / 8) ^ K`\n\n\nAs shown in the example, the possibility that K-th move remains on board, or p(K, r, c),  can be expressed in two ways:\n- (DFS) Each in-board child contributes 1 / 8 * p(K-1, next_r, next_c) to the final probability. Hence, the in-board possiblity of tree node (r, c) in step k would be the sum of all on-board children in-board possibility weighted uniformly by 1/8.\n- (BFS) For each generation of children, or in other words, for all tree nodes in level k, the in-board possibility would be he count of all in-board positions over all the count of all possible positions, including in-board and out-of-board, which would be 8 ^ k.\n\n> Note that there will be duplicate positions in each level like node (1) and (3) in the example, it is necessary to track the count of duplicates. For DFS a memo is used to track duplicate subproblems, while for BFS each node has a weight to indicate the count of duplicates.\n\n## BFS Solution\nThe possibility that the knight remains on board on the K-th move can be calculated as:\n`p = (count of all K-th moves ending up within board) / (8 ^ K)`\n```python\ndef knightProbability(self, N: int, K: int, r: int, c: int) -> float:\n\t"""\n\tBFS, use a set to track the nodes in a tree remaining in the board in each step\n\tTime: O(8 * N ^ 2 * K)\n\tSpace: O(N ^ 2)\n\t"""\n\tq = {(r, c): 1}\n\tlevel = 0\n\tdirections = {(dx, dy) for dx in (-2, -1, 1, 2) for dy in (-2, -1, 1, 2) if abs(dx) + abs(dy) == 3}\n\tis_in_board = lambda r, c: 0 <= r < N and 0 <= c < N\n\twhile level < K and q:\n\t\tnext_q = collections.defaultdict(int)\n\t\tfor coord, count in q.items():\n\t\t\tx, y = coord\n\t\t\tfor dx, dy in directions:\n\t\t\t\tif is_in_board(x + dx, y + dy):\n\t\t\t\t\tnext_q[(x + dx, y + dy)] += count\n\t\tq = next_q\n\t\tlevel += 1\n\t\t# print(f\'Level {level}: {q}\')\n\n\treturn sum(q.values()) / 8 ** K\n```\n## DFS Solution\n```python \ndef knightProbability(self, N: int, K: int, r: int, c: int) -> float:\n\t"""\n\tdfs with memo\n\tTime: O(K*N^2)\n\tSpace: O(K*N^2)\n\t"""\n\tis_in_board = lambda r, c: 0 <= r < N and  0 <= c < N\n\tdirections = {(dx, dy) for dx in (-2, -1, 1, 2) for dy in (-2, -1, 1, 2) if abs(dx) + abs(dy) == 3}\n\tmemo = {}\n\tdef dfs(K, r, c):\n\t\tnonlocal memo\n\t\tif K == 0:\n\t\t\treturn 1\n\t\tif (K, r, c) in memo:\n\t\t\treturn memo[(K, r, c)]\n\n\t\tp = 0\n\t\tfor dx, dy in directions:\n\t\t\tx, y = r + dx, c + dy\n\t\t\tif is_in_board(x, y):\n\t\t\t\tp += dfs(K - 1, x, y) / 8\n\t\tmemo[(K, r, c)] = p\n\t\treturn p\n\n\treturn dfs(K, r, c)\n```
['Depth-First Search', 'Breadth-First Search', 'Recursion', 'Python']