Number of shortest paths of a knight in chessboard from A to B
<p>Here is the problem:</p>

<p>Given the input n = 4 x = 5, we must imagine a chessboard that is 4 squares across (x-axis) and 5 squares tall (y-axis). (This input changes, all the up to n = 200 x = 200)</p>

<p>Then, we are asked to determine the minimum shortest path from the bottom left square on the board to the top right square on the board for the Knight (the Knight can move 2 spaces on one axis, then 1 space on the other axis).</p>

<p>My current ideas:</p>

<p>Use a 2d array to store all the possible moves, perform breadth-first 
search(BFS) on the 2d array to find the shortest path.</p>

<p>Floyd-Warshall shortest path algorithm.</p>

<p>Create an adjacency list and perform BFS on that (but I think this would be inefficient).</p>

<p>To be honest though I don't really have a solid grasp on the logic.</p>

<p>Can anyone help me with psuedocode, python code, or even just a logical walk-through of the problem?</p>

<p>BFS is efficient enough for this problem as it's complexity is O(n*x) since you explore each cell only one time. For keeping the number of shortest paths, you just have to keep an auxiliary array to save them.</p>

<p>You can also use A* to solve this faster but it's not necessary in this case because it is a programming contest problem.</p>

<pre><code>dist = {}
ways = {}

def bfs():
    start = 1,1
    goal = 6,6

    queue = [start]
    dist[start] = 0
    ways[start] = 1

    while len(queue):
        cur = queue[0]
        queue.pop(0)
        if cur == goal:
            print "reached goal in %d moves and %d ways"%(dist[cur],ways[cur])
            return

        for move in [ (1,2),(2,1),(-1,-2),(-2,-1),(1,-2),(-1,2),(-2,1),(2,-1) ]:
            next_pos = cur[0]+move[0], cur[1]+move[1]
            if next_pos[0] &gt; goal[0] or next_pos[1] &gt; goal[1] or next_pos[0] &lt; 1 or next_pos[1] &lt; 1:
                continue
            if next_pos in dist and dist[next_pos] == dist[cur]+1:
                ways[next_pos] += ways[cur]
            if next_pos not in dist:
                dist[next_pos] = dist[cur]+1
                ways[next_pos] = ways[cur]
                queue.append(next_pos)

bfs()
</code></pre>

<p>Output</p>

<pre><code>reached goal in 4 moves and 4 ways
</code></pre>

<p><em>Note that the number of ways to reach the goal can get exponentially big</em></p>

python algorithm chess