USACO 2.4 Cow Tours

This problem asks about the longest paths among the shortest paths. The basic idea is to use a brutal force search against all pair shortest paths. There are two cases for the shortest paths:

The shortest path is one of those that’s connecting two pastures that’s already connected. These paths are already available in original graph.
The shortest path does not exist in original graph. Between two disconnected pastures, say pasture A and pasture B, we can have them connected by having a path go between A and B. Now before we connect A and B, there must exist pasture C and D, such that distance AC is the maximized possible distance between A and all other pastures A already connected in original graph, and similarly distance BD is maximized possible distance between B and all other pastures B already connected in original graph. The new possible longest path of all shortest path between pairs is now distance(AC) + distance(BD) + distance (AB).
Combining two cases, we can do a brutal force search and find the maximum path.
For all pastures that have already connected, use Floyd all pair shortest paths to calculate the path values.
There is no need to explicitly calculate the strongly connected component that connected pastures form, because we would iterate through pair of pastures, rather than through pair of strongly connected components formed by pastures. And we can tell if two pastures needs to be checked because we will only check those that have initial distance value of infinite (meaning not connected initially.).

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <limits>
#include <iomanip>

using namespace std;
#define DOUBLE_MAX std::numeric_limits<double>::max()

int N;

typedef struct Point {
  int x; int y;
} tPoint;

vector<tPoint> points;
vector<vector<double>> dist;
vector<double> dmax;

double distance(int x1, int y1, int x2, int y2) {
  return sqrt((double)pow(x1 - x2, 2) + (double)pow(y1 - y2, 2));
}

int main() {
  ifstream fin("cowtour.in");
  ofstream fout("cowtour.out");

  fin >> N;
  points = vector<tPoint>(N, tPoint());
  dist = vector<vector<double>>(N, vector<double>(N, 0));
  dmax = vector<double>(N, 0);

  for (int i = 0; i < N; ++i) {
    fin >> points[i].x;
    fin >> points[i].y;
  }

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      char c;
      fin >> c;
      if (c == '0') {
        dist[i][j] = DOUBLE_MAX;
      } else {
        dist[i][j] = distance(points[i].x, points[i].y, points[j].x, points[j].y);
      }
    }
  }

  // Flyod all pair shortest path.
  for (int k = 0; k < N; ++k) {
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        if ((dist[i][k] + dist[k][j] < dist[i][j]) &&
             dist[i][k] != DOUBLE_MAX &&
             dist[k][j] != DOUBLE_MAX) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  for(int i = 0; i < N; ++i){
    dist[i][i] = DOUBLE_MAX;
  }

  double max_distance = 0;
  for(int i = 0; i < N; ++i){
    double cmax = 0;
    for(int j = 0; j < N; ++j){
      if (dist[i][j] == DOUBLE_MAX)
        continue;
      cmax = std::max(cmax, dist[i][j]);
    }
    dmax[i] = cmax;
    max_distance = std::max(max_distance, cmax);
  }


  double ret = DOUBLE_MAX;
  for(int i = 0; i < N - 1; ++i){
    for(int j = i + 1; j < N; ++j){
      if (i != j && dist[i][j] == DOUBLE_MAX) {
        double d = distance(points[i].x, points[i].y,
                            points[j].x, points[j].y);
        ret = std::min(ret, d + dmax[i] + dmax[j]);
      }
    }
  }

  fout << setiosflags(ios::fixed) << setprecision(6)
    << (max_distance > ret ? max_distance : ret) << endl;

  cout << setiosflags(ios::fixed) << setprecision(6)
  << (max_distance > ret ? max_distance : ret) << endl;
  return 0;
}

2016-10-07

USACO

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;
}

2016-10-06

USACO

USACO 2.4 The Tamworth Two

The problem can be solved using simple search. The only catch seems that we need properly encode the global state such that we don’t end up visit two exact same state twice, so we can bail out in cases where farmer and cows would never meet.
The visited state can be encoded using a six dimensional array, with dimensions as farmers locations (x, y), direction, and cows locations (x, y) and direction.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <unordered_map>
#include <set>
#include <stack>

using namespace std;

bool visited[10][10][4][10][10][4] = {false};
vector<vector<char>> grid(10, vector<char>(10, ' '));
// Encoding of directions: 0, 1, 2, 3 for north, east, south, west.
int fd = 0, cd = 0;
typedef struct state {
    int x; int y; int d;
    state() : x(0), y(0), d(0) {}
} tState;
tState fs, cs;

void move(tState &s) {
    if (s.d == 0) {
        --s.y;
        if (s.y < 0 || grid[s.y][s.x] == '*') {
            ++s.y;
            s.d = 1;
        }
    } else if (s.d == 1) {
        ++s.x;
        if (s.x > 9 || grid[s.y][s.x] == '*') {
            --s.x;
            s.d = 2;
        }
    } else if (s.d == 2) {
        ++s.y;
        if (s.y > 9 || grid[s.y][s.x] == '*') {
            --s.y;
            s.d = 3;
        }
    } else if (s.d == 3) {
        --s.x;
        if (s.x < 0 || grid[s.y][s.x] == '*') {
            ++s.x;
            s.d = 0;
        }
    } else {
        cout << "Invalid State!!" << endl;
    }
}

int main() {
    ifstream fin("ttwo.in");
    ofstream fout("ttwo.out");
    
    char c;
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            fin >> c;
            grid[i][j] = c;
            if (c == 'F') {
                fs.x = j; fs.y = i;
            }
            if (c == 'C') {
                cs.x = j; cs.y = i;
            }
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
    
    visited[fs.x][fs.y][fs.d][cs.x][cs.y][cs.d] = true;
    int res = 0;
    while (true) {
        ++res;
        move(fs);
        move(cs);
        if (visited[fs.x][fs.y][fs.d][cs.x][cs.y][cs.d]) {
            res = 0; break;
        }
        
        if (fs.x == cs.x && fs.y == cs.y) {
            break;
        }
        
        visited[fs.x][fs.y][fs.d][cs.x][cs.y][cs.d] = true;
    }
    
    fout << res << endl;
    cout << res << endl;
}