思路
用队列实现广度优先搜索,碰到障碍停止,来过了停止,越界了停止,这一部分跟普通的广度优先搜索差不多,那为何这道题评绿呢?因为小明的宽度会缩小啊,其实处理这个点十分简单,我们让小明在必要时停止运动,等待宽度变得合适时,再一次运动。代码是位置不变,时间增加时入队。
Code
#include <bits/stdc++.h>
#define int long long
const int N=305;
using namespace std;
inline int read(){
int t=1,x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') t=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return t*x;
}
char c;
int n,k,ans=1e9,a[N][N];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool vis[N][N];
struct node {
int x,y,time,size;
};
bool check(int x,int y,int size){
if(vis[x][y]) return 0;
for(int i=x-size;i<=x+size;i++)
for(int j=y-size;j<=y+size;j++)
if(i<1 || i>n || j<1 || j>n || a[i][j]) return 0;
return 1;
}
int work(int time){
if(time<k) return 2;
else if(time<2*k) return 1;
else return 0;
}
void bfs(){
queue<node> q;
vis[3][3]=1;
q.push((node){3,3,0,2});
while(!q.empty()){
node t=q.front();
q.pop();
if(t.x==n-2 && t.y==n-2){
cout<<t.time;
return ;
}
if(t.size!=0) q.push((node){t.x,t.y,t.time+1,work(t.time+1)});
for(int i=0;i<4;i++){
int xx=t.x+dx[i],yy=t.y+dy[i];
if(check(xx,yy,t.size)){
vis[xx][yy]=1;
q.push((node){xx,yy,t.time+1,work(t.time+1)});
}
}
}
}
signed main(){
n=read(),k=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>c;
if(c=='*') a[i][j]=1;
else a[i][j]=0;
}
}
bfs();
return 0;
}