Assume that the number of colors $$$c$$$ is fixed. Let $$$mx[i][j]$$$ represent the length of the continuous path ending at node $$$i$$$ with color $$$j$$$. How do we construct $$$mx$$$?

Let's try some approaches. For the connected component formed by the first $$$k$$$ nodes, we can use color 1 for all of them. In this case, the $$$i$$$-th node's $$$mx$$$ array (for $$$1 \le i \le k$$$) would be:
$$$mx[i] = [0, \dots, 0, i-1]$$$.

For the $$$(k+1)$$$-th node, we can use color 2 to connect the connected component formed by the first $$$k-1$$$ nodes. Thus, the $$$k$$$-th node's $$$mx$$$ array would be:
$$$mx[k+1] = [0, \dots, 1, 0]$$$.

For the $$$(k+2)$$$-th node, we can use color 2 to connect the connected component formed by the first $$$k-1$$$ nodes and color 1 to connect node $$$k$$$. In this case, the $$$(k+1)$$$-th node's $$$mx$$$ array would be:
$$$mx[k+2] = [0, \dots, 1, 1]$$$.

At this point, you might realize: The $$$i$$$-th node's $$$mx$$$ array is exactly the $$$(i-1)$$$ in base $$$k$$$ as a mask!

Claim $$$1$$$: for two indices $$$i$$$ and $$$j(i \lt j)$$$, $$$mx[i] \neq mx[j]$$$.

Proof $$$1$$$: if we use color $$$k$$$ to connect node $$$i$$$ and $$$j$$$, $$$mx[i][k]+1=mx[j][k]$$$ must hold.

So we can assign values to each node's $$$mx$$$ array using a $$$k$$$-base mask from $$$0$$$ to $$$n-1$$$, which gives us a lower bound on the answer.

Claim $$$2$$$: we can always reach this lower bound.

Proof $$$2$$$: for two indices $$$i$$$ and $$$j(i \lt j)$$$, find $$$k$$$ such that $$$mx[i][k] \lt mx[j][k]$$$, then use color $$$k$$$ to connect node $$$i$$$ and $$$j$$$.

• $$$a[1][2]=a[2][1]=a[n-1][m]=a[n][m-1]='.'$$$ must hold.

• We can simply find the shortest path using BFS.

• Robot B can follow behind Robot A. That is, Return to $$$(1,1)$$$ in two steps, then "track" A. So the lower bound of our answer is the shortest path length+2.

• The only remaining problem is: how to find two disjoint shortest paths?

To to find two disjoint shortest paths, we have a classic idea: only walk along the edge of the shortest path tree.

That is, note $$$dis[x]$$$ as the distance from $$$s$$$ to $$$x$$$, we only remain edges $$$u \rightarrow v$$$ such that $$$dis[u]+1=dis[v]$$$.

Official editorial said:

Once all cells on the shortest path are known, sort them by their distance to $$$(1, 1)$$$, i.e., $$$d_1(x, y)$$$ values. Now, if there’s any “level” of the shortest path that contains exactly one cell, every shortest path much pass through this cell and two disjoint paths cannot exist. Otherwise, a valid pair of paths will always exist.

I am confused about how to prove this. After thinking, I came up with a rigorous proof using the maximum flow minimum cut theorem.

Since each node can be visited at most once, we need to split node $$$x$$$ into $$$x$$$ -> $$$x'$$$ when constructing the flow graph. Let's say $$$dis[x]=dis[x']$$$.

What I want to prove is that if the number of nodes at all "levels" is greater than $$$1$$$ (except for $$$s$$$ and $$$t$$$), then for all cuts, the number of cut edges is always greater than $$$1$$$.

Let $$$D[i]$$$ be the set of all nodes $$$x$$$ such that $$$dis[x] = i$$$.

Let's start with an arbitrary $$$D[i]$$$. According to our assumption, there are at least two pairs of $$$x$$$->$$$x'$$$ in $$$D[i]$$$. We will discuss three cases.

-Case $$$1$$$: $$$x$$$ and $$$x'$$$ are from different $$$S/T$$$ sets. In this case, $$$x$$$->$$$x'$$$ is already a cut edge.

-Case $$$2$$$: $$$x$$$ and $$$x'$$$ are both from $$$S$$$. In this case, by following the successors of $$$x'$$$, we can always find a cut edge.

-Case $$$3$$$: $$$x$$$ and $$$x'$$$ are both from $$$T$$$. In this case, by following the predecessors of $$$x$$$, we can always find a cut edge.

In this way, we can always find at least two different cutting edges. Q.E.D.

Note |D[i]| as the number of nodes of $$$D[i]$$$($$$s$$$ and $$$t$$$ are excluded). If $$$min(D[i])=k$$$, can we find $$$k$$$ disjoint shortest path for any $$$k$$$?

No. It only holds when $$$k=2$$$.

The following is the counter case for $$$k=3$$$:

After retaining only the edges on the shortest path tree, we can run a maximum flow algorithm to check if the maximum flow is $$$2$$$. Due to the special nature of the graph, the time complexity is equivalent to performing two BFS traversals on the graph.