For what kind of \(K\) does the solution exist? Obviously, \(K\geq N\) is required, considering the length of the shortest path between squares \((1,M)\) and \((N,M)\).

Out of the blue, let us draw the grid in a checkered pattern as follows:

Any path on the grid visits red square \(\rightarrow\) blue square \(\rightarrow\) red square \(\rightarrow\dots\), i.e. squares with alternating colors. Moreover, whether the colors of squares \((1,M)\) and \((N,M)\) are the same or different solely depends on the parity of \(N\). Thus, the parity of \(N\) and \(K\) must coincide. (For example, if \(N\) is even, the colors of squares \((1,M)\) and \((N,M)\) are different. That means a path from the start to the goal goes like red \(\rightarrow\) blue \(\righarrow\) red \(\rightarrow\) blue \(\rightarrow\dots\rightarrow\) red \(\rightarrow\) blue, which always comprises an even number of vertices.)

Conversely, if \(K\geq N\) and the parities of \(N\) and \(K\) are the same, then one can always construct a solution. Specifically, starting from the path of the shortest length \(N\), one can incrementally increase the length of the path by \(2\), as \(N,N+2,N+4,\dots\).

If \(N\) is even

If \(N\) is odd

All that left is to carefully implement it. You need a bit of casework, but placing walls within the branch is hard, so we recommend you to do casework and construction separately. In the sample code below, it first does some casework to compute the sequence of squares to pass through, then build walls to every boundary, and finally remove those between the pairs of squares adjacent in the path.

Sample code (C++):

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    if (k < n or k % 2 != n % 2) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    vector<pair<int, int>> path;
    k -= n;
    for (int i = 0; i < n - 1; i += 2) {
        if (i != n - 3) {
            int w = 1 + min(m - 1, k / 2);
            k -= (w - 1) * 2;
            for (int j = 0; j < w; j++) {
                path.emplace_back(i, m - 1 - j);
            }
            for (int j = 0; j < w; j++) {
                path.emplace_back(i + 1, m - w + j);
            }
        } else if (k <= (m - 1) * 2) {
            int w = 1 + k / 2;
            for (int j = 0; j < w; j++) {
                path.emplace_back(i, m - 1 - j);
            }
            for (int j = 0; j < w; j++) {
                path.emplace_back(i + 1, m - w + j);
            }
            path.emplace_back(i + 2, m - 1);
        } else {
            for (int j = 0; j < m; j++) {
                path.emplace_back(i, m - 1 - j);
            }
            k -= (m - 1) * 2;
            int j = 0;
            while (j < m) {
                if (k) {
                    path.emplace_back(i + 1, j);
                    path.emplace_back(i + 2, j);
                    path.emplace_back(i + 2, j + 1);
                    path.emplace_back(i + 1, j + 1);
                    j += 2;
                    k -= 2;
                } else {
                    path.emplace_back(i + 1, j);
                    j++;
                }
            }
            path.emplace_back(i + 2, m - 1);
        }
    }
    vector c(n, string(m - 1, '|'));
    vector r(n - 1, string(m, '-'));
    for (int i = 0; i < path.size() - 1; i++) {
        auto [x1, y1] = path[i];
        auto [x2, y2] = path[i + 1];
        if (x1 == x2) c[x1][min(y1, y2)] = '.';
        else r[min(x1, x2)][y1] = '.';
    }
    cout << string(2 * m - 1, '+') + "S+\n";
    for (int i = 0; i < n; i++) {
        cout << '+';
        for (int j = 0; j < m - 1; j++) cout << 'o' << c[i][j];
        cout << "o+\n";
        if (i < n - 1) {
            for (int j = 0; j < m; j++) cout << '+' << r[i][j];
            cout << "+\n";
        }
    }
    cout << string(2 * m - 1, '+') + "G+\n";
}