各マスから \(4\) 方向それぞれに動いた時どのマスで止まるかを計算したいです。これは各行と各列にある柱の位置を管理し、今いる行番号あるいは列番号より大きい番号の位置にある柱を探し、その手前まで行けるというふうにして計算できます。二分探索などを利用して時間計算量 \(\mathrm{O}(N+HW \log HW)\) ですべてのマスについて求められます。(時間計算量 \(\mathrm{O}(N+HW)\) でも計算できます)

マスと進む方角によってどのマスで止まるかが計算できれば、グラフの頂点んと各マスが対応したグラフで出発するマスと停止するマスの間に有向辺を張り、マス \((0,0)\) からマス \((H,W)\) の最短距離を求めればよいです。辺の重みはすべて \(1\) なので、BFSを行うだけでよいです。この部分の時間計算量は \(\mathrm{O}(HW)\) になります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int h, w, n;
    cin >> h >> w >> n;
    vector<vector<int>> row(h), col(w);
    for (int i = 0; i < n; ++i) {
        int r, c;
        cin >> r >> c;
        r--, c--;
        row[r].emplace_back(c);
        col[c].emplace_back(r);
    }
    for (int i = 0; i < h; ++i) sort(row[i].begin(), row[i].end());
    for (int i = 0; i < w; ++i) sort(col[i].begin(), col[i].end());
    vector<vector<int>> g(h * w);
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j) {
            // 右
            auto it = upper_bound(row[i].begin(), row[i].end(), j);
            int nj = -1;
            if (it == row[i].end())
                nj = w - 1;
            else
                nj = *it - 1;
            g[i * w + j].emplace_back(i * w + nj);

            // 左
            auto it = lower_bound(row[i].begin(), row[i].end(), j);
            int nj = -1;
            if (it == row[i].begin())
                nj = 0;
            else
                nj = *prev(it) + 1;
            g[i * w + j].emplace_back(i * w + nj);

            // 下
            auto it = upper_bound(col[j].begin(), col[j].end(), i);
            int ni = -1;
            if (it == col[j].end())
                ni = h - 1;
            else
                ni = *it - 1;
            g[i * w + j].emplace_back(ni * w + j);

            // 上
            auto it = lower_bound(col[j].begin(), col[j].end(), i);
            int ni = -1;
            if (it == col[j].begin())
                ni = 0;
            else
                ni = *prev(it) + 1;
            g[i * w + j].emplace_back(ni * w + j);
        }

    vector<int> dist(h * w, (int)1e9);
    dist[0] = 0;
    queue<int> que;
    que.emplace(0);
    while (!que.empty()) {
        auto v = que.front();
        que.pop();
        for (auto to : g[v]) {
            if (dist[to] > dist[v] + 1) {
                dist[to] = dist[v] + 1;
                que.emplace(to);
            }
        }
    }
    if (dist[h * w - 1] == (int)1e9)
        cout << -1 << endl;
    else
        cout << dist[h * w - 1] << endl;
}