One Shared Corridor#13119

One Shared Corridor (Shpjegimi i zgjidhjes)

Solution

We need to count pairs of paths that have exactly one common contiguous segment containing at least two cells.

Each path can only move right or down. Let $A = (1, a)$ A=(1,a) and $B = (b, 1)$ B=(b,1) be the starting cells, and let $C = (c, w)$ C=(c,w) and $D = (h, d)$ D=(h,d) be the destination cells.

The key observation is that every compatible pair of paths can be uniquely divided into three parts:

Two vertex-disjoint paths from $A$ and $B$ to the first common cell.
One shared path containing at least one edge.
Two vertex-disjoint paths from the last common cell to $C$ and $D$ .

We will count these three parts using dynamic programming.

Counting paths

First, calculate four arrays:

$F_{A} (v)$ F_A(v) — the number of paths from $A$ to cell $v$ .
$F_{B} (v)$ F_B(v) — the number of paths from $B$ to cell $v$ .
$G_{C} (v)$ G_C(v) — the number of paths from cell $v$ to $C$ .
$G_{D} (v)$ G_D(v) — the number of paths from cell $v$ to $D$ .

All paths must use only free cells and move right or down.

The first two arrays can be calculated from top to bottom and from left to right. For example, for a free cell $(i, j)$ ,

F_{A} (i, j) = F_{A} (i - 1, j) + F_{A} (i, j - 1),

F_A(i,j)=F_A(i-1,j)+F_A(i,j-1),

with the initial value $F_{A} (A) = 1$ F_A(A)=1.

Similarly, $G_{C}$ G_C and $G_{D}$ G_D can be calculated in reverse order:

G_{C} (i, j) = G_{C} (i + 1, j) + G_{C} (i, j + 1) .

G_C(i,j)=G_C(i+1,j)+G_C(i,j+1).

All values are calculated modulo $1 0^{9} + 7$ 10^9+7.

First common cell

Let $v = (i, j)$ v=(i,j) be the first common cell of the two paths.

Since the paths do not intersect before $v$ , they must enter this cell from different directions.

Denote the cell above $v$ by $U = (i - 1, j)$ U=(i-1,j) and the cell to its left by $L = (i, j - 1)$ L=(i,j-1).

Because the first path starts on the upper boundary and the second path starts on the left boundary, the first path must enter $v$ from $U$ , and the second path must enter from $L$ .

We need to count pairs of paths from $A$ to $U$ and from $B$ to $L$ that do not share any cells.

Using the Lindström–Gessel–Viennot lemma, this number equals

j o in (v) = F_{A} (U) F_{B} (L) - F_{A} (L) F_{B} (U) .

join(v)=F_A(U)F_B(L)-F_A(L)F_B(U).

The subtraction removes pairs of paths that intersect before reaching $v$ . Due to the relative positions of the starting and ending cells, the opposite pairing cannot be vertex-disjoint.

For cells on the upper or left boundary, and for blocked cells, we set $j o in (v) = 0$ join(v)=0.

Thus, $j o in (v)$ join(v) is the number of ways for the two couriers to meet for the first time at cell $v$ .

Last common cell

Now let $v = (i, j)$ v=(i,j) be the last common cell.

After leaving $v$ , the paths must immediately separate and never intersect again.

Denote the cell to the right of $v$ by $R = (i, j + 1)$ R=(i,j+1) and the cell below it by $T = (i + 1, j)$ T=(i+1,j).

Since the first courier finishes on the right boundary and the second courier finishes on the bottom boundary, the first path must leave through $R$ , while the second must leave through $T$ .

Using the same lemma, the number of ways to finish the two paths without further intersections is

s pl i t (v) = G_{C} (R) G_{D} (T) - G_{C} (T) G_{D} (R) .

split(v)=G_C(R)G_D(T)-G_C(T)G_D(R).

For cells on the right or bottom boundary, and for blocked cells, we set $s pl i t (v) = 0$ split(v)=0.

