记录编号	298846	评测结果	AAAAAAAAAA
题目名称	[BYVoid S1] 埃雷萨拉斯的宝藏	最终得分	100
用户昵称	open the window	是否通过	通过
代码语言	C++	运行时间	0.201 s
提交时间	2016-08-23 08:55:22	内存使用	1.16 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int a[101][101],h[50001][3],d[101][101],b[50001];
bool v[101][101];
int t,w,n,p,minx,hp;
int main()
{
	freopen("eldrethalas.in","r",stdin);
	freopen("eldrethalas.out","w",stdout);
	scanf("%d%d%d",&n,&p,&hp);
	for (int i=1; i<=p; ++i) scanf("%d",&b[i]);
	for (int i=1; i<=n; ++i)
	 for (int j=1; j<=n; ++j) 
	  scanf("%d",&a[i][j]);
	for (int i=1; i<=n; ++i)
	{
		w++;
		h[w][1]=1;
		h[w][2]=i;
		v[1][i]=true;
		d[1][i]=hp-b[a[1][i]];
	}
	while (t<w)
	{
		t++;
		for (int i=1; i<=n; ++i)
		 for (int j=1; j<=n; ++j)
		 {
		  if (abs(h[t][1]-i)+abs(h[t][2]-j)==1 && a[h[t][1]][h[t][2]]!=a[i][j] && d[i][j]<d[h[t][1]][h[t][2]]-b[a[i][j]])
		  {
		    d[i][j]=d[h[t][1]][h[t][2]]-b[a[i][j]];
		  	if (!v[i][j])
		    {
		    	v[i][j]=true;
		  	    w++;
		  	    h[w][1]=i;
		  	    h[w][2]=j;
		    }
		  }
		  if (a[h[t][1]][h[t][2]]==a[i][j] && d[i][j]<d[h[t][1]][h[t][2]])
		  {
		  	d[i][j]=d[h[t][1]][h[t][2]];
		  	if (!v[i][j])
		    {
		    	v[i][j]=true;
		  	    w++;
		  	    h[w][1]=i;
		  	    h[w][2]=j;
		    }
		  }
	    }
		v[h[t][1]][h[t][2]]=false;
	}
	for (int i=1; i<=n; ++i) minx=max(d[n][i],minx);
	if (minx<=0) printf("NO");
	 else printf("%d\n",minx);
}