做混剪素材下载网站seo专业培训中心
资源限制
内存限制：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数组中，然后对每一个点进行判断。