可以用前缀和来判定是否能走
就障碍的地方记为0
其他思路都和其他题解一样
仅137ms

#include<bits/stdc++.h>
using namespace std;
int const N=310;
int n,k;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
struct now{
    int x,y,tick;
};
int f[N][N],c[N][N];
char ma[N][N];
queue<now> q;
bool st[N][N];
bool check(int x,int y,int nt){
    int m=2;
    if(nt>=2*k)m=0;
    else if(nt>=k) m=1;
    if(y-m<0 or x-m<=0 or y+m>n or x+m>n)return false;
    return f[x+m][y+m]+f[x-m-1][y-m-1]-f[x+m][y-m-1]-f[x-m-1][y+m]==(2*m+1)*(2*m+1);
}
int bfs(){
    q.push({3,3,0});
    st[3][3]=true;
    while(!q.empty()){
        now t=q.front();q.pop();
        int nt=t.tick;
        if(nt<2*k)
        q.push({t.x,t.y,nt+1});
        //cout<<t.x<<" "<<t.y<<" "<<t.tick<<endl;
        if(t.x==n-2 and t.y== n-2)return nt;
        for(int i=0;i<4;i++){
            int tx=t.x+dx[i],ty=t.y+dy[i];
            if(!st[tx][ty] and check(tx,ty,nt)){
                q.push({tx,ty,nt+1});
                st[tx][ty]=true;
            }
        }
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        scanf("%s",ma[i]+1);
        for(int j=1;j<=n;j++){
            if(ma[i][j]=='+')c[i][j]=1;
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+c[i][j];
        }
    }
    cout<<bfs();
    return 0;
}