#!/usr/bin/env python
# coding: utf-8

# If we take each intersection as a node and each direction as an edge, then we can see that this is just a [DAG](https://en.wikipedia.org/wiki/Directed_acyclic_graph).
# To count the possible paths from start to end we can observe than the number of paths of a node is the sum of the number of paths of its children. We do a [topological sort](https://en.wikipedia.org/wiki/Topological_sorting) of the graph and starting from the bottom right corner we go back calculating the number of paths. Since for each $v$ the paths of its children have already been calculated, we need to just sum them.

# In[3]:


import networkx as nx


def build_graph(n):
    g = nx.DiGraph()

    def i(col, row):
        return n * (row - 1) + col

    for c in range(1, n + 1):
        for r in range(1, n + 1):
            if c != n:
                g.add_edge(i(c, r), i(c + 1, r))
            if r != n:
                g.add_edge(i(c, r), i(c, r + 1))
    return g


# Kahn's algorithm
def topological_sort(g):
    g = g.copy()
    sorted_nodes = []
    without_incoming_edges = [1]
    while without_incoming_edges:
        n = without_incoming_edges.pop()
        sorted_nodes.append(n)
        edges_to_remove = []
        for s in g.successors(n):
            edges_to_remove.append((n, s))
            if g.in_degree(s) == 1:  # the edge n -> s will be removed, so we check for 1 instead of 0
                without_incoming_edges.append(s)
        for (n, s) in edges_to_remove:
            g.remove_edge(n, s)
    return sorted_nodes


def count_paths(g, f, t):
    sorted_nodes = topological_sort(g)
    cache = {t: 1}
    for n in reversed(sorted_nodes[:-1]):
        count = 0
        for s in g.successors(n):
            count += cache[s]
        cache[n] = count
    return cache[f]


nodes = 20 + 1
g = build_graph(nodes)
count_paths(g, 1, nodes * nodes)