解题思路:本题相比普通的迷宫问题 多了一个无敌道具和陷阱 所以普通的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 人评分
永远的丰碑 (C语言代码)浏览:656 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:684 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:646 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:623 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:675 |
WU-字符串比较 (C++代码)浏览:759 |
C语言程序设计教程(第三版)课后习题6.6 (C++代码)浏览:633 |
回文数字 (C语言代码)浏览:2510 |
1013题解浏览:561 |
A+B for Input-Output Practice (III) (C语言代码)浏览:569 |