记录编号	98919	评测结果	AAWWWWWWWW
题目名称	1611.积木游戏	最终得分	20
用户昵称	GDFRWMY	是否通过	未通过
代码语言	C++	运行时间	0.030 s
提交时间	2014-04-25 16:26:48	内存使用	0.43 MiB

#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("bricka.in");
ofstream fout("bricka.out");
int t,num,n,m,k,ans,o,l,r,f,xx,yy,d,e;
int xl[5000],yl[5000],map[100][100],v[5000],q[5000];
int main(){
	fin>>t;
	for(int y=0;y<t;y++){

		fin>>n>>m>>k;
		
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				fin>>map[i][j];
		
		ans=0;
		for (int i=1;i<=m;i++){
			memset(v,0,sizeof(v));
			memset(q,0,sizeof(q));
			o=0; num=0;l=r=1;
			q[1]=map[n][i];
			yl[1]=n;
			xl[1]=i;
			while (o<n*m-k){
				f=0;
				o++;
				for(int j=l;j<=r;j++)
					if (v[xl[j]+(yl[j]-1)*m]==0){
						//if (i==4)
						//fout<<q[j]<<' ';
						if (q[j]>f){
							f=q[j];
							d=xl[j]+(yl[j]-1)*m;
							e=j;
						}
				}
					//if (i==4)
						//fout<<endl;		
					v[d]=1;
					num=num+f;
                   xx=xl[e];
				   yy=yl[e];
				   //if (i==4)
					 //fout<<f<<' '<<xx<<' '<<yy<<' '<<(yy-2)<<' '<<n<<' '<<xx<<' '<<v[(yy-2)*n+xx]<<endl;
				   if (yy+1<=n)
					   if (v[yy*m+xx]==0) {
						   r++;
						   q[r]=map[yy+1][xx];
						   xl[r]=xx;
						   yl[r]=yy+1;
					   }
				   if (yy-1>0)
					   if (v[(yy-2)*m+xx]==0) {
						   r++;
						   q[r]=map[yy-1][xx];
						   xl[r]=xx;
						   yl[r]=yy-1;
					   }
				   if (xx+1<=m)
					   if (v[(yy-1)*m+xx+1]==0) {
						   r++;
						   q[r]=map[yy][xx+1];
						   xl[r]=xx+1;
						   yl[r]=yy;
					   }
				   if (xx-1>0)
					   if (v[(yy-1)*m+xx-1]==0) {
						   r++;
						   q[r]=map[yy][xx-1];
						   xl[r]=xx-1;
						   yl[r]=yy;
					   }	
			   
						   
			}
			if (num>ans)
				ans=num;
			//fout<<endl;
		}
		fout<<"Case "<<y+1<<':'<<ans<<endl;
	}
	return 0;
}