USACO 2.4 Overfencing

The basic idea is for each starting position, find the shortest path from the starting position to one of the exists. Then, among all these shortest paths, find the longest one.
The shortest path problem typically can be solved using either BFS, or, by superimposing the grid into some sort of graph and then applying graph shortest path algorithms (Dijkstra or
Floyd-Warshall). Here I am using simple BFS which is easier to implement with hands tied.

Two catches for this problem:

• Be careful with parse of input. For example ifstream in C++ by default will skip white space charaters, this is obviously what we don’t want here because white space char is legitimate input char. Hopefully the behavior is tunable through std::noskipws.
• The number of steps need to be encoded in each state.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <queue>

using namespace std;

int W, H;
vector<vector<char>> grid;

typedef struct state {
    int x; int y; int s;
    state(int x, int y, int s) : x(x), y(y), s(s) {}
} tState;

bool ongrid(int x, int y) {
    if (x < 0 || x >= 2 * H + 1 || y < 0 || y >= 2 * W + 1) {
        return false;
    }
    return true;
}
// All possible start positions.
vector<tState> pos;
ifstream fin("maze1.in");
ofstream fout("maze1.out");

void parseGrid() {
    fin >> W >> H;
    
    grid = vector<vector<char>>(2 * H + 1, vector<char>(2 * W + 1));

    for (int i = 0; i < 2 * H + 1; ++i) {
        for (int j = 0; j < 2 * W + 1; ++j) {
            char c;
            fin >> std::noskipws >> c;
            if (c == '\n') {
                fin >> std::noskipws >> c;
            }
            grid[i][j] = c;
            cout << c;
            if (c == ' ' && i % 2 && j % 2) {
                pos.emplace_back(tState(i, j, 0));
            }
        }
        cout << endl;
    }
}

int main() {
    parseGrid();
    int res = -1;
    vector<vector<bool>> visited(2 * H + 1, vector<bool>(2 * W + 1, false));
    for (auto &position : pos) {
        for (int i = 0; i < 2 * H + 1; ++i) {
            for (int j = 0; j < 2 *W + 1; ++j) {
                visited[i][j] = false;
            }
        }
        
        int step = 0;
        queue<tState> q;
        q.push(position);

        bool find = false;
        while (!q.empty() && !find) {
            auto p = q.front();
            q.pop();
            if (visited[p.x][p.y])
                continue;
            int dx[] = {1, -1, 0, 0};
            int dy[] = {0, 0, 1, -1};
            for (int i = 0; i < 4; ++i) {
                int x = p.x, y = p.y;
                int xx = x + dx[i], yy = y + dy[i];
                if (!ongrid(xx, yy))
                    continue;
                if (grid[xx][yy] == '|' || grid[xx][yy] == '-') continue;
                xx = xx + dx[i]; yy = yy + dy[i];
                tState next(xx, yy, p.s + 1);
                if (!ongrid(xx, yy)) {
                    step = next.s;
                    find = true;
                    break;
                }
                if (!visited[next.x][next.y]) {
                    q.push(next);
                }
                visited[p.x][p.y] = true;
            }
        }
        res = std::max(res, step);
    }
    
    fout << res<< endl;
    cout << res << endl;
}