蓝桥杯练习系统（算法训练）ALGO-949 勇士和地雷阵

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　勇士们不小心进入了敌人的地雷阵（用n行n列的矩阵表示，'*'表示某个位置埋有地雷，'-'表示某个位置是安全的），他们各自需要在规定的步数（一步代表走到和当前位置相邻的位置）内绕开地雷到达出口（第一行第一格，即坐标为（0,0）的位置）才能完成任务，告诉你每个勇士的位置（x，y）和规定的步数s，请你判断每个勇士能否顺利完成任务（1代表“能”，-1代表“不能”）。

输入格式

　　输入数据的第一行为一个整数n；第二行至第n+1行是n行n列地雷阵的矩阵表示（见输入样例）；第n+2行至最后一行每行是一个勇士的位置x、y和到达出口规定的最大步数s，三个整数间用空格隔开。

输出格式

　　按顺序输出对每个勇士是否能顺利完成任务的判断（1代表“能”，-1代表“不能”），对每个勇士的判断占一行。

样例输入

5
-----
--*--
-**--
-**--
*-*--
0 1 1
0 4 3
1 1 3
1 4 2
2 0 3
3 0 4
3 3 2
4 1 3

样例输出

1
-1
1
-1
1
1
-1
-1

数据规模和约定

　　1≤n≤500，0≤x≤n-1，0≤y≤n-1，1≤s≤500

对每一个要求的判断的点都进行bfs，超时，仅供理解题意

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int N=505;
typedef struct point{
	int x;
	int y;
	int step;
}point;

int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int main(){
	int n;
	cin>>n;
	char map[N][N];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>map[i][j];
		}
	}
	int x,y,num;
	while(cin>>x>>y>>num){
		queue<point> q;
        bool st[N][N];
		memset(st,0,sizeof(st));
		point start;
		start.x=x;
		start.y=y;
		start.step=0;
		q.push(start);
		//bfs
		while(q.size()){
			point p=q.front();
			if(p.x==0&&p.y==0){
				break;
			}
			for(int i=0;i<4;i++){
				int a=p.x+dx[i],b=p.y+dy[i];
				if(a>=0&&a<n&&b>=0&&b<n&&!st[a][b]&&map[a][b]=='-'){
					st[a][b]=true;
					point next;
					next.x=a,next.y=b,next.step=p.step+1;
					q.push(next);
				}
			}
			q.pop();
		}
		if(q.size()==0){
			cout<<"-1"<<endl;
		}else{
			if(q.front().step<=num){
				cout<<1<<endl;
			}else cout<<-1<<endl;
		}
	}
	return 0;
} 

bfs一次

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int N=505;
typedef struct point{
	int x;
	int y;
	int step;
}point;

int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
char map[N][N];
int dist[N][N];//(0,0)到点的距离，如果无法到达（x,y）点，dist为0 
bool st[N][N];
queue<point> q;
int n;

void bfs(){
	while(q.size()){
		point p=q.front();
		for(int i=0;i<4;i++){
			int a=p.x+dx[i],b=p.y+dy[i];
			if(a>=0&&a<n&&b>=0&&b<n&&!st[a][b]&&map[a][b]=='-'){
				st[a][b]=true;
				point next;
				next.x=a,next.y=b,next.step=p.step+1;
				dist[a][b]=p.step+1;
				q.push(next);
			}
		}
		q.pop();
	}
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>map[i][j];
		}
	}
	point start;
	start.x=0,start.y=0,start.step=0;
	q.push(start);
	bfs();
	 
	int x,y,num;
	while(cin>>x>>y>>num){
		//dist为0有两种情况，第一种是真的步数为0，第二种是到不了 
		if(x==0&&y==0) cout<<1<<endl;//第一种 
		else{
			if(dist[x][y]!=0&&dist[x][y]<=num){//在能到的前提下，步长小于等于num 可行 
				cout<<1<<endl; 
			}else cout<<-1<<endl;
		}
	}
	return 0;
} 

思路：在判断之前，可以求出（0,0）到其他任何点的步数 ，存在dist数组中，然后对每一个点进行判断。