记录

代码：

//总体思路：1.位运算求出在不同体积下可以到的地方
//			2. BFS，在碰到在当前体积已经遍历过的点时，将其体积更新时的下一步放入优先队列 
#include <bits/stdc++.h>
using namespace std;
char mp[305][305];
bitset<305> bit[5][305];
int n,k,nx[4]={0,1,0,-1},ny[4]={1,0,-1,0};
int bjt[305][305][5],flag;
struct T{
	int x,y,tim,bj;
	bool operator <(const T temp)const{
		return tim>temp.tim;
	} 
};
priority_queue<T> que;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>mp[i][j];
	
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)	if(mp[i][j]=='*') bit[0][i][j]=1;//本身为1 
	
	for(int i=0;i<=n+1;i++) bit[0][i][0]=bit[0][0][i]=bit[0][n+1][i]=bit[0][i][n+1]=1;//边界预处理 
	
	for(int i=0;i<=n+1;i++) bit[1][i]=(bit[0][i])|(bit[0][i]<<1)|(bit[0][i]>>1);//同一层连续3个（左右和自己）是否有1 
	
	for(int i=1;i<=n;i++) bit[2][i]=(bit[1][i]|bit[1][i-1]|bit[1][i+1]);//上一层，本层，下一层（3*3方阵） 是否有1
	
	bit[2][0]=bit[1][0];bit[2][n+1]=bit[1][n+1];//边界继承 
	
	for(int i=0;i<=n+1;i++) bit[3][i]=(bit[2][i]<<1)|(bit[2][i]>>1);//左右3*3方阵（3*5方阵）是否有1 
	
	for(int i=1;i<=n;i++) bit[4][i]=bit[3][i-1]|bit[3][i+1];//上下3*5方阵（5*5方阵） 是否有1 
	
	bit[4][0]=bit[3][0];bit[4][n+1]=bit[3][n+1];
	
	 //位运算得到在不同体积下可以移动到哪些地方（1代表不能被移动到） 
//	for(int i=0;i<=n+1;i++) cout<<bit[4][i]<<endl;
	que.push((T){3,3,0,4});
	while(!que.empty()){
		T ls=que.top();que.pop();
		if(ls.tim>2*k) ls.bj=0;
		else if(ls.tim>k) ls.bj=2;//更新体积 
		if(bit[ls.bj][ls.x][ls.y]) continue;
		if(bjt[ls.x][ls.y][ls.bj]){//如果已经在当前体积被遍历，让其原地等待到体积更新 
			if(bjt[ls.x][ls.y][ls.bj]==1){//没有已经原地等待的元素 
				bjt[ls.x][ls.y][ls.bj]=2;//标记 
				if(ls.bj!=0){
					ls.tim=(ls.tim/k+1)*k+1;//在时间更新的基础上再加一步（否则体积无法被更新） 
					ls.bj-=2;
					for(int i=0;i<4;i++){
						int tmpx=ls.x+nx[i],tmpy=ls.y+ny[i];
						if(tmpx-ls.bj/2<1||tmpy-ls.bj/2<1||tmpx+ls.bj/2>n||tmpy+ls.bj/2>n) continue;
						que.push((T){tmpx,tmpy,ls.tim,ls.bj});
					}
				}
			}
			continue;
		}
		
		bjt[ls.x][ls.y][ls.bj]=1;
		if(ls.x==n-2&&ls.y==n-2){
			printf("%d",ls.tim);
			return 0;
		}
		
		ls.tim+=1;
		if(ls.tim>2*k) ls.bj=0;
		else if(ls.tim>k) ls.bj=2;
		for(int i=0;i<4;i++){
			int tmpx=ls.x+nx[i],tmpy=ls.y+ny[i];
			if(tmpx-ls.bj/2<1||tmpy-ls.bj/2<1||tmpx+ls.bj/2>n||tmpy+ls.bj/2>n) continue;
			que.push((T){tmpx,tmpy,ls.tim,ls.bj});
		}//正常拓展 
	}
	return 0;
}