Shared segment

We have calculated the number of ways to start and finish the common segment. It remains to connect its endpoints.

Let $d p (v)$ be the number of ways to choose the first common cell and construct a shared path ending at $v$ , such that the shared path contains at least one edge.

For each cell $u$ , we can start a shared segment in $j o in (u)$ ways.

However, we cannot immediately finish it at $u$ , because the common segment must contain at least two cells.

Therefore, these new segments contribute only when we move from $u$ to one of its neighboring cells.

For a free cell $v = (i, j)$ v=(i,j), let $U$ and $L$ again denote its upper and left neighbors.

Then

d p (v) = d p (U) + j o in (U) + d p (L) + j o in (L) .

dp(v)=dp(U)+join(U)+dp(L)+join(L).

Here, $d p (U)$ and $d p (L)$ count extensions of existing shared segments, while $j o in (U)$ join(U) and $j o in (L)$ count shared segments that begin at the corresponding neighboring cell.

This guarantees that every counted shared segment contains at least one edge.

Finally, if the shared segment ends at $v$ , there are $s pl i t (v)$ split(v) ways to finish both routes without further intersections.

Therefore, the answer is

an s = v \sum d p (v) \cdot s pl i t (v) (mod 1 0^{9} + 7) .

ans=\sum_v dp(v)\cdot split(v)\pmod{10^9+7}.

Every compatible pair of routes has a unique first and last common cell, so it is counted exactly once.

Complexity Analysis

Each of the four path-counting arrays can be calculated in $O (h w)$ time.

The values $j o in (v)$ join(v), $s pl i t (v)$ split(v) and $d p (v)$ are also calculated in $O (1)$ time per cell.

Therefore, the total time complexity is $O (h w)$ , and the space complexity is $O (h w)$ .

Implementation

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int mod = 1e9 + 7;

void solve() {
    int h, w;
    cin >> h >> w;

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    --a; --b; --c; --d;

    vector<string> g(h);
    for (auto &s : g) cin >> s;

    int n = h * w;

    vector<int> fromA(n), fromB(n);
    vector<int> join(n), dp(n);
    vector<int> toC(n), toD(n);

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            int v = i * w + j;

            if (g[i][j] == '#') continue;

            int up = v - w;
            int left = v - 1;

            ll x = (i == 0 && j == a);
            ll y = (i == b && j == 0);

            if (i) {
                x += fromA[up];
                y += fromB[up];
            }

            if (j) {
                x += fromA[left];
                y += fromB[left];
            }

            fromA[v] = x % mod;
            fromB[v] = y % mod;

            if (i && j) {
                int t = 1LL * fromA[up] * fromB[left] % mod;

                t -= 1LL * fromA[left] * fromB[up] % mod;

                if (t < 0) t += mod;

                join[v] = t;
            }

            ll z = 0;

            if (i) {
                z += dp[up] + join[up];
            }

            if (j) {
                z += dp[left] + join[left];
            }

            dp[v] = z % mod;
        }
    }

    int ans = 0;

    for (int i = h - 1; i >= 0; i--) {
        for (int j = w - 1; j >= 0; j--) {
            int v = i * w + j;

            if (g[i][j] == '#') continue;

            int down = v + w;
            int right = v + 1;

            ll x = (i == c && j == w - 1);
            ll y = (i == h - 1 && j == d);

            if (i + 1 < h) {
                x += toC[down];
                y += toD[down];
            }

            if (j + 1 < w) {
                x += toC[right];
                y += toD[right];
            }

            toC[v] = x % mod;
            toD[v] = y % mod;

            if (i + 1 < h && j + 1 < w) {
                int t = 1LL * toC[right] * toD[down] % mod;

                t -= 1LL * toC[down] * toD[right] % mod;

                if (t < 0) t += mod;

                ans = (ans + 1LL * dp[v] * t) % mod;
            }
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}