博客类网站怎么做,wordpress 仿主题,纯英文网站建设,网络服务提供者知道网络用户利用其网络服务资源限制
内存限制#xff1a;256.0MB C/C时间限制#xff1a;1.0s Java时间限制#xff1a;3.0s Python时间限制#xff1a;5.0s
问题描述 勇士们不小心进入了敌人的地雷阵#xff08;用n行n列的矩阵表示#xff0c;*表示某个位置埋有地雷#xff0c;-表示某个…资源限制
内存限制256.0MB C/C时间限制1.0s Java时间限制3.0s Python时间限制5.0s
问题描述 勇士们不小心进入了敌人的地雷阵用n行n列的矩阵表示*表示某个位置埋有地雷-表示某个位置是安全的他们各自需要在规定的步数一步代表走到和当前位置相邻的位置内绕开地雷到达出口第一行第一格即坐标为0,0的位置才能完成任务告诉你每个勇士的位置xy和规定的步数s请你判断每个勇士能否顺利完成任务1代表“能”-1代表“不能”。
输入格式 输入数据的第一行为一个整数n第二行至第n1行是n行n列地雷阵的矩阵表示见输入样例第n2行至最后一行每行是一个勇士的位置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≤5000≤x≤n-10≤y≤n-11≤s≤500
对每一个要求的判断的点都进行bfs超时仅供理解题意
#includeiostream
#includequeue
#includestring.h
using namespace std;
const int N505;
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;cinn;char map[N][N];for(int i0;in;i){for(int j0;jn;j){cinmap[i][j];}}int x,y,num;while(cinxynum){queuepoint q;bool st[N][N];memset(st,0,sizeof(st));point start;start.xx;start.yy;start.step0;q.push(start);//bfswhile(q.size()){point pq.front();if(p.x0p.y0){break;}for(int i0;i4;i){int ap.xdx[i],bp.ydy[i];if(a0anb0bn!st[a][b]map[a][b]-){st[a][b]true;point next;next.xa,next.yb,next.stepp.step1;q.push(next);}}q.pop();}if(q.size()0){cout-1endl;}else{if(q.front().stepnum){cout1endl;}else cout-1endl;}}return 0;
} bfs一次
#includeiostream
#includequeue
#includestring.h
using namespace std;
const int N505;
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];
queuepoint q;
int n;void bfs(){while(q.size()){point pq.front();for(int i0;i4;i){int ap.xdx[i],bp.ydy[i];if(a0anb0bn!st[a][b]map[a][b]-){st[a][b]true;point next;next.xa,next.yb,next.stepp.step1;dist[a][b]p.step1;q.push(next);}}q.pop();}
}
int main(){cinn;for(int i0;in;i){for(int j0;jn;j){cinmap[i][j];}}point start;start.x0,start.y0,start.step0;q.push(start);bfs();int x,y,num;while(cinxynum){//dist为0有两种情况第一种是真的步数为0第二种是到不了 if(x0y0) cout1endl;//第一种 else{if(dist[x][y]!0dist[x][y]num){//在能到的前提下步长小于等于num 可行 cout1endl; }else cout-1endl;}}return 0;
} 思路在判断之前可以求出0,0到其他任何点的步数 存在dist数组中然后对每一个点进行判断。
