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 careful consideration, I came up with a rigorous proof.

I used the maximum flow minimum cut theorem.

Since each node is 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']$$$.

Let's call the graph before and after split as "original graph" and "split graph". When there is no $$$x$$$ and $$$x'$$$ belongs to different $$$S/T$$$ sets, it is more convenient to analyze on the "original graph".

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 in the "split graph", 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$$$.

• Case $$$1$$$: for each $$$D[i]$$$, there is no $$$x$$$, $$$y$$$ belongs to $$$D[i]$$$ satisfies $$$x∈S$$$ and $$$y∈T$$$.

-- In

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.