蓝桥杯练习系统（算法训练）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);//bfswhile(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数组中，然后对每一个点进行判断。