题解：P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱
__jingzrui__ · · 题解
思考
于是我想到了 bfs
定义mp数字二维数组和c字符二维数组。
然后这道题与其他题不同的是新增了两个东西： 分别是X和%，X是陷阱除了无敌时间中外不能通过， 而%就是让你获得无敌时间的道具， 无敌时间的长度就是K。
我们理解题义后就要编写代码了！
代码实现
有注释版
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st{
int x , y , k , sp ;
}; //定义结构体
int mp[1005][1005] ; //数字地图
int n , k ;
char c[1005][1005] ; //字符地图
int dx[] = { 0 , 1 , 0 , -1 } ;
int dy[] = { -1 , 0 , 1 , 0 } ; //dfs路线
queue<st> que ; //定义队列
signed main()
{
cin >> n >> k ;
memset( mp , -1 , sizeof( mp ) ) ; //memset复值-1
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = 1 ; j <= n ; j++ ){
cin >> c[i][j] ;
}
} //无脑输入
que.push( { 1 , 1 , 0 , 0 } ) ; //将第一个的信息放入队列
mp[1][1] = 0 ;
while( !que.empty() ){
st head = que.front() ; //取出第一个
que.pop() ; //弹出第一个
int sp = head.sp + 1 ; // 定义step
for ( int kk = 0 ; kk <= 3 ; kk++ ){
int xx = head.x + dx[kk] ; //走的行数
int yy = head.y + dy[kk] ; //走的列数
if ( xx < 1 || xx > n || yy < 1 || yy > n ) continue ; //判断是否越界
if ( xx == n && yy == n ){
cout << sp ;
return 0 ;
} //到达终点
int wd = head.k ; //无敌时间
if ( c[xx][yy] == '#' ) continue ; //判断是否是墙壁
if ( c[xx][yy] == 'X' && wd == 0 ) continue ; //碰到陷阱并没有无敌时间
wd-- ; //无敌时间-1
if ( wd < 0 ) wd = 0 ; //处理
if ( c[xx][yy] == '%' ){
wd = k ;
c[xx][yy] = '.' ; //道具
}
if ( mp[xx][yy] >= wd ) continue ;
que.push( { xx , yy , wd , sp } ) ;
mp[xx][yy] = wd ; //赋值mp地图
}
}
cout << -1 ; //没有输出最后输出-1
return 0 ; //好习惯的养成qwq
}无注释版
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st{
int x , y , k , sp ;
};
int mp[1005][1005] ;
int n , k ;
char c[1005][1005] ;
int dx[] = { 0 , 1 , 0 , -1 } ;
int dy[] = { -1 , 0 , 1 , 0 } ;
queue<st> que ;
signed main()
{
cin >> n >> k ;
memset( mp , -1 , sizeof( mp ) ) ;
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = 1 ; j <= n ; j++ ){
cin >> c[i][j] ;
}
}
que.push( { 1 , 1 , 0 , 0 } ) ;
mp[1][1] = 0 ;
while( !que.empty() ){
st head = que.front() ;
que.pop() ;
int sp = head.sp + 1 ;
for ( int kk = 0 ; kk <= 3 ; kk++ ){
int xx = head.x + dx[kk] ;
int yy = head.y + dy[kk] ;
if ( xx < 1 || xx > n || yy < 1 || yy > n ) continue ;
if ( xx == n && yy == n ){
cout << sp ;
return 0 ;
}
int wd = head.k ;
if ( c[xx][yy] == '#' ) continue ;
if ( c[xx][yy] == 'X' && wd == 0 ) continue ;
wd-- ;
if ( wd < 0 ) wd = 0 ;
if ( c[xx][yy] == '%' ){
wd = k ;
c[xx][yy] = '.' ;
}
if ( mp[xx][yy] >= wd ) continue ;
que.push( { xx , yy , wd , sp } ) ;
mp[xx][yy] = wd ;
}
}
cout << -1 ;
return 0 ;
}