<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

378. Save the Fisher
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Peter has a boat. He loves to use it for fishing on the Berland Lake. But today an accident happen with him. A huge fish ate the hook, and when Peter tried to take the fish out of the lake, he suddenly discovered that the fish was stronger. Unfortunately Peter was unable to stay on the board and he fell down into the water. But he did not want to lose such a catch. So the fish took him somewhere...

The Peter is now somewhere inside the lake and lost his boat and his rod. Luckily, Peter knows each bermeter of this lake (bermeter is the length measurement unit in Berland). You will help Peter to create the plan to save himself.

The lake is a rectangle of N x M bermeters. Let us consider an N x M grid of 1 x 1 squares within this rectangle. Peter can move within the lake according to the following:

When Peter is in the center of some cell, his real velocity is the sum of the vectors of the velocity of the flow and Peter's movement vector. He moves with this velocity until he reaches the center of some other cell, where his new velocity will be calculated independently of the previous velocity. The velocity could not be changed in any place other than the center of some cell.
For each cell you know the flow velocity, it can be one of the following five vectors: 1: (0, -1), 2: (0, 1), 3: (1, 0), 4: (-1, 0), 0: (0, 0). All velocities are in bermeters per minute. Peter's movement vector also is chosen among these five vectors, and he can change it any time when he is in the center of some cell. E. g. if the flow velocity is (0, -1) and the Peter's movement vector is (1, 0) then the resulting velocity will be (1, -1), i. e. Peter will move diagonally. Note that Peter may stay in the center of any cell during any period of time (may be non-integer amount of minutes) by selecting movement vector opposite to the flow speed. If Peter moves with the same vector as the flow, he will reach the center of the next cell in half a minute.
The boat moves according to the same laws as Peter, but the boat's movement speed is always zero.
Peter is saved when he is in the same point as the boat (it is not neccessary to reach the center of any cell) or if he reaches the shore of the lake. The boat can also reach the shore, if it happens, the boat stops there.




Input
The first line of the input contains two integers N and M (1 ≤ N, M≤ 500) separated by one space. Each of the next N lines contains M digits each — the description of the lake. The digit is the number of the flow velocity vector in the corresponding cell, according to the statement. The last two lines contain two integers each, the first corresponds to initial coordinates of Peter, the second is for the boat.

Output
Output the minimal time in minutes required for Peter to save himself, rounded up to two digits after decimal point. If Peter is not able to save himself, output "SOS".

Example(s)
sample input
sample output
4 6
222222
444444
444444
111111
5 3
6 2
2.00

sample input
sample output
3 2
00
32
11
1 2
2 3
0.67

sample input
sample output
3 5
32240
33442
31140
2 2
5 2
SOS

<|response|>
## 1. Abridged problem statement

The lake is an `N × M` grid. Each cell has a water-flow vector:

```text
0: (0, 0)
1: (0, -1)
2: (0, 1)
3: (1, 0)
4: (-1, 0)
```

Peter starts at the center of one cell. His boat starts at the center of another cell.

At every cell center, Peter chooses one of the same five vectors as his own swimming vector. His actual velocity is:

```text
flow vector + swimming vector
```

He moves with this velocity until reaching another cell center, where he may choose again. He may also wait at a center by cancelling the flow.

The boat has no own movement, so it only follows the flow.

Peter is saved if:

1. he reaches the shore, or
2. he reaches the same point as the boat, possibly inside a cell edge.

Find the minimum time, or print `SOS` if impossible.

---

## 2. Key observations needed to solve the problem

### Observation 1: Peter’s center-to-center times are only `0.5` or `1`

From a cell center, Peter’s resulting velocity can be:

- zero — he stays,
- horizontal/vertical speed `1`,
- horizontal/vertical speed `2`,
- diagonal speed with components `±1`.

Therefore, if Peter reaches another cell center:

- speed `2` along one axis means time `0.5`,
- otherwise the time is `1`.

So we can compute shortest times to all cell centers in units of half-minutes.

---

### Observation 2: Peter can wait at any reachable center

