解题思路:本题相比普通的迷宫问题 多了一个无敌道具和陷阱 所以普通的bool数组没办法判断是否应该走这个格子,所以可以改用int 数组记录当前这个格子走过的最大无敌数值(当无敌时间超过这个vis数组记录的值时才将这个格子压入队列中)
注意事项:
参考代码:
#include<bits/stdc++.h>
#define DZT ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define N 1005
using namespace std;
typedef struct NODE{
int x,y,step,invi;
}NODE;
typedef pair<int,int> pii;
pii ch[4]={{0,1},{1,0},{-1,0},{0,-1}};
char ma[N][N];
int vis[N][N];//判断是否应该回到这个点 当剩余无敌步数大于vis记录的结果时候 才走
int n,k;
queue<NODE> q;//用于广度优先搜索
bool check(const int& x,const int& y){//判断有没有超出边界 以及是不是墙体
return x>=1 and x<=n and y>=1 and y<=n and ma[x][y]!='#';
}
int main()
{ DZT;
cin>>n>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>ma[i][j];
}
}
memset(vis,-1,sizeof(vis));
q.push({1,1,0,0});
vis[1][1]=0;
while(!q.empty()){
auto temp=q.front(); q.pop();
if(temp.x==n &&temp.y==n){
cout<<temp.step<<endl;
return 0;
}
for(int i=0;i<4;i++){
int t_x=ch[i].first; int t_y=ch[i].second;
t_x+=temp.x;t_y+=temp.y;
//判读 X % 以及对于普通路
if(ma[t_x][t_y]=='X'&&temp.invi==0){//没有无敌了 有无敌就正常压入队列
continue;
}
int t_invi=max(0,temp.invi-1);//更新无敌时间
if(ma[t_x][t_y]=='%'){
t_invi=k;
}
if(check(t_x,t_y)&&t_invi>vis[t_x][t_y]){//判断需不需要回走
vis[t_x][t_y]=t_invi;
q.push({t_x,t_y,temp.step+1,t_invi});
}
}
}
return 0;
}
0.0分
0 人评分
2005年春浙江省计算机等级考试二级C 编程题(3) (C语言代码)浏览:390 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:1031 |
最长单词 (C语言代码)浏览:1377 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:531 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:558 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:1072 |
罗列完美数 (C语言代码)浏览:491 |
sizeof的大作用 (C语言代码)浏览:1028 |
格式化数据输出 (C语言代码)浏览:822 |
整除问题 (C语言代码)浏览:526 |