U38098 PION贪吃蛇 20分现场

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k,cnt,foodnum;
int a[210][210],bel[210][210],input[25][110],dead[25],next[50000];
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,1,-1};
struct snake{
	int len,headx,heady,lastx,lasty;
}snakes[25];
inline int exc(char c){
	if(c=='.'||c=='W')return 1;
	if(c=='#'||c=='S')return 2;
	if(c=='@'||c=='D')return 3;
	if(c=='&'||c=='A')return 4;
	return 0;
}
inline char ch(int c){
	if(c==1)return '.';
	if(c==2)return '#';
	if(c==3)return '@';
	if(c==4)return '&';
	return '0';
}
inline bool die(int x,int y){
	if(bel[x][y])return true;
	if(x<1||x>n||y<1||y>m)return true;
	return false;
}
void dfs(int x,int y,int lx,int ly,int num){
	bel[x][y]=num; snakes[num].len++;
	next[(x-1)*m+y]=(lx-1)*m+ly;
	if(a[x+1][y]==2&&(lx!=x+1||ly!=y))dfs(x+1,y,x,y,num);
	else if(a[x-1][y]==2&&(lx!=x-1||ly!=y))dfs(x-1,y,x,y,num);
	else if(a[x][y+1]==2&&(lx!=x||ly!=y+1))dfs(x,y+1,x,y,num);
	else if(a[x][y-1]==2&&(lx!=x||ly!=y-1))dfs(x,y-1,x,y,num);
	else{
		snakes[num].lastx=x,snakes[num].lasty=y;
		return;
	}
}
void del(int x,int y,int num){
	while(next[(x-1)*m+y]>0){
		int lx=next[(x-1)*m+y]/m+1,ly=next[(x-1)*m+y]%m;
		a[x][y]=4; bel[x][y]=0; next[(x-1)*m+y]=0;
		x=lx, y=ly;
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		string s; cin>>s;
		for(int j=0;j<m;j++){
			a[i][j+1]=exc(s[j]);
			if(a[i][j+1]==4)foodnum++;
			if(a[i][j+1]==3){
				cnt++;
				snakes[cnt].headx=i,snakes[cnt].heady=j+1;
			}
		}
	}
	for(int i=1;i<=cnt;i++){
		string s; cin>>s;
		for(int j=0;j<m;j++)input[i][j+1]=exc(s[j]);
	}
	for(int i=1;i<=cnt;i++)
		dfs(snakes[i].headx,snakes[i].heady,1,0,i);
	for(int i=1;i<=k;i++){
		for(int j=1;j<=cnt;j++){
			if(dead[j])continue;
			int ux=snakes[j].headx,uy=snakes[j].heady;
			int vx=ux+dx[input[j][i]],vy=uy+dy[input[j][i]];
			if(die(vx,vy)){
				dead[j]=1;
				del(ux,uy,j);
				foodnum+=snakes[j].len;
				snakes[j].len=0;
			}else if(a[vx][vy]==4){
				snakes[j].len++;
				a[ux][uy]=2; next[(ux-1)*m+uy]=(vx-1)*m+vy;
				snakes[j].headx=vx,snakes[j].heady=vy;
				a[vx][vy]=3; bel[vx][vy]=j;
				foodnum--;
			}else{
				a[ux][uy]=2; next[(ux-1)*m+uy]=(vx-1)*m+vy;
				snakes[j].headx=vx,snakes[j].heady=vy;
				bel[vx][vy]=j; a[vx][vy]=3;
				int lx=snakes[j].lastx,ly=snakes[j].lasty;
				a[lx][ly]=1; bel[lx][ly]=0;
				int nx=next[(lx-1)*m+ly]/m+1,ny=next[(lx-1)*m+ly]%m;
				snakes[j].lastx=nx,snakes[j].lasty=ny;
			}
		}
	}
	for(int i=1;i<=cnt;i++)printf("%d %d\n",snakes[i].len,i);
	printf("%d\n",foodnum);
	return 0;
}