题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1294
状压dp，dis[s][i][j]表示从(i,j)出发围的状态是s的最短路。
然后判断一个点是否在区间内用射线法（向右射出一条射线，如果穿过的边界是奇数就算，偶数则不算。
然后枚举起点跑最短路就可以了。
（傻叉错误调半天TAT
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<queue>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
using namespace std;
struct data{int x,y,z;
};
int dx[]={,,,-},dy[]={,,-,};
int mp[][],dis[][][],d[][][],vis[][][],v[],p[][],bin[];
int n,m,D,tot,ans;
int read(){
int x=,f=; char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
while (isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
int get(int s,int x,int y,int xx,int yy){
int ans=s;
rep(i,,D) {
int nowx=p[i][],nowy=p[i][];
if (yy>nowy&&((x<=nowx&&xx>nowx)||(x>nowx&&xx<=nowx))) ans=ans^bin[i-];
}
return ans;
}
void spfa(int x,int y){
queue<data> q;
clr(dis,); clr(vis,); dis[][x][y]=; q.push((data){x,y,});
while (!q.empty()){
data u=q.front(); q.pop(); vis[u.z][u.x][u.y]=;
rep(i,,){
int vx=u.x+dx[i],vy=u.y+dy[i];
if (mp[vx][vy]!=) continue;
int tmp=get(u.z,u.x,u.y,vx,vy);
if (dis[tmp][vx][vy]>dis[u.z][u.x][u.y]+) {
dis[tmp][vx][vy]=dis[u.z][u.x][u.y]+;
if (!vis[tmp][vx][vy]){
vis[tmp][vx][vy]=;
q.push((data){vx,vy,tmp});
}
}
}
vis[u.z][u.x][u.y]=;
}
rep(i,,(<<D)-) {
int tmp=-dis[i][x][y];
rep(j,,D) if (i&bin[j-]) tmp+=v[j];
ans=max(ans,tmp);
}
}
int main(){
bin[]=; rep(i,,) bin[i]=bin[i-]*;
n=read(); m=read();
D=read();
rep(i,,D) v[i]=read();
clr(mp,-);
rep(i,,n) rep(j,,m){
char ch=getchar(); while (!isdigit(ch)&&ch!='#') ch=getchar();
if (ch=='#') continue;
else mp[i][j]=ch-'';
if (ch!='') p[ch-''][]=i,p[ch-''][]=j;
}
ans=;
rep(i,,n) rep(j,,m)
if (mp[i][j]==)spfa(i,j);
printf("%d\n",ans);
return ;
}