# 2. 题解

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

（另外不知道为什么网上都说是什么 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;
}