2021年度训练联盟热身训练赛第五场 J——Kangaroo Commotion（bfs变式+哈希）

题目链接

bfs变式题，bfs的中难题。

1、新增两个变量，水平、竖直方向上的分速度vx,vy，每次移动，这两种速度变化值不能超过1（可以+1,-1,+0）。

—> 因为这个矩阵数据范围在50以内，到最后一个点时，两个速度还要归零，所以分速度最大为7。 （1+2+…+7+6+…+1）/ 2 < 50 ,到8就超过了。

—>对于每个的格子的不同状态可以用哈希。

2、矩阵有些点不能经过。（学长说这题出简单了，这个条件应该改成火山喷发类的，随步数也会影响周围格子不能经过）

3、要依次（按一定顺序）经过矩阵内的一些点，到其中点时不必归零，只要最后一个点归零即可

const int N=2e6+7;
int n,m,k;
char s[100][100];
bool mp[N];
int dx[9]={0,0,0,1,-1,-1,-1,1,1};
int dy[9]={0,1,-1,0,0,-1,1,-1,1};
struct node{
	int x,y,vx,vy,k,d;
	node(int x,int y,int vx,int vy,int k,int d):x(x),y(y),vx(vx),vy(vy),k(k),d(d){}
	bool cc(){
		if(x<1||y<1||x>n||y>m||s[x][y]=='#')	return 0;
		if(abs(vx)>7||abs(vy)>7)	return 0;
		return 1;
	}
	int hash(){	return x+y*50+(vx+8)*50*50+(vy+8)*50*50*15+(k+1)*50*50*15*15;	}
};
node go(node i,int dx,int dy){
	i.vx+=dx;	i.vy+=dy;
	i.x+=i.vx;	i.y+=i.vy;
	i.d++;
	return i;
}
queue<node>q;
int main(){
	n=read();	m=read();	k=read();
	for(int i=1;i<=n;i++){
		scanf("%s",&s[i][1]);
		for(int j=1;j<=m;j++){
			if(s[i][j]=='0'){
				q.push(node(i,j,0,0,1,0));
				mp[q.front().hash()]=1;
			}
		}
	}
	while(!q.empty()){
		node pre=q.front();	q.pop();
		for(int i=0;i<9;i++){
			node u=go(pre,dx[i],dy[i]);
			if(!u.cc())	continue;
			if(u.k==s[u.x][u.y]-'0')	u.k++;
			if(u.k==k+2&&s[u.x][u.y]-'0'==k+1&&u.vx==0&&u.vy==0){
				printf("%d",u.d);
				return 0;
			}
			int v=u.hash();
			if(mp[v])	continue;
			q.push(u);	mp[v]=1;
		}
	}
	printf("impossible");
}