small code king(直译为小码王)，一个新出牌的编程培训机构，总是有一些奇奇怪怪的题目让学员做。。。
第一次就是。。。一个BFS题。不知这东东咋想的，我先不说这题的不同之处，先上题。
【题目描述】
小z身处在一个迷宫中，小z每分钟可以走到上下左右四个方向的相邻格之一。迷宫中有一些墙和障碍物。
同时迷宫中也有一些怪兽，当小z碰到任意一个怪兽时，小z需要将怪兽消灭掉才可以离开此方格。但消
灭怪兽会花费一定的时间。现在小z想知道走出迷宫需要花费的最少时间
【输入格式】
对于每组数据第一行为两个整数R和C(1<=R,C<=20)。以下R行有C个字符，即迷宫地图。
其中"#"代表墙和障碍物，"."表示空地，[1~9]的数字代表此处有怪兽以及消灭此处的怪兽需要的时间。
对于每组数据保证起始位置和出口唯一。
【输出格式】
对于每组数据，输出走出迷宫的最短时间(单位:分钟)。如果无法走出迷宫则输出"IMPOSSIBLE"。
【输入样例】
3 4
.Z..
.234
#.W.
【输出样例1】
5
【输入样例2】
4 4
Z.1.
.32.
##4.
W#..
【输出样例2】
IMPOSSIBLE
抄题辛苦，求求关注和普通的BFS不太一样，这题的变式点不在走的方式，而是在于走到一个点的时间不太一样了。
有其问必有其果，这题一定是可以做出来的（说了和没说一样。。。），只不过方法不太一样。
想想，一个点到另一个点所需的时间，感觉有点耳熟。。。
这不就是边权吗？可以用图论做一做啊！这种就是典型的最短路径问题嘛！
但是这个有点超纲（超现在我讲的纲），可能以后会写到最短路，但至少这个月不会。。。
那我们该怎么做呢？首先我们先来回顾一下广搜的原理：因为时间越少，它就越有可能先到终点站。
所以我们用queue来存储，把少的取出来，再把多一点的放进去，又因为queue先进先出，先放进的肯定是时间最少的，那就把他拿出来找呗！
那我们想想，这样直接套到这题目里面会怎么样呢？
很明显，因为走一个的时间不一定是1了，所以先放进去的时间不一定时间最少，明显违背了广搜的硬性要求，不错就怪了！
那该怎么办呢。。。
想想我讲过哪些数据结构：栈，队列，链表，数组，还有。。。对，优先队列！
优先队列明显可以正好满足要求，只需要再改成结构体类型的就完事了
struct node{int x,y,step;
}
bool operator < (node a,node b){return b.step<a.step;
}
priority_queue<node> q;
当然，如果你有强迫症，你非要用正规的定义法，那你也可以这样
struct node{int x,y,step;bool operator < (node a,node b){return b.step<a.step;}
}
priority_queue< node,vector<node>,greater<node> >;不适应正常，因为我也不适应，做他个几千道题就好了
那这就很easy了
直接上代码
#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,step;
}arr[44444],st,ed,now,nxt;
char mp[222][222];
int vis[222][222];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
bool operator < (node a,node b){return b.step<a.step;
}
int main(){int n,m,t,flag;flag=0;priority_queue<node>q;scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",mp[i]+1);for(int j=1;j<=m;j++){if(mp[i][j]=='Z') st.x=i,st.y=j; if(mp[i][j]=='W') ed.x=i,ed.y=j;}}st.step=0;q.push(st);vis[st.x][st.y]=1;while(q.size()){now=q.top();if(now.x==ed.x&&now.y==ed.y){printf("%d\n",now.step);flag=1;break;}for(int i=0;i<4;i++){nxt=now;nxt.x+=dir[i][0];nxt.y+=dir[i][1];if(nxt.x>=1&&nxt.x<=n&&nxt.y>=1&&nxt.y<=m&&!vis[nxt.x][nxt.y]&&mp[nxt.x][nxt.y]!='#'){if(mp[nxt.x][nxt.y]>='0'&&mp[nxt.x][nxt.y]<='9') nxt.step+=(1+mp[nxt.x][nxt.y]);else nxt.step+=1;q.push(nxt);vis[nxt.x][nxt.y]=1;}}q.pop();}if(!flag) printf("IMPOSSIBLE\n");return 0;
}还有一道同类型的题目
题目描述
在一个n*m的迷宫里，有一个萌新被困住了，你作为一个久经码场的战士，决定去营救
萌新。地图中还会有一些守卫，你必须打败守卫才能通过守卫所在的位置，打败守卫
需要花费1分钟，移动一步需要花费一分钟，每次你只能往上下左右某个方向移动一步。
问你最少需要花费多少时间才能救到萌新。输入格式
第一行输入两个整数 n,m 接下来n行每行输入m个字符'#'代表障碍物，无法直接通过'.'代表空地，可以直接通过'G'代表守卫，你需要打败他才能通过'M'代表萌新所在的位置'@'表示你所在的位置输出格式
如果可以营救到萌新，就输出最少需要花费的分钟数如果不可以，输出“You can't save Mengxin”输入输出样例
输入 #17 8
#.#####.
#.M#..@.
#..#G...
..#..#.#
#...##..
.#......
........
输出 #113
说明/提示
1<=n,m<=200，输入保证合法
没抄题，但是必须点赞，哼再放下正解
#include<bits/stdc++.h>
using namespace std;
int n,m,stx,sty,edx,edy,dir[4][2]={0,1,0,-1,-1,0,1,0},vis[222][222];
struct node{int x,y,s;};
char mp[222][222];
bool operator < (node a,node top){return top.s<a.s;}
int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>mp[i][j];if(mp[i][j]=='@') stx=i,sty=j;if(mp[i][j]=='#') vis[i][j]=1;if(mp[i][j]=='M') edx=i,edy=j;}priority_queue<node> q;q.push((node){stx,sty,0});while(!q.empty()){node now=q.top();q.pop();if(now.x==edx&&now.y==edy){printf("%d\n",now.s);return 0;}for(int i=0;i<4;i++){int xx=now.x+dir[i][0],yy=now.y+dir[i][1];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){vis[xx][yy]=1;if(mp[xx][yy]=='G') q.push((node){xx,yy,now.s+2});else q.push((node){xx,yy,now.s+1});}}}printf("You can't save Mengxin\n");return 0;
}很容易看出，这并不是我喜欢的写法，这是小码王的。
但是，SCK又双叒叕秀了我一脸
看题
【BFS】走迷宫2
题目描述
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走，还有的是传送门，走到传送门可以瞬间传送至任意传送门。给定一个迷宫，求从左上角走到右下角最少需要走多少步。只能在水平方向或垂直方向走，不能斜着走。输入格式
第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1≤ R，C ≤ 40)接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。空地格子用‘.’表示，有障碍物的格子用‘#’表示，传送门用'$'表示，传送门数目小于10迷宫左上角和右下角都是‘.’。输出格式
输出从左上角走到右下角至少要经过多少步。计算步数要包括起点和终点。如果走不到终点输出-1。输入输出样例
输入 #15 5
.$###
##...
#.#.#
#.#.#
#.#$.
输出 #13
抄题很累，必须三连！我想了想，干了两小时，干了个毛线
#include<bits/stdc++.h>
using namespace std;
struct place{int x,y,step;
};
int n,m,mmap[41][41],dir[4][2]={{1,0},{0,-1},{-1,0},{0,1}};bool vis[41][41];
int fly[11][2],flyn=0;
bool operator < (place a,place b){return b.step<a.step;
}
void bfs(){priority_queue<place> q;place front;front.x=0,front.y=0,front.step=0;q.push(front);while(!q.empty()){front=q.top();q.pop();if(front.x==n-1&&front.y==m-1){cout<<front.step<<endl;return ;}if(mmap[front.x][front.y]!=2){for(int i=0;i<4;i++){int dx=front.x+dir[i][0],dy=front.y+dir[i][1];if(dx>=0&&dy>=0&&dx<n&&dy<m&&(!mmap[dx][dy]||mmap[dx][dy]==2)&&!vis[dx][dy]){vis[dx][dy]=1;place now;now.x=dx,now.y=dy,now.step=front.step+1;q.push(now);}}}else{for(int i=0;i<flyn;i++){if(!(fly[i][0]==front.x&&fly[i][1]==front.y)){int dx=fly[i][0],dy=fly[i][1];if(!vis[dx][dy]){vis[dx][dy]=1;place now;now.x=dx,now.y=dy,now.step=front.step+1;q.push(now);}}}}}cout<<-1<<endl;
}
int main(){cin>>n>>m;for(int i=0;i<n;i++)for(int j=0;j<m;j++){char ch;cin>>ch;if(ch=='.') mmap[i][j]=0;if(ch=='#') mmap[i][j]=1;if(ch=='$') mmap[i][j]=2,fly[flyn][0]=i,fly[flyn++][1]=j;}bfs();return 0;
}
//这才是我的style但是，他给了我一个20分，其他全wa
我惊了，看了看官方做法
#include<bits/stdc++.h>
using namespace std;
queue<int> x,y,a,b;
int dis[4][2]={{1,0},{0,1},{-1,0},{0,-1}},n,m,vis[41][41],temp[41][41];
char c[41][41];
int main(){scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>c[i][j];if(c[i][j]=='$'){a.push(i);b.push(j);}if(c[i][j]=='#') vis[i][j]=1;}}x.push(1);y.push(1);temp[1][1]=1;int flag=0;while(!x.empty()){if(x.front()==n&&y.front()==m){flag=1;break;}vis[x.front()][y.front()]=1;for(int i=0;i<4;i++){int dx=x.front()+dis[i][0],dy=y.front()+dis[i][1];if(c[dx][dy]=='$'&&!vis[dx][dy]){while(!a.empty()){x.push(a.front());y.push(b.front());vis[a.front()][b.front()]=1;temp[a.front()][b.front()]=temp[x.front()][y.front()]+1;a.pop();b.pop();}}if(dx>=1&&dy>=1&&dx<=n&&dy<=m&&!vis[dx][dy]){vis[dx][dy]=1;temp[dx][dy]=temp[x.front()][y.front()]+1;x.push(dx);y.push(dy);}}x.pop();y.pop();}if(flag) printf("%d\n",temp[n][m]);else printf("-1");return 0;
}这不是差不多吗？（此处指思路）有没有大神能帮我找下错，实在找不出了，我那fw老师也没有改对我这道题。
最后求一下三连，谢谢（ 毁 灭 吧 赶 紧 的 ）
版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间：8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态
