\(HW\) 個の頂点 \((i,j)\ (1\le i\le H,1\le j\le W)\) について、\((i,j)\) と \((i+1,j)\) 、\((i,j)\) と \((i,j+1)\) の間に辺を張り、容量を

• どちらかのマスに障害物が置かれているなら \(0\)
• そうでなければ \(1\)

としたグラフを考えます。

元の問題の答えが Yes であることは、\((1,1)\) から \((H,W)\) への最大流の流量が \(1\) 以上であることと同値です。

これは、最大流最小カット定理から、重み \(0\) のカットが存在しないことと同値になります。

上のグラフは平面グラフなので、適切に平面へ埋め込んだのち双対グラフをとることで（頂点 \((i,j)\) を座標 \((i,j)\) に配置すればよいです）、双対グラフの最短経路問題に帰着することができます。

特に、最短経路の重みが \(0\) であるかが判定できればよく、辺の重みは非負なので、これは重みが \(0\) の辺のみで連結であるかが判定できればよいです。

これは、（孤立点を適切に削除した上で、）幅優先探索や深さ優先探索、Union Find などを用いることで解くことができます。

実装例は以下のようになります。 以下の実装例では Union Find を利用しています。

#include <iostream>
#include <unordered_map>

int main() {
    using namespace std;
    unsigned H, W, K;
    cin >> H >> W >> K;

    // union-find を hash map で実装
    unordered_map<unsigned long, unsigned long> parent;
    unordered_map<unsigned long, unsigned> size;

    const auto find{[&parent, &size](unsigned long i) {
        if (!parent.contains(i)) {
            parent[i] = i;
            size[i] = 1;
        }
        while (i != parent[i])
            i = parent[i] = parent[parent[i]];
        return i;
    }};
    const auto unite{[&parent, &size, &find](unsigned long i, unsigned long j) {
        i = find(i);
        j = find(j);
        if (i == j) return;
        if (size[i] < size[j]) swap(i, j);
        size[i] += size[j];
        parent[j] = i;
    }};

    // 双対グラフの頂点から番号に変換する
    const auto coordinate_to_index{[H, W](unsigned long x, unsigned long y) -> unsigned long {
        if (x == 0 || y == W)
            return 0;
        if (y == 0 || x == H)
            return 1;
        return x * W + y;
    }};

    for (unsigned i{}, x, y; i < K; ++i) {
        cin >> x >> y;
        // 関係する辺の重みを 0 に → 双対グラフにその辺を貼る
        if (x > 1)
            unite(coordinate_to_index(x - 1, y), coordinate_to_index(x - 1, y - 1));
        if (y > 1)
            unite(coordinate_to_index(x, y - 1), coordinate_to_index(x - 1, y - 1));
        if (x < H)
            unite(coordinate_to_index(x, y - 1), coordinate_to_index(x, y));
        if (y < W)
            unite(coordinate_to_index(x - 1, y), coordinate_to_index(x, y));
    }

    // 双対グラフで連結なら、最小カット = 最大フローの重みは 0
    cout << (find(0) == find(1) ? "No" : "Yes") << endl;
    return 0;
}