Codeforces375C Circling Round Treasures

未分类

首先要知道咋判断一个点是否在一个多边形里面：做一条不穿过任意多边形顶点的射线，如果经过的边数为奇数则在多边形里面，反之在外面。

咋造不穿过方格里任意点的射线呢？选一个趋于负无穷的斜率就行了。那么状压 DP，设 $f(i,j,k)$ 为走到点 $(i,j)$，$k$ 为宝藏的包含状态时的最短路。用 BFS 来转移。

对于炸弹，将它看成一个收益为负无穷的宝藏就行了。注意这个值不能太小，不然会溢出。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
const int MAXN = 200;
const int NXT[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int n, m, sx, sy, tot;
int dp[MAXN | 1][MAXN | 1][1 << 8];
char s[MAXN + 5][MAXN + 5];
struct Dot {
  int x, y, val;
  Dot() : x(0), y(0), val(0) {}
  Dot(int _x, int _y, int _val) : x(_x), y(_y), val(_val) {}
} a[10];
struct Queue {
  int x, y, z;
  Queue() : x(0), y(0), z(0) {}
  Queue(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
};
std::queue < Queue > q;
inline int read() {
  register int x = 0, v = 1;
  register char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') v = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * v;
}
int calc(int _x0, int _y0, int _x1, int _y1, int i) {
  if (_x0 == a[i].x && _y0 > a[i].y) return _x1 < a[i].x;
  if (_x1 == a[i].x && _y1 > a[i].y) return _x0 < a[i].x;
  return 0;
}
int DP() {
  memset(dp, -1, sizeof(dp));
  q.push(Queue(sx, sy, 0));
  dp[sx][sy][0] = 0;
  do {
    Queue from = q.front();
    q.pop();
    for (int k = 0; k < 4; ++k) {
      int tx = from.x + NXT[k][0], ty = from.y + NXT[k][1];
      if (tx < 1 || tx > n || ty < 1 || ty > m || (s[tx][ty] != '.' && s[tx][ty] != 'S')) continue;
      int tmp = from.z;
      for (int i = 1; i <= tot; ++i) {
        tmp ^= (calc(from.x, from.y, tx, ty, i) << (i - 1));
      }
      if (dp[tx][ty][tmp] == -1 || dp[tx][ty][tmp] == 0) {
        dp[tx][ty][tmp] = dp[from.x][from.y][from.z] + 1;
        q.push(Queue(tx, ty, tmp));
      }
    }
  } while (!q.empty());
  int ans = 0;
  for (int i = 1; i < (1 << tot); ++i) {
    int sum = 0;
    if (dp[sx][sy][i] == -1) continue;
    for (int j = 1; j <= tot; ++j) {
      if (((i >> (j - 1)) & 1) == 1) {
        sum += a[j].val;
      }
    }
    if (sum - dp[sx][sy][i] > ans) {
      ans = sum - dp[sx][sy][i];
    }
  }
  return ans;
}
int main() {
  freopen("code.in", "r", stdin);
  freopen("code.out", "w", stdout);
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s[i] + 1);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (s[i][j] == 'S') {
        sx = i;
        sy = j;
      }
      if (isdigit(s[i][j])) {
        a[s[i][j] - '0'] = Dot(i, j, 0);
        ++tot;
      }
    }
  }
  for (int i = 1; i <= tot; ++i) a[i].val = read();
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (s[i][j] == 'B') {
        a[++tot] = Dot(i, j, -2e9 / 400);
      }
    }
  }
  printf("%d\n", DP());
  return 0;
}