If Peter can reach a center at time `t`, then he can also be there at any later time, because he can choose the vector opposite to the flow and stay still.

This is important for meeting the boat.

---

### Observation 3: The boat path is deterministic

The boat only follows the flow. From each cell it has at most one next cell.

Therefore the boat path must eventually:

1. stop in a zero-flow cell,
2. leave the grid and reach the shore,
3. enter a cycle.

We can simulate this path in `O(NM)` time.

---

### Observation 4: Peter may escape directly to the shore

From any reachable cell center, Peter can choose a velocity. If he reaches the shore before reaching another cell center, he is saved.

So after computing shortest distances to centers, we test all possible velocities from each reachable center.

---

### Observation 5: Meeting the boat happens either at a center or inside a boat edge

The boat moves only along horizontal/vertical edges between neighboring cell centers.

Peter can meet it:

1. at a cell center,
2. inside an edge while coming head-on from the next cell,
3. inside an edge while chasing from the same cell.

Those are the only useful inside-edge cases.

---

## 3. Full solution approach

### Step 1: Compute Peter’s shortest arrival time to every center

Build a graph where each cell is a vertex.

From cell `(r, c)`:

1. take the cell flow vector,
2. try all five swimming vectors,
3. add them,
4. if the resulting velocity is not zero, it points to a neighboring center.

The edge cost is:

```text
1 half-minute if speed is 2
2 half-minutes otherwise
```

Since edge weights are only `1` and `2`, we can use Dial’s algorithm with three buckets instead of Dijkstra.

Complexity:

```text
O(NM)
```

---

### Step 2: Try direct escape to the shore

For every reachable cell center and every possible velocity:

- compute the time to hit a vertical shore,
- compute the time to hit a horizontal shore,
- take the minimum.

This escape is valid if the shore is reached before or exactly when Peter would reach another center.

Update the answer with:

```text
dist[cell] + time_to_shore
```

---

### Step 3: Simulate the boat

Starting from the boat’s initial cell:

- record every visited cell and its visiting time,
- if a zero-flow cell is reached, the boat stays there forever,
- if the next cell is outside, the boat reaches the shore,
- if a cell is repeated, a cycle is found.

For cycle cells, the boat visits them at times:

```text
base_time + k * period
```

---

### Step 4: Meet the boat at centers

For every cell visited by the boat:

- if it is in the non-cyclic prefix, the boat visits it once,
- if it is in the cycle, the boat visits it periodically,
- if the boat stops there, it stays forever.

Peter can meet the boat at that center if he can arrive no later than one of those visit times.

---

### Step 5: Meet the boat inside an edge

Suppose the boat moves from `A` to `A'` during time interval:

```text
[t, t + 1]
```

#### Case 1: Peter comes head-on from `A'`

Peter starts from `A'` and moves toward `A`.

This is possible only if Peter can move along that edge toward `A`.

His speed `sp` is:

- `2` if the flow at `A'` points toward `A`,
- `1` if the flow at `A'` is zero.

If Peter reaches `A'` at time `d`, then the meeting time is:

```text
meet = (1 + t + sp * d) / (sp + 1)
```

The meeting point lies inside the edge iff:

```text
t ∈ [d - 1, d + 1 / sp]
```

For cycle edges, shift `t` by multiples of the cycle period until it fits this interval.

---

#### Case 2: Peter chases the boat from `A`

Peter starts from `A` after the boat has left and moves in the same direction.

He can catch the boat only with speed `2`, so the flow at `A` must point in the boat direction.

If Peter reaches `A` at time `d`, then:

```text
meet = 2d - t
```

This is valid iff:

```text
d ∈ [t, t + 0.5]
```

Equivalently:

```text
t ∈ [d - 0.5, d]
```

Again, for cycle edges, shift `t` forward by multiples of the period.

---

### Final answer

Take the minimum among:

1. direct escape to shore,
2. meeting at centers,
3. meeting inside boat edges.

If no candidate exists, print:

```text
SOS
```

Otherwise print the minimum time with two digits after the decimal point.

---

