记录编号	139892	评测结果	AAAAAAAAAA
题目名称	[SCOI 2009]围豆豆	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.139 s
提交时间	2014-11-17 15:53:47	内存使用	0.75 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int SIZEn=15,MAXD=9;
int n,m,D;
int V[MAXD]={0};
char board[SIZEn][SIZEn];
int dta[SIZEn][SIZEn]={0};
int f[SIZEn][SIZEn][1<<MAXD];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void printdig(int s){
	for(int i=0;i<D;i++) cout<<((s>>i)&1);
}
class STATE{//各种功能函数的排布好混乱......
public:
	int x,y,s;
	void print(void){
		cout<<x<<" "<<y<<" ";printdig(s);cout<<endl;
	}
	int getf(void){return f[x][y][s];}
	bool legal(void){
		if(!(0<=x&&x<n&&0<=y&&y<m)) return false;
		if(board[x][y]!='0') return false;
		return true;
	}
	void walk(int d){
		if(d==1) s^=dta[x][y];
		x+=dx[d],y+=dy[d];
		if(d==0) s^=dta[x][y];
	}
};
STATE getstate(int x_,int y_,int s_){
	STATE ans;
	ans.x=x_,ans.y=y_,ans.s=s_;
	return ans;
}
bool mark_f(STATE st,int k){
	int &a=f[st.x][st.y][st.s];
	if(a!=-1) return false;
	a=k;return true;
}
queue<STATE> Q;
void BFS(int sx,int sy){
	while(!Q.empty()) Q.pop();
	memset(f,-1,sizeof(f));
	STATE s=getstate(sx,sy,0),t;
	mark_f(s,0);Q.push(s);
	while(!Q.empty()){
		s=Q.front();Q.pop();int k=s.getf();
		for(int d=0;d<4;d++){
			t=s;t.walk(d);
			if(!t.legal()) continue;
			if(mark_f(t,k+1)) Q.push(t);
		}
	}
}
int calc_value(int s){
	int ans=0;
	for(int i=0;i<D;i++)
		if((s>>i)&1) ans+=V[i];
	return ans;
}
int calc(int sx,int sy){
	BFS(sx,sy);
	int ans=0;
	for(int s=0;s<(1<<D);s++){
		if(f[sx][sy][s]!=-1){
			ans=max(ans,calc_value(s)-f[sx][sy][s]);
		}
	}
	return ans;
}
void work(void){
	int ans=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(board[i][j]=='0') ans=max(ans,calc(i,j));
	printf("%d\n",ans);
}
void prepare(void){
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if('1'<=board[i][j]&&board[i][j]<='9'){
				//用0到8,不要问为什么,我有钱,任性→_→
				int t=board[i][j]-'0';t--;
				for(int k=i-1;k>=0;k--) dta[k][j]|=(1<<t);
			}
		}
	}
}
void read(void){
	scanf("%d%d",&n,&m);
	scanf("%d",&D);
	for(int i=0;i<D;i++) scanf("%d",&V[i]);
	getchar();
	for(int i=0;i<n;i++) scanf("%s",board[i]);
}
int main(){
	freopen("bean.in","r",stdin);
	freopen("bean.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}