首页 > 代码库 > BFS:noi6044鸣人与佐助

BFS:noi6044鸣人与佐助

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

先粘题目:

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

 

 技术分享

已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费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[4]={1,-1,0,0},p[4]={0,0,1,-1};
int n,m,w,xz,yz,h,l;
bool vis[210][210][20];
char b[210][210];
struct mmap{int dis,cha,x,y;};
mmap q[400100];
void doit(){
    int i,x,y,head=0,tail=1;
    q[1].x=h; q[1].y=l; q[1].cha=w; q[1].dis=0;
    while(head<tail) {
        head++; 
        for(i = 0 ; i < 4 ; ++i){
            x=u[i]+q[head].x;
            y=p[i]+q[head].y;
            if(x<=0||x>m||y<=0||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+1;
                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 = 1 ; i <= m ; ++i){
        scanf("%s",b[i]+1);
        for(int j = 1 ; j <= n ; ++j){
             if(b[i][j]==@){
                h=i;
                l=j;
            }
            if(b[i][j]==+){
                xz=i;
                yz=j;
            }
        }
    }
    doit();    
    return 0; 
}

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

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

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

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

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

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

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

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

傅远植  加油!!!!

2017.5.21

 

BFS:noi6044鸣人与佐助