围豆豆
题面
游戏的规则非常简单，在一个 \(N\times M\) 的矩阵方格内分布着 \(D\) 颗豆子，每颗豆有不同的分值 \(V_i\)。
游戏者可以选择任意一个方格作为起始格，每次移动可以随意的走到相邻的四个格子，直到最终又回到起始格。
最终游戏者的得分为所有被路径围住的豆豆的分值总和减去游戏者移动的步数。矩阵中某些格子内设有障碍物，任何时刻游戏者不能进入包含障碍物或豆子的格子。游戏者可能的最低得分为 \(0\)，即什么都不做。
求能获得的最大分值
注意路径包围的概念，即某一颗豆在路径所形成的多边形（可能是含自交的复杂多边形）的内部。下面有两个例子：
第一个例子中，豆在路径围成的矩形内部，所以豆被围住了。第二个例子中，虽然路径经过了豆的周围的 \(8\) 个格子，但是路径形成的多边形内部并不包含豆，所以没有围住豆子。
满足 \(1\le D\le 9\)，\(1\le N,M\le 10\)，\(-10^4\le V_i\le 10^4\)。
题解
考虑要求解这个问题，我们需要知道那些信息？
要选哪些豆？起点在哪里？路径长度？怎么判断一个豆子是否被选上？
那么我们可以设 \(f(x,y,s)\) 表示从某个起点出发走到 \((x,y)\) ，选豆豆集合为 \(s\) 的最短路径长度
假如我们已经能算 \(f\) ，那么答案就是先枚举一个起点，然后算一下 \(f\) ，统计答案即可
问题是如何求 \(f\) ？
我们可以用 \(spfa\) 用类似求最短路的方式去求，但是要考虑一个子问题是如何转移 \(s\) ？
也就是一个豆子怎么才算被选上，我们要用一个“射线定理”，从一个豆子朝某个方向作一条射线，看与轮廓有多少交点，如果有奇数个那么被包含，否则不被包含。
我们钦定向右边作射线，每次向上或向下时改变一下 \(s\) 即可实现转移，但是发现出现了问题
比如下面这种情况：
如果我们只判断下一步的格子是否改变豆豆的包围情况，那么上面的豆子就是被包围的，单实际上它没有被包围，所以我们需要换一种能避免这种情况的方式更新
如果我们将图中两种箭头经过红线的位置作为关键点，那么是不是就能避免这种情况，并且不会影响正常的更新
时间复杂度 \(O(n^2m^22^d)\) ，瓶颈在bfs时每个点最劣都要被经过 \(O(2^d)\) 次
code
#include
#include
#include
#include
#include
using namespace std;
const int N = 11, M = (1 << N - 1) - 7;
int n, m, D, ans = 0;
int a[N], f[N][N][M];
char str[N][N];
pair
struct node { int x, y, s; };
int calc (int s, int x, int y, int tx, int ty) {
for (int i = 1; i <= D; i ++) {
if (((x == p[i].first && tx < p[i].first) || (x < p[i].first && tx == p[i].first)) && p[i].second < y) {
s ^= (1 << i - 1);
}
}
return s;
}
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1 ,0, 0};
void bfs (int sx, int sy) {
memset (f, 0x3f, sizeof f);
queue
q.push ({sx, sy});
f[sx][sy][0] = 0;
while (q.size ()) {
auto tmp = q.front ();
q.pop ();
int x = tmp.x, y = tmp.y, s = tmp.s;
for (int i = 0; i < 4; i ++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx < 1 || tx > n || ty < 1 || ty > m || str[tx][ty] != '0') continue;
int ss = s;
if (i > 1) ss = calc (ss, x, y, tx, ty);
if (f[tx][ty][ss] > f[x][y][s] + 1) {
f[tx][ty][ss] = f[x][y][s] + 1;
q.push ({tx, ty, ss});
}
}
}
for (int i = 0; i < (1 << D); i ++) {
int val = 0;
for (int j = 1; j <= D; j ++) {
if ((i >> j - 1) & 1) {
val += a[j];
}
}
ans = max (ans, val - f[sx][sy][i]);
}
}
int main () {
cin >> n >> m >> D;
for (int i = 1; i <= D; i ++) {
cin >> a[i];
}
for (int i = 1; i <= n; i ++) {
scanf ("%s", str[i] + 1);
for (int j = 1; j <= m; j ++) {
if (str[i][j] > '0' && str[i][j] <= '9') {
int id = str[i][j] - '0';
p[id] = {i, j};
}
}
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (str[i][j] == '0') {
bfs (i, j);
}
}
}
cout << ans << endl;
return 0;
}