Description
Input
第一行两个整数N和M，为矩阵的边长。第二行一个整数D，为豆子的总个数。第三行包含D个整数V1到VD，分别为每颗豆子的分值。接着N行有一个N×M的字符矩阵来描述游戏矩阵状态，0表示空格，#表示障碍物。而数字1到9分别表示对应编号的豆子。
Output
仅包含一个整数，为最高可能获得的分值。
Sample Input
3 8
3
30 -100 30
00000000
010203#0
00000000
3
30 -100 30
00000000
010203#0
00000000
Sample Output
38
HINT
50%的数据满足1≤D≤3。100%的数据满足1≤D≤9，1≤N, M≤10，-10000≤Vi≤10000。
这个题呀，好题。
可以边搜索边更新状态，用射线法（自己百度吧）。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,d,ans,v[11],mp[11][11],x[11],y[11],dis[1105][11][11];
bool inq[1105][11][11];
int xx[]={-1,0,1,0},yy[]={0,-1,0,1};
struct node
{int x,y,z;//x,y坐标，z吃豆子的情况
};
queue<node>q;
void bfs(int sx,int sy)
{memset(dis,0x3f,sizeof(dis));memset(inq,0,sizeof(inq));node t;dis[0][sx][sy]=0;t.x=sx,t.y=sy,t.z=0;q.push(t);inq[0][sx][sy]=1;while(!q.empty()){node u=q.front();q.pop();inq[u.z][u.x][u.y]=0;for(int i=0;i<=3;i++)if(u.x+xx[i]>=1&&u.x+xx[i]<=n&&u.y+yy[i]>=1&&u.y+yy[i]<=m&&mp[u.x+xx[i]][u.y+yy[i]]==0){t.x=u.x+xx[i],t.y=u.y+yy[i],t.z=u.z;for(int j=1;j<=d;j++)if(t.y>y[j]&&((u.x>x[j]&&t.x<=x[j])||(u.x<=x[j]&&t.x>x[j])))//垂直于x轴的射线 t.z^=(1<<(j-1));if(dis[t.z][t.x][t.y]>dis[u.z][u.x][u.y]+1){dis[t.z][t.x][t.y]=dis[u.z][u.x][u.y]+1;if(!inq[t.z][t.x][t.y]){inq[t.z][t.x][t.y]=1;q.push(t);}}}}int end=(1<<d)-1;for(int i=1;i<=end;i++){int tmp=-dis[i][sx][sy];for(int j=1;j<=d;j++)if(i&(1<<(j-1)))tmp+=v[j];ans=max(tmp,ans);}
}
int main()
{scanf("%d%d%d",&n,&m,&d);for(int i=1;i<=d;i++)scanf("%d",&v[i]);for(int i=1;i<=n;i++){char s[15];scanf("%s",s+1);for(int j=1;j<=m;j++)if(s[j]=='#')mp[i][j]=1;else if(s[j]=='0')mp[i][j]=0;else{mp[i][j]=1;x[s[j]-'0']=i;y[s[j]-'0']=j;}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]==0)bfs(i,j);printf("%d\n",ans);return 0;
}