今晚是报复性水博客之夜 QwQ

1. 题目

传送门=￣ω￣=

2. 题解

首先你要知道一个 XZY 不知道的判断一个点是否在一个多边形内的方法：

以这个点为起点向右（其他方向也行）发射一条射线，如果该射线与多边形交点个数为奇数个，则该点在多边形内。

至于多边形与射线重合的部分，我们认为多边形的每条线段在与射线方向垂直的方向上是左闭右开的即可。

（比如如果射线是向右的，那么相同的格子内多边形的位置是高于射线的位置的）

然后枚举一个起点。

设状态 $f[i][j][k]$表示以你当前设定的起点，你当前在 $(i, j)$处、每个豆豆的射线被穿过次数的奇偶性集合为二进制数 $k$时你走过的最短路程。

状态转移就枚举下一步走到哪里，然后看有没有穿过某一个射线（暴力判就行了），更新状态即可。

注意最后要回到起点

然后可以预处理一下每一种二进制集合下被围到的豆豆的价值总和。

（另外不知道为什么网上都说是什么 Spfa？？？每个状态都只会被更新一次啊，为什么都是 Spfa？虽说边长为 1 的图上 Spfa 与 Bfs 是等价的，但是不免让人觉得有点奇♂妙。。。）

代码：

#include <bits/stdc++.h>

#define DS (9)
#define NS (12)
#define lowbit(a) (a & -a)

using namespace std;

const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct TII
{
    int x, y, z;
    TII(int a, int b, int c) {x = a, y = b, z = c;}
};

int n, m, D, v[DS], lg[1 << DS], sum[1 << DS], X[DS], Y[DS];

int dis[NS][NS][1 << DS], ans;

char mp[NS][NS];

queue<TII> que;

void Bfs(int a, int b)
{
    memset(dis, 0, sizeof(dis));
    que.push(TII(a, b, 0)), dis[a][b][0] = 1;
    TII F(0, 0, 0), P(0, 0, 0);
    while (!que.empty())
    {
        F = que.front(); que.pop();
        for (int i = 0; i < 4; i += 1)
        {
            P.x = F.x + dx[i], P.y = F.y + dy[i], P.z = F.z;
            if (P.x < 1 || P.y < 1 || P.x > n || P.y > m) continue;
            if (mp[P.x][P.y] != '0') continue;
            for (int j = 0; j < D; j += 1)
                if (P.y > Y[j])
                {
                    if (i == 0 && F.x == X[j]) P.z ^= (1 << j);
                    if (i == 1 && P.x == X[j]) P.z ^= (1 << j);
                }
            if (dis[P.x][P.y][P.z]) continue;
            dis[P.x][P.y][P.z] = dis[F.x][F.y][F.z] + 1, que.push(P);
        }
    }
    for (int i = 1; i < (1 << D); i += 1)
        if (dis[a][b][i])
            ans = max(ans, sum[i] - dis[a][b][i] + 1);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(D);
    for (int i = 0; i < D; i += 1) IN(v[i]), lg[1 << i] = i;
    for (int i = 1; i < (1 << D); i += 1)
        sum[i] = sum[i - lowbit(i)] + v[lg[lowbit(i)]];
    for (int i = 1; i <= n; i += 1)
    {
        scanf("%s", mp[i] + 1);
        for (int j = 1; j <= m; j += 1)
            if (isdigit(mp[i][j]) && mp[i][j] > '0')
                X[mp[i][j] - '1'] = i, Y[mp[i][j] - '1'] = j;
    }
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j <= m; j += 1)
            if (mp[i][j] == '0')
                Bfs(i, j);
    printf("%d\n", ans);
    return 0;
}