UVa 10937 - Blackbeard the Pirate

Accepted date: 2016-08-12
Run Time: 0.000
Ranking (as of 2016-08-12): 19 out of 385
Language: C++

/*
  UVa 10937 - Blackbeard the Pirate

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10937_Blackbeard_the_Pirate.cpp

  This problem is similar to 10944 - Nuts for nuts..
*/

#include <algorithm>
#include <queue>
#include <utility>
#include <limits>
#include <cstdio>
#include <cstring>
using namespace std;

const int infinite = numeric_limits<int>::max();
const int h_max = 50, w_max = 50, nr_treasures_max = 10;
char map[h_max][w_max + 1];
struct place {
  int r_, c_;
  place() {}
  place(int r, int c) : r_(r), c_(c) {}
  place(const place& p) : r_(p.r_), c_(p.c_) {}
} places[nr_treasures_max + 1];

bool visited[h_max][w_max];
int distances[nr_treasures_max + 1][nr_treasures_max + 1];
  // distances[i][j] is the distance between the treasures of i and j
int bitmasks[1 << (nr_treasures_max + 1)][nr_treasures_max + 1];

const int nr_cardinal_dirs = 4;
const pair<int, int> cardinal_dirs[nr_cardinal_dirs] =
  {make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)};
const int nr_diagonal_dirs = 4;
const pair<int, int> diagonal_dirs[nr_diagonal_dirs] =
  {make_pair(1, 1), make_pair(-1, 1), make_pair(-1, -1), make_pair(1, -1)};

int tsp(int nr_treasures, int places, int p) // travelling salesman problem
{
  if (places == (1 << p))
    return distances[p][0]; // distance from the landing point to the treasure of p
  int& d = bitmasks[places][p];
  if (d >= 0)
    return d;
  d = infinite;
  for (int i = 0; i < nr_treasures; i++)
    if (i != p && (places & (1 << i)))
      d = min(d, distances[p][i] + tsp(nr_treasures, places & ~(1 << p), i));
  return d;
}

int bfs(int h, int w, int s, int nr_treasures)
{
  memset(visited, 0, sizeof(visited));
  for (int i = 0; i < nr_treasures; i++)
    distances[s][i] = infinite;
  queue< pair<place, int> > q;
  visited[places[s].r_][places[s].c_] = true;
  distances[s][s] = 0;
  q.push(make_pair(places[s], 0));
  while (!q.empty()) {
    place p = q.front().first;
    int d = q.front().second;
    q.pop();
    for (int i = 0; i < nr_cardinal_dirs; i++) {
      int nr = p.r_ + cardinal_dirs[i].first, nc = p.c_ + cardinal_dirs[i].second;
      if (nr >= 0 && nr < h && nc >= 0 && nc < w && map[nr][nc] != -1 && !visited[nr][nc]) {
        visited[nr][nc] = true;
        if (map[nr][nc] < nr_treasures)
          distances[s][map[nr][nc]] = distances[map[nr][nc]][s] = d + 1;
        q.push(make_pair(place(nr, nc), d + 1));
      }
    }
  }
  for (int i = 0; i < nr_treasures; i++)
    if (distances[s][i] == infinite)
      return -1;
  return 0;
}

int main()
{
  while (true) {
    int h, w;
    scanf("%d %d", &h, &w);
    if (!h)
      break;
    int nr_treasures = 1;
    for (int r = 0; r < h; r++) {
      scanf("%s", map[r]);
      for(int c = 0; c < w; c++)
        switch (map[r][c]) {
        case '@':
          places[0].r_ = r, places[0].c_ = c;
          map[r][c] = 0;
          break;
        case '!':
          places[nr_treasures].r_ = r, places[nr_treasures].c_ = c;
          map[r][c] = nr_treasures++;
          break;
        case '~': case '#':
          map[r][c] = -1;
            break;
        }
    }
    int result = 0;
    for (int r = 0; r < h; r++)
      for(int c = 0; c < w; c++)
        if (map[r][c] == '*') {
          for (int i = 0; i < nr_cardinal_dirs; i++) {
            int nr = r + cardinal_dirs[i].first, nc = c + cardinal_dirs[i].second;
            if (nr >= 0 && nr < h && nc >= 0 && nc < w && map[nr][nc] != '*') {
              if (map[nr][nc] >= 0 && map[nr][nc] < nr_treasures)
                result = -1; // a treasure is not reachable
              map[nr][nc] = -1;
            }
            if (result == -1)
              break;
          }
          for (int i = 0; i < nr_diagonal_dirs; i++) {
            int nr = r + diagonal_dirs[i].first, nc = c + diagonal_dirs[i].second;
            if (nr >= 0 && nr < h && nc >= 0 && nc < w && map[nr][nc] != '*') {
              if (map[nr][nc] >= 0 && map[nr][nc] < nr_treasures)
                result = -1;
              map[nr][nc] = -1;
            }
            if (result == -1)
              break;
          }
          if (result == -1)
            break;
        }
    if (result != -1) {
      // calculate the distances between the treasures/landing point
      for (int i = 0; i < nr_treasures; i++)
        if ((result = bfs(h, w, i, nr_treasures)) == -1)
          break;
      if (result != -1) {
        memset(bitmasks, -1, sizeof(bitmasks));
        result = tsp(nr_treasures, (1 << nr_treasures) - 1, 0);
      }
    }
    printf("%d\n", result);
  }
  return 0;
}