蓝桥杯2019年第十届国赛真题-大胖子走迷宫

解题思路:

BFS  多加几个判断条件

注意事项:

当时间<2*k，可能原地不动，也可能动。

当时间>=2*k之后，就不用原地不动了，直接走。

参考代码:

#include"bits/stdc++.h"
using namespace std;
char a[1000][1000];
int v[1000][1000];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int n;
int k;
int len;
struct node{
	int x;
	int y;
	int step;
};
queue<node> q;
bool check(int xx,int yy,int time){
	if(time<k)
	len=2;
	else if(time>=k&&time<2*k)
	len=1;
	else
	len=0;
	for(int i=xx-len;i<=xx+len;i++){
		for(int j=yy-len;j<=yy+len;j++){
	            if(a[i][j]=='*')
				return false;	 
	  }
    } 
  if(xx<=0||yy<=0||xx>n||yy>n||v[xx][yy]==1||a[xx][yy]=='*')
  return false;
 return true;
}
void bfs(int nx,int ny){
	node pre;
	node next;
	node pree;
	pre.x=nx;
	pre.y=ny;
	pre.step=0;
	v[pre.x][pre.y]=1;
	q.push(pre);
	while(q.size()){
		pre=q.front();
		q.pop();
		
		if(pre.x==n-2&&pre.y==n-2){
			cout<<pre.step;
			return ;
		}
		
		if(pre.step<2*k ){            //原地不动 
		 pree.step=pre.step+1;
		 pree.x=pre.x;
		 pree.y=pre.y;
		 q.push(pree);
		} 
		
		for(int i=0;i<4;i++){                
			next.x=pre.x+dx[i];
			next.y=pre.y+dy[i];
			next.step=pre.step;
			if(check(next.x,next.y,next.step)){    //能动
				v[next.x][next.y]=1;
			 	 next.step=pre.step+1;
				q.push(next);
			}
		}
 	}
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	
	bfs(3,3);
	return 0;
}