¿Número de rutas entre puntos en una cuadrícula con nodos bloqueados?

Una forma de hacerlo es por inclusión-exclusión .

Basta con excluir el nodo inferior prohibido de cada columna. En tu ejemplo, estos son los nodos.$(0,2)$,$(1,2)$,$(2,4)$y$(3,5)$. Denote el conjunto de estos nodos por$N$y el número de caminos que usan todos los nodos en un conjunto$S$por$a_S$. Entonces por inclusión-exclusión el número de caminos admisibles es

$$\sum_{S\subseteq N}(-1)^{|S|}a_S\;.$$

Hay$\binom{x_2-x_1+y_2-y_1}{x_2-x_1}$caminos desde$(x_1,y_1)$a$(x_2,y_2)$. Al insertar los nodos prohibidos como pasos intermedios, podemos escribir la suma anterior como

$$\sum_{S\subseteq N}(-1)^{|S|}\prod_{i=0}^{|S|}\binom{y_{s_{i+1}}-y_{s_i}+x_{s_{i+1}}-x_{s_i}}{x_{s_{i+1}}-x_{s_i}}\;,$$

dónde$s_1,\ldots,s_{|S|}$son los nodos en$S$en orden ascendente$x$coordenadas, y$s_0=A$y$s_{|S|+1}=B$.

En tu ejemplo, esto es

$$\binom{10}5-\binom20\binom85-\binom31\binom74-\binom62\binom43-\binom83\binom22+\binom20\binom11\binom74+\binom20\binom42\binom43+\binom20\binom63\binom22+\binom31\binom31\binom43+\binom31\binom52\binom22+\binom62\binom21\binom22-\binom20\binom11\binom31\binom43-\binom20\binom11\binom52\binom22-\binom20\binom42\binom21\binom22-\binom31\binom31\binom21\binom22+\binom20\binom11\binom31\binom21\binom22 \\[15pt] =104\;.$$

Dejar$p(x,y)$sea ​​el número de tales caminos desde$(0,0)$a$(x,y)$. Al considerar el último paso en$(x,y)$, encontramos eso

$$p(x,y)=p(x-1,y)+p(x,y-1),$$ dónde$p(x,y)=0$si$x<0$,$y<0$, o$(x,y)$está bloqueado. La condición de frontera es$p(0,0)=1$, y desea calcular$p(5,5)$.

$$\begin{matrix} 0 &0 &0 &0 &32 &\color{red}{104} \\ 0 &0 &0 &10 &32 &72 \\ 0 &0 &3 &10 &22 &40 \\ 0 &0 &3 &7 &12 &18 \\ 1 &2 &3 &4 &5 &6 \\ 1 &1 &1 &1 &1 &1 \\ \end{matrix}$$

Definir$P_{x,y}$como el número de camino para llegar al punto$(x,y)$de$(0,0)$. Podemos llegar al punto$(x,y)$de$(x-1,y)$o$(x,y-1)$. Por lo tanto se aplica la siguiente expresión:$P_{x,y}=P_{x-1,y}+P_{x,y-1}$. Si se le permite usar la computadora, es muy simple. Por ejemplo, uso Excel como a continuación:

acabo de ingresar$1$en la celda inferior izquierda, luego$0$en las celdas bloqueadas.

Esto puede no ser importante, pero un caso muy especial es si las celdas bloqueadas forman un triángulo en la esquina superior izquierda, siendo la primera celda bloqueada$(0,a)$

El número de ruta desde$(0,0)$a$(x,y)$convertirse$\binom{x+y}{x}-\binom{x+y}{x+a}$

Digamos que tenemos un gráfico de cuadrícula de celosía de tamaño$n$. Ahora ponemos obstáculos en este gráfico con la siguiente regla:
si ponemos un obstáculo en un nodo, también ponemos obstáculos en todos los nodos al norte y al oeste de él.

En otras palabras, nuestros obstáculos siempre forman una pared que segmenta el gráfico en una parte que se puede atravesar y una parte que está bloqueada.
Llamemos a los nodos de obstáculos que no tienen nodos de obstáculos al sur o al este "nodos de obstáculos externos".

Podemos desmontar el gráfico original en una serie de gráficos de cuadrícula rectangular (sin obstáculos):

Ahora contamos los caminos de A a B usando los bordes entre las cuadrículas rectangulares.

Una ruta de ejemplo:

Dejar$(x_1,y_1), ..., (x_k,y_k)$ser los nodos de obstáculo exterior.

si tenemos un$a\times b$cuadrícula rectangular (es decir,$(0,0)$a$(a-1,b-1)$), entonces hay$\binom {a+b}{a,b} = \binom{a+b}{a}$maneras de llegar desde la esquina suroeste a la esquina noreste.
De manera similar, tenemos que el número de caminos desde$(a_1,b_1)$a$(a_2,b_2)$es

$$\text{paths}(\pmatrix{a_1\\b_1},\pmatrix{a_2\\b_2}) := \binom{(a_2-a_1) + (b_2-b_1)}{a_2-a_1}$$

Usando esto, nuestra recursividad es:

$$P(x,y) = \begin{cases} \sum_{i=x_{\mu-1} +1}^x\text{paths}\left(\pmatrix{i\\y_{\mu-1}},\pmatrix{x\\y-1}\right)\cdot P(i,y_{\mu-1}) ,&\text{ if }\, \exists \mu: y = y_\mu \,\,\land\,\, x_\mu<x\le n \\ 1,&\text{ if } x=y=0 \\ \end{cases}$$ El primer caso representa la situación en la que se nos da un nodo que está en la parte inferior de una de las cuadrículas rectangulares, y rastreamos las rutas a este nodo hasta las rutas a los nodos inferiores de la cuadrícula rectangular hacia el sur.

Añadiendo$(x_0,y_0) = (-1,0)$y$(x_{k+1},y_{k+1}) = (n,n-1)$,
$P(n,n)$nos da el número de caminos desde$(0,0)$a$(n-1,n-1)$.

Formulando esta recursividad como un programa dinámico, se puede lograr un tiempo de ejecución de$O(nk)$(dónde$k$es el número de nodos de obstáculos exteriores, para los que siempre se cumple$k\le n$).