本人于2025年7月12日00:04ac了此题，现已封帖

我已经要抑郁了。各种思路和题解都看过了也重写过。真的是被资本做局了。

单bfs73pts,2wa1TLE：

#include<iostream>
#include<queue>
using namespace std;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
struct node{
    int x,y,cnt;
};
queue<node> q;
int n,k,fat=2;//初始体积为（1+2+2）（1+2+2）=5*5
char m[305][305];//地图
bool vis[305][305];//标记
bool check(int x,int y,int w){//检查是否可以通过
    for(int i=x-w;i<=x+w;i++){
        for(int j=y-w;j<=y+w;j++){
            if(m[i][j]=='*') return 0;
        }
    }
    return 1;
}
void bfs(int i,int j){
    q.push({i,j,0});
    vis[i][j]=1;
    while(!q.empty()){
        node t=q.front();
        q.pop();
        if(t.x==n-2&&t.y==n-2){//到了终点输出步数
            cout<<t.cnt;
            exit(0);
        }
        if(t.cnt==k) fat=1;//步数达到k fat-1，体积变为（5-1-1）（5-1-1）=3*3
        else if(t.cnt==2*k) fat=0;//同上，体积变为1*1
        if(fat) q.push({t.x,t.y,t.cnt+1});
        for(int ppp=0;ppp<4;ppp++){//正常搜联通块
            int nx=t.x+dx[ppp],ny=t.y+dy[ppp];
            if(nx>0&&nx<=n&&ny>0&&ny<=n&&check(nx,ny,fat)&&!vis[nx][ny]){//不越界，可以通过并且没走过
                q.push({nx,ny,t.cnt+1});
                vis[nx][ny]=1;//标记了一处地点
            }
        }
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){//nbsahdbvjlsadbsdjbsnkdbnsrkbnrm.bnmsbkerbsebv.jkvhjwz.hfagj
        for(int j=1;j<=n;j++){
            cin>>m[i][j];
            vis[i][j]=(m[i][j]=='+'?0:1);
        }
    }
    bfs(3,3);
    return 0;
}

bfs+二维前缀和优化0pts:10MLE(为什么啊啊啊啊啊啊啊啊啊啊

#include<iostream>
#include<queue>
using namespace std;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
struct node{
    int x,y,cnt;
};
queue<node> q;
int n,k,fat=2;//初始体积为（1+2+2）（1+2+2）=5*5
char m[305][305];//地图
bool vis[305][305];//标记
int ps[305][305];
void bfs(int i,int j){
    q.push({i,j,0});
    vis[i][j]=1;
    while(!q.empty()){
        node t=q.front();       
        q.pop();
        if(t.x==n-2&&t.y==n-2){//到了终点输出步数
            cout<<t.cnt;
            exit(0);
        }
        if(t.cnt==k&&fat==2) fat=1;//步数达到k fat-1，体积变为（5-1-1）（5-1-1）=3*3
        else if(t.cnt==2*k&&fat==1) fat=0;//同上，体积变为1*1
        if(fat) q.push({t.x,t.y,t.cnt+1});
        for(int ppp=0;ppp<4;ppp++){//正常搜联通块
            int nx=t.x+dx[ppp],ny=t.y+dy[ppp];
            if(nx-fat>0&&nx+fat<=n&&ny-fat>0&&ny+fat<=n&&ps[nx+fat][ny+fat]-ps[nx+fat][ny-fat-1]-ps[nx-fat-1][ny+fat]+ps[nx-fat-1][ny-fat-1]==0){//不越界，可以通过并且没走过
                q.push({nx,ny,t.cnt+1});
                vis[nx][ny]=1;//标记了一处地点
            }
        }
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){//请输入文本
        for(int j=1;j<=n;j++){
            char c;
            cin>>c;
            vis[i][j]=(c=='+'?0:1);
        }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ps[i][j]=ps[i-1][j]+ps[i][j-1]+vis[i][j]-ps[i-1][j-1];
    bfs(3,3);
}

嗯。对。就是这样的。请输入文本。