## 4. C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int FX[5] = {0, 0, 0, 1, -1};
const int FY[5] = {0, -1, 1, 0, 0};

int n, m;
vector<string> grid;
int peter_x, peter_y, boat_x, boat_y;

void read() {
    cin >> n >> m;
    grid.assign(n, "");
    for(int r = 0; r < n; r++) {
        cin >> grid[r];
    }

    cin >> peter_x >> peter_y >> boat_x >> boat_y;
}

void solve() {
    // Cell (col c, row r) has its centre at the point (c, r); the lake occupies
    // x in [-0.5, m-0.5], y in [-0.5, n-0.5]. The flow digit picks one of five
    // vectors and Peter adds one of the same five, so a resulting velocity has
    // each component in {-2,-1,0,1,2}: along the flow axis he moves at speed 2
    // (next centre in 0.5 min), at speed 1 with no push (1 min), diagonally at
    // speed sqrt(2) to a diagonal neighbour (1 min), or stays put by cancelling
    // the flow. Every Peter-to-centre time is therefore a multiple of 0.5, so a
    // shortest path with edge weights 1 and 2 in half-minutes gives dist[c],
    // the earliest he can sit in each centre (he may then wait there
    // arbitrarily). Because the weights are only 1 and 2 the live frontier
    // spans at most three consecutive distances, so Dial's algorithm with
    // buckets keyed by distance % 3 settles every cell in order without a heap.
    //
    // The boat only drifts, so from any cell it has a single successor: it
    // steps one axis-aligned cell per minute. A deterministic walk with one
    // successor each must, within at most n*m steps, either stop on a
    // still-water cell, step off the board through the shore, or revisit a cell
    // it has already seen. The first repeated cell is where the trajectory
    // folds into a cycle: the prefix before it is walked once, and from there
    // the boat loops forever with period = (current time) - (time the repeated
    // cell was first seen). So a prefix cell is occupied at one fixed time,
    // while a cycle cell is occupied at base + k*period for every k >= 0; the
    // move from the last recorded cell back to the cycle's entry is itself an
    // edge of the loop and is added explicitly. Reaching the shore is always a
    // save, so one candidate answer is the min over cells of dist[c] plus the
    // time to push out of the nearest wall from c (half the usual cell-crossing
    // time, since a wall sits half a cell from the centre).
    //
    // To meet the boat there are three ways, each turned into the earliest
    // valid time and minimised together with the shore candidate. First, Peter
    // can sit in a centre the boat visits: he is fine as long as he arrives no
    // later than the boat, so the candidate is the earliest visit time >=
    // dist[c] (just the single time for a prefix cell, or base + k*period
    // rounded up past dist[c] for a cycle cell, or max(dist[c], stop_time) for
    // a stalled boat).
    //
    // Second, while the boat crosses an edge from A to A' during [t, t+1] Peter
    // can dart in from A' straight back toward A, head-on against it. To stay
    // on the edge his velocity must lie along it, so his speed sp there is 2 if
    // the flow at A' points from A' to A, 1 if A' is still water, and otherwise
    // this case does not apply. Leaving A' at his earliest time dist[A'] and
    // meeting the boat after he has covered sp*(t_m - dist[A']) while the boat
    // has covered (t_m - t) of the unit edge gives sp*(t_m - dist[A']) = 1 -
    // (t_m - t), i.e. t_m = (1 + t + sp*dist[A']) / (sp + 1). This only counts
    // when the contact point really falls inside the edge, which works out to t
    // lying in [dist[A'] - 1, dist[A'] + 1/sp]; for a cycle edge the smallest
    // qualifying t = base + k*period is used (this is the case the 2/3 sample
    // needs).
    //
    // Third, Peter can chase the boat from A in its own direction at speed 2
    // (only when the flow at A matches the boat's heading). Closing the unit
    // gap at relative speed 2 - 1 gives t_m = 2*dist[A] - t, valid when dist[A]
    // lies in [t, t + 0.5] (earlier arrival is just the centre-wait case at A).
    // If no candidate is ever finite Peter cannot be saved and the answer is
    // SOS.

    const double INF = 1e18;

    auto inside = [&](int r, int c) {
        return r >= 0 && r < n && c >= 0 && c < m;
    };

    auto flow_of = [&](int r, int c) {
        int d = grid[r][c] - '0';
        return make_pair(FX[d], FY[d]);
    };

    vector<int> dist_half(n * m, INT_MAX);
    int pr = peter_y - 1, pc = peter_x - 1;
    int br = boat_y - 1, bc = boat_x - 1;

    array<vector<int>, 3> bucket;
    dist_half[pr * m + pc] = 0;
    bucket[0].push_back(pr * m + pc);

    int max_dist = 0;
    for(int d = 0; d <= max_dist; d++) {
        auto& b = bucket[d % 3];
        while(!b.empty()) {
            int id = b.back();
            b.pop_back();
            if(dist_half[id] != d) {
                continue;
            }

            int r = id / m, c = id % m;
            auto [fx, fy] = flow_of(r, c);
            for(int k = 0; k < 5; k++) {
                int vx = fx + FX[k], vy = fy + FY[k];
                if(vx == 0 && vy == 0) {
                    continue;
                }

                int ox = (vx > 0) - (vx < 0), oy = (vy > 0) - (vy < 0);
                int nr = r + oy, nc = c + ox;
                if(!inside(nr, nc)) {
                    continue;
                }

                int w = (abs(vx) == 2 || abs(vy) == 2) ? 1 : 2;
                int nd = d + w;
                if(nd < dist_half[nr * m + nc]) {
                    dist_half[nr * m + nc] = nd;
                    bucket[nd % 3].push_back(nr * m + nc);
                    max_dist = max(max_dist, nd);
                }
            }
        }
    }

    vector<double> dist(n * m, INF);
    for(int i = 0; i < n * m; i++) {
        if(dist_half[i] != INT_MAX) {
            dist[i] = dist_half[i] * 0.5;
        }
    }

    double ans = INF;

    for(int r = 0; r < n; r++) {
        for(int c = 0; c < m; c++) {
            if(dist[r * m + c] >= INF) {
                continue;
            }

            auto [fx, fy] = flow_of(r, c);
            double best_exit = INF;
            for(int k = 0; k < 5; k++) {
                int vx = fx + FX[k], vy = fy + FY[k];
                if(vx == 0 && vy == 0) {
                    continue;
                }

                double tx = INF, ty = INF;
                if(vx > 0) {
                    tx = ((m - 1) + 0.5 - c) / vx;
                } else if(vx < 0) {
                    tx = (c + 0.5) / (-vx);
                }
                if(vy > 0) {
                    ty = ((n - 1) + 0.5 - r) / vy;
                } else if(vy < 0) {
                    ty = (r + 0.5) / (-vy);
                }

                double t_wall = min(tx, ty);
                int ox = (vx > 0) - (vx < 0), oy = (vy > 0) - (vy < 0);
                double t_center =
                    inside(r + oy, c + ox)
                        ? ((abs(vx) == 2 || abs(vy) == 2) ? 0.5 : 1.0)
                        : INF;
                if(t_wall <= t_center + 1e-12) {
                    best_exit = min(best_exit, t_wall);
                }
            }

            if(best_exit < INF) {
                ans = min(ans, dist[r * m + c] + best_exit);
            }
        }
    }

    vector<int> bcell;
    vector<int64_t> btime;
    vector<int> seen_idx(n * m, -1);
    int cr = br, cc = bc;
    int64_t bt = 0;
    int cycle_start = -1;
    int64_t period = 0;
    bool stationary = false;

    while(true) {
        int id = cr * m + cc;
        if(seen_idx[id] != -1) {
            cycle_start = seen_idx[id];
            period = bt - btime[cycle_start];
            break;
        }

        seen_idx[id] = (int)bcell.size();
        bcell.push_back(id);
        btime.push_back(bt);

        auto [fx, fy] = flow_of(cr, cc);
        if(fx == 0 && fy == 0) {
            stationary = true;
            break;
        }

        int nr = cr + fy, nc = cc + fx;
        if(!inside(nr, nc)) {
            break;
        }

        cr = nr;
        cc = nc;
        bt++;
    }

    int len = (int)bcell.size();
    auto is_cyclic = [&](int i) {
        return cycle_start != -1 && i >= cycle_start;
    };

    for(int i = 0; i < len; i++) {
        int id = bcell[i];
        if(dist[id] >= INF) {
            continue;
        }

        double base = (double)btime[i];
        if(stationary && i == len - 1) {
            ans = min(ans, max(dist[id], base));
        } else if(is_cyclic(i)) {
            double cand = base;
            if(dist[id] > base) {
                int64_t k =
                    (int64_t)ceil((dist[id] - base) / (double)period - 1e-9);
                cand = base + (double)max(0LL, k) * period;
            }
            ans = min(ans, cand);
        } else {
            if(dist[id] <= base + 1e-9) {
                ans = min(ans, base);
            }
        }
    }

    auto edge_meet = [&](int a_id, int db_idx, int64_t tb, bool cyc) {
        int ar = a_id / m, ac = a_id % m;
        int dx = FX[db_idx], dy = FY[db_idx];
        int a2r = ar + dy, a2c = ac + dx;
        if(!inside(a2r, a2c)) {
            return;
        }
        int a2 = a2r * m + a2c;

        if(dist[a2] < INF) {
            auto [f2x, f2y] = flow_of(a2r, a2c);
            int sp = 0;
            if(f2x == -dx && f2y == -dy) {
                sp = 2;
            } else if(f2x == 0 && f2y == 0) {
                sp = 1;
            }

            if(sp > 0) {
                double da = dist[a2];
                double lo = da - 1.0, hi = da + 1.0 / sp;
                double t = (double)tb;
                if(cyc && t < lo) {
                    int64_t k = (int64_t)ceil((lo - t) / (double)period - 1e-9);
                    t += (double)max(0LL, k) * period;
                }
                if(t >= lo - 1e-9 && t <= hi + 1e-9) {
                    ans = min(ans, (1.0 + t + sp * da) / (sp + 1));
                }
            }
        }

        if(dist[a_id] < INF) {
            auto [fax, fay] = flow_of(ar, ac);
            if(fax == dx && fay == dy) {
                double da = dist[a_id];
                double lo = da - 0.5, hi = da;
                double t = (double)tb;
                if(cyc && t < lo) {
                    int64_t k = (int64_t)ceil((lo - t) / (double)period - 1e-9);
                    t += (double)max(0LL, k) * period;
                }
                if(t >= lo - 1e-9 && t <= hi + 1e-9) {
                    ans = min(ans, 2.0 * da - t);
                }
            }
        }
    };

    for(int i = 0; i + 1 < len; i++) {
        int cellr = bcell[i] / m, cellc = bcell[i] % m;
        int d = grid[cellr][cellc] - '0';
        edge_meet(bcell[i], d, btime[i], is_cyclic(i));
    }

    if(cycle_start != -1) {
        int last = len - 1;
        int cellr = bcell[last] / m, cellc = bcell[last] % m;
        int d = grid[cellr][cellc] - '0';
        edge_meet(bcell[last], d, btime[last], true);
    }

    if(ans >= INF) {
        cout << "SOS\n";
        return;
    }

    cout << fixed << setprecision(2) << ans << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys
import math


# Direction vectors indexed by lake digit.
# x is column direction, y is row direction.
FX = [0, 0, 0, 1, -1]
FY = [0, -1, 1, 0, 0]


def solve():
    data = sys.stdin.read().strip().split()

    if not data:
        return

    ptr = 0

    n = int(data[ptr])
    ptr += 1

    m = int(data[ptr])
    ptr += 1

    grid = data[ptr:ptr + n]
    ptr += n

    peter_x = int(data[ptr])
    ptr += 1
    peter_y = int(data[ptr])
    ptr += 1

    boat_x = int(data[ptr])
    ptr += 1
    boat_y = int(data[ptr])
    ptr += 1

    # Convert from 1-based (x, y) to 0-based (row, col).
    pr = peter_y - 1
    pc = peter_x - 1
    br = boat_y - 1
    bc = boat_x - 1

    total = n * m

    INF = 10**100
    BIG = 10**18
    EPS = 1e-9

    def inside(r, c):
        return 0 <= r < n and 0 <= c < m

    def flow_of(r, c):
        d = ord(grid[r][c]) - ord('0')
        return FX[d], FY[d]

    # ------------------------------------------------------------
    # 1. Shortest Peter times to all centers.
    # Distances are stored in half-minutes.
    # ------------------------------------------------------------

    dist_half = [BIG] * total

    start = pr * m + pc
    dist_half[start] = 0

    # Dial buckets for weights 1 and 2.
    buckets = [[], [], []]
    buckets[0].append(start)

    max_dist = 0
    d = 0

    while d <= max_dist:
        bucket = buckets[d % 3]

        while bucket:
            cell_id = bucket.pop()

            # Stale entry.
            if dist_half[cell_id] != d:
                continue

            r = cell_id // m
            c = cell_id % m

            fx, fy = flow_of(r, c)

            # Try all Peter swimming vectors.
            for k in range(5):
                vx = fx + FX[k]
                vy = fy + FY[k]

                if vx == 0 and vy == 0:
                    continue

                ox = (vx > 0) - (vx < 0)
                oy = (vy > 0) - (vy < 0)

                nr = r + oy
                nc = c + ox

                if not inside(nr, nc):
                    continue

                # Speed 2 means 0.5 minutes.
                weight = 1 if abs(vx) == 2 or abs(vy) == 2 else 2

                nd = d + weight
                nid = nr * m + nc

                if nd < dist_half[nid]:
                    dist_half[nid] = nd
                    buckets[nd % 3].append(nid)

                    if nd > max_dist:
                        max_dist = nd

        d += 1

    # Convert distances to real minutes.
    dist = [INF] * total

    for i in range(total):
        if dist_half[i] != BIG:
            dist[i] = dist_half[i] * 0.5

    ans = INF

    # ------------------------------------------------------------
    # 2. Direct escape to shore.
    # ------------------------------------------------------------

    for r in range(n):
        for c in range(m):
            cell_id = r * m + c

            if dist[cell_id] >= INF:
                continue

            fx, fy = flow_of(r, c)

            for k in range(5):
                vx = fx + FX[k]
                vy = fy + FY[k]

                if vx == 0 and vy == 0:
                    continue

                tx = INF
                ty = INF

                # Time to a vertical shore.
                if vx > 0:
                    tx = ((m - 1) + 0.5 - c) / vx
                elif vx < 0:
                    tx = (c + 0.5) / (-vx)

                # Time to a horizontal shore.
                if vy > 0:
                    ty = ((n - 1) + 0.5 - r) / vy
                elif vy < 0:
                    ty = (r + 0.5) / (-vy)

                t_wall = min(tx, ty)

                ox = (vx > 0) - (vx < 0)
                oy = (vy > 0) - (vy < 0)

                nr = r + oy
                nc = c + ox

                if inside(nr, nc):
                    t_center = 0.5 if abs(vx) == 2 or abs(vy) == 2 else 1.0
                else:
                    t_center = INF

                # Peter reaches shore before needing to choose again.
                if t_wall <= t_center + EPS:
                    ans = min(ans, dist[cell_id] + t_wall)

    # ------------------------------------------------------------
    # 3. Simulate boat path.
    # ------------------------------------------------------------

    bcell = []
    btime = []
    seen = [-1] * total

    cr = br
    cc = bc
    bt = 0

    cycle_start = -1
    period = 0
    stationary = False

    while True:
        cell_id = cr * m + cc

        # Repeated cell means cycle.
        if seen[cell_id] != -1:
            cycle_start = seen[cell_id]
            period = bt - btime[cycle_start]
            break

        seen[cell_id] = len(bcell)
        bcell.append(cell_id)
        btime.append(bt)

        fx, fy = flow_of(cr, cc)

        # Zero flow: boat stays forever.
        if fx == 0 and fy == 0:
            stationary = True
            break

        nr = cr + fy
        nc = cc + fx

        # Boat reaches shore.
        if not inside(nr, nc):
            break

        cr = nr
        cc = nc
        bt += 1

    length = len(bcell)

    def is_cyclic(i):
        return cycle_start != -1 and i >= cycle_start

    # ------------------------------------------------------------
    # 4. Meet boat at cell centers.
    # ------------------------------------------------------------

    for i in range(length):
        cell_id = bcell[i]

        if dist[cell_id] >= INF:
            continue

        base = float(btime[i])

        if stationary and i == length - 1:
            # Boat remains at this cell forever.
            ans = min(ans, max(dist[cell_id], base))

        elif is_cyclic(i):
            # Visits happen at base + k * period.
            cand = base

            if dist[cell_id] > base:
                k = math.ceil((dist[cell_id] - base) / period - EPS)
                k = max(0, k)
                cand = base + k * period

            ans = min(ans, cand)

        else:
            # Prefix cell is visited once.
            if dist[cell_id] <= base + EPS:
                ans = min(ans, base)

    # ------------------------------------------------------------
    # 5. Meet boat inside an edge.
    # ------------------------------------------------------------

    def try_edge_meet(a_id, dir_digit, tb, cyclic_edge):
        nonlocal ans

        ar = a_id // m
        ac = a_id % m

        dx = FX[dir_digit]
        dy = FY[dir_digit]

        a2r = ar + dy
        a2c = ac + dx

        # If boat moves out of lake, shore escape already covers saving.
        if not inside(a2r, a2c):
            return

        a2_id = a2r * m + a2c

        # -----------------------------
        # Case 1: Peter comes head-on from A'.
        # -----------------------------
        if dist[a2_id] < INF:
            f2x, f2y = flow_of(a2r, a2c)

            sp = 0

            if f2x == -dx and f2y == -dy:
                sp = 2
            elif f2x == 0 and f2y == 0:
                sp = 1

            if sp > 0:
                d = dist[a2_id]

                lo = d - 1.0
                hi = d + 1.0 / sp

                t = float(tb)

                # For cycle edge, shift to first possible repetition.
                if cyclic_edge and t < lo:
                    k = math.ceil((lo - t) / period - EPS)
                    k = max(0, k)
                    t += k * period

                if t >= lo - EPS and t <= hi + EPS:
                    meet = (1.0 + t + sp * d) / (sp + 1)
                    ans = min(ans, meet)

        # -----------------------------
        # Case 2: Peter chases from A.
        # -----------------------------
        if dist[a_id] < INF:
            fax, fay = flow_of(ar, ac)

            # Need speed 2 in the same direction as the boat.
            if fax == dx and fay == dy:
                d = dist[a_id]

                lo = d - 0.5
                hi = d

                t = float(tb)

                if cyclic_edge and t < lo:
                    k = math.ceil((lo - t) / period - EPS)
                    k = max(0, k)
                    t += k * period

                if t >= lo - EPS and t <= hi + EPS:
                    meet = 2.0 * d - t
                    ans = min(ans, meet)

    # Process consecutive boat edges.
    for i in range(length - 1):
        cell_id = bcell[i]
        r = cell_id // m
        c = cell_id % m

        dir_digit = ord(grid[r][c]) - ord('0')

        try_edge_meet(cell_id, dir_digit, btime[i], is_cyclic(i))

    # If boat path has a cycle, also process the edge from the last
    # recorded cycle cell back to the cycle entry.
    if cycle_start != -1:
        cell_id = bcell[-1]
        r = cell_id // m
        c = cell_id % m

        dir_digit = ord(grid[r][c]) - ord('0')

        try_edge_meet(cell_id, dir_digit, btime[-1], True)

    # ------------------------------------------------------------
    # Output.
    # ------------------------------------------------------------

    if ans >= INF:
        print("SOS")
    else:
        print(f"{ans:.2f}")


if __name__ == "__main__":
    solve()
```
