PS:一道XX到我心态崩溃的好(傻逼)题。

先粘题目:

佐助被大蛇丸诱骗走了,鸣人在多少时间内能追上他呢?

BFS:noi6044鸣人与佐助-LMLPHP

已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费1个单位时间,打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了,则只可以走到没有大蛇丸手下的位置,不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动,大蛇丸的手下也不移动。请问,鸣人要追上佐助最少需要花费多少时间?

输入输入的第一行包含三个整数:M,N,T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200,0 ≤ T < 10
后面是M行N列的地图,其中@代表鸣人,+代表佐助。*代表通路,#代表大蛇丸的手下。输出输出包含一个整数R,代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助,则输出-1。样例输入

样例输入1
4 4 1
#@##
**##
###+
**** 样例输入2
4 4 2
#@##
**##
###+
****

样例输出

样例输出1
6 样例输出2
4

先写一下心路历程吧。

还是一道典型迷宫,唯一的新颖是查克拉的加入。

首先,我写出基本的迷宫框架。

一开始判断查克拉的办法稍有复杂,借鉴了网上大佬的方法,依旧通过一个数组来判断查克拉。

别的地方没有太大的更新了,贴代码吧:

#include<cstdio>
#include<cstdlib>
#include<cstring>
int u[]={,-,,},p[]={,,,-};
int n,m,w,xz,yz,h,l;
bool vis[][][];
char b[][];
struct mmap{int dis,cha,x,y;};
mmap q[];
void doit(){
int i,x,y,head=,tail=;
q[].x=h; q[].y=l; q[].cha=w; q[].dis=;
while(head<tail) {
head++;
for(i = ; i < ; ++i){
x=u[i]+q[head].x;
y=p[i]+q[head].y;
if(x<=||x>m||y<=||y>n||((!q[head].cha)&&(b[x][y]=='#'))||!(vis[x][y][q[head].cha]))continue;
tail++;
q[tail].x =x;
q[tail].y =y;
q[tail].dis=q[head].dis+;
q[tail].cha=q[head].cha;
if(b[x][y]=='#')q[tail].cha--;
vis[x][y][q[tail].cha]=false;
if(x==xz&&y==yz){
printf("%d",q[tail].dis);
return ;
}
}
}
printf("-1");
}
int main(){
memset(vis,true,sizeof(vis));
scanf("%d %d %d",&m,&n,&w);
for(int i = ; i <= m ; ++i){
scanf("%s",b[i]+);
for(int j = ; j <= n ; ++j){
if(b[i][j]=='@'){
h=i;
l=j;
}
if(b[i][j]=='+'){
xz=i;
yz=j;
}
}
}
doit();
return ;
}

关于这道题就是这样了,下面,总结一下吧。

最近比较浮躁,静不下心,不停地提交提交,也没有仔细看看代码。之前一直在RE,于是一直检查数组,没看出错误。RE了好几次决定静下心看看代码,发现在还没有改变查克拉的时候就改变了vis查克拉。这是第一个错误。

之后再测评就一直5分,寻找最后一分错在哪里(满分6分)。仔细研究正确代码后发现,自己的数组开小了。虽然地图最大200*200,但是每一个点的查克拉最多有10种出现情况,也就是说,在用结构体时,每一个位置可能占用10个房间,那么一共便需要400000个房间。

这道题用了大量的时间,但也还值得,有很多收获:

结构体在搜索中的优势非常明显,可以更加简单明了;

也给自己一个很惨的教训:在以后,无论是做什么事,都要静下心来慢慢分析,太浮躁的结果只能是既花费时间,又没有太大收获。

以后我会牢牢记住这一点的。

那么,再次打起精神来,投入接下来的战斗吧!

傅远植  加油!!!!

2017.5.21

05-06 13:37