UVa 816 - Abbott's Revenge

Accepted date: 2015-12-05
Ranking (as of 2015-12-05): 39 out of 565
Language: C++

/*
  UVa 816 - Abbott's Revenge

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_816_Abbotts_Revenge.cpp
*/

#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

enum {north, south, east, west};
enum {left, forward_, right};
const int nr_rows = 9, nr_columns = 9,
  nr_nsew = west - north + 1, nr_lfr = right - left + 1,
  nr_name_chars_max = 20, nr_chars_max = 8;

bool exits[nr_rows + 1][nr_columns + 1][nr_nsew][nr_lfr];
  // path[r][c][f][t] is true if the path to (r, c) from f to can be exited
bool visited[nr_rows + 1][nr_columns + 1][nr_nsew][nr_lfr];

int symbol_values[] = {
  0, 0, 0, 0, east, forward_, 0, 0, 0, 0, 0, left, 0, north, 
  0, 0, 0, right, south, 0, 0, 0, west, 0, 0, 0
};

struct path {
  int r_, c_;
  vector<int> froms_; // vector of north, south, east or west

  path() {}
  path(const path& p) : r_(p.r_), c_(p.c_), froms_(p.froms_) {}
  path(int r, int c, const vector<int>& froms, int f)
    : r_(r), c_(c), froms_(froms) {froms_.push_back(f);}
};

const int next_dirs[nr_nsew][nr_lfr] = {
  // dirs[f][t] is the next direction from f to t
  {west, north, east},
  {east, south, west},
  {north, east, south},
  {south, west, north}
};

void next_path(int from, int &r, int& c)
{
  switch (from) {
  case north:
    r--; break;
  case south:
    r++; break;
  case east:
    c++; break;
  case west:
    c--; break;
  }
}

void print_paths(int sr, int sc, const vector<int>& froms)
{
  int r = sr, c = sc;
  size_t i, j;
  for (i = 0, j = froms.size(); i < j; i++) {
    if (!(i % 10))
      printf("  ");
    printf("(%d,%d)%c", r, c, (((i % 10) == 9) ? '\n' : ' '));
    next_path(froms[i], r, c);
  }
  if (!(i % 10))
    printf("  ");
  printf("(%d,%d)\n", r, c);
}

int main()
{
  while (true) {
    char name[nr_name_chars_max + 1];
    scanf("%s", name);
    if (!strcmp(name, "END"))
      break;
    memset(exits, 0, sizeof(exits));
    memset(visited, 0, sizeof(visited));
    int sr, sc, gr, gc, sd;
    char s[nr_chars_max];
    scanf("%d %d %s %d %d", &sr, &sc, s, &gr, &gc);
    sd = symbol_values[s[0] - 'A'];
    while (true) {
      int r, c;
      scanf("%d", &r);
      if (!r)
        break;
      scanf("%d", &c);
      while (true) {
        scanf("%s", s);
        if (s[0] == '*')
          break;
        int f = symbol_values[s[0] - 'A'];
        for (int i = 1; s[i]; i++)
          exits[r][c][f][symbol_values[s[i] - 'A']] = true;
      }
    }
    printf("%s\n", name);
    bool solution = false;
    queue<path> q;
    visited[sr][sc][sd][forward_] = true;
    q.push(path(sr, sc, vector<int>(), sd));
    while (!q.empty()) {
      path u = q.front(); q.pop();
      int from = u.froms_.back(), r = u.r_, c = u.c_;
#ifdef DEBUG
      printf("%d %d %d %d\n", r, c, u.froms_.back(), u.forms_.size());
#endif
      next_path(from, r, c);
      if (r == gr && c == gc) {
        solution = true;
        print_paths(sr, sc, u.froms_);
        break;
      }
      if (r >= 1 && r <= nr_rows && c >= 1 && c <= nr_columns)
        for (int to = left; to <= right; to++)
          if (exits[r][c][from][to] && !visited[r][c][from][to]) {
            visited[r][c][from][to] = true;
            q.push(path(r, c, u.froms_, next_dirs[from][to]));
          }
    }
    if (!solution)
      puts("  No Solution Possible");
  }
  return 0;
}