Consider a graph with \(HW\) vertices \((i,j)\ (1\le i\le H,1\le j\le W)\) and with edges between \((i,j)\) and \((i+1,j)\), and between \((i,j)\) and \((i,j+1)\), whose capacity is defined as:

• \(0\) if either cell contains an obstacle, and
• \(1\) otherwise.

The answer to the original problem is Yes if and only if the maximum flow from \((1,1)\) to \((H,W)\) is \(1\) or greater.

By the max-flow min-cut theorem, this is equivalent to that there is no weight-\(0\) cut.

Since the graph above is a planar graph, one can embed it in the plane and take the dual (specifically, by placing vertex \((i,j)\) to coordinates \((i,j)\)) to reduce the problem to a shortest path problem on the dual graph.

Notably, it is sufficient to determine if the weight of the shortest path is \(0\). Since the edge weights are non-negative, it is enough to check if the graph is connected only by the edges of weight \(0\).

This can be determined by (after removing isolated vertices appropriately) Breadth-First Search, Depth-First Search, or Disjoint Set Union (DSU).

The following is sample code. In the following sample code, we use DSU.

#include <iostream>
#include <unordered_map>

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

    // Implement DSU with 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;
    }};

    // Convert from a vertex in the dual graph to the corresponding index
    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;
        // Make the related edge weights 0 -> add those edges to the dual graph
        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));
    }

    // If the dual graph is connected, then the weight of minimum cut = maximum flow is 0
    cout << (find(0) == find(1) ? "No" : "Yes") << endl;
    return 0;
}