FZU 2092 bfs+记忆化搜索

时间：2023-03-08 15:56:42

晚上团队训练赛的题

和普通bfs不同的是 这是同时操纵人与影子两个单位进行的bfs 由于可能发生人和影子同时接触水晶 所以不可以分开操作

当时使用node记录人和影子的位置 然后进行两重for循环来分别改变位置 结果超内存 分析了一下应该是队列超了内存 毕竟如果每个点都存入的话一个点最多可以衍生出25个node 然后t最大为200s 一定会超

之间还发生了一些并不能理解的bug 被逼到最后重构才拿到了一个超内存 名次也不好 急需一个ac来赶上去 简直要烧起来了 侧面反映心理素质还是差一些

当时未能想起来改进的办法 后来百度别人的博客学习了一下记忆化搜索(总感觉以前好像学习过...)

其中有一些很省时间的技巧 例如node中的函数

如果一个点的时间没有被走过(vis=-1)那么就进行搜索它

如果这个点探索过并且小于h 那就覆盖它(之所以不放进队列是因为放进去也没有意义了 拿一次就够了 (如果放进去的话也可以AC不过时间增加一倍) )

#include<cstdio>

#include<iostream>

#include<math.h>

#include<cstring>

#include<algorithm>

#include<map>

#include<queue>

using namespace std;

int ma[12][12];

int vis[12][12][12][12][205];

int bs[12][12][205];

char s[15];

int n,m;

int t,v,x,y;

int wan;

int ans;

struct node

{

    int x1,x2,y1,y2;

    int t;

    node(int x1,int y1,int x2,int y2,int t):x1(x1),y1(y1),x2(x2),y2(y2),t(t){}

};

int dx[5]={0,0,0,-1,1};

int dy[5]={1,-1,0,0,0};

void bfs()

{

    queue<node >q;

    vis[1][1][1][1][0]=0;

    q.push(node(1,1,1,1,0));

    while(!q.empty())

    {

        node te=q.front();

        q.pop();

        if(te.t>200)

            break;

        for(int i=0;i<5;i++)

        {

            for(int k=0;k<5;k++)

            {

                int tt=te.t+1;

                int x1=te.x1+dx[i];

                int x2=te.x2+dx[k];

                int y1=te.y1+dy[i];

                int y2=te.y2+dy[k];

                if(ma[x1][y1]+ma[x2][y2]<2)

                    continue;

                int h=vis[te.x1][te.y1][te.x2][te.y2][te.t];

                h+=bs[x1][y1][tt]+bs[x2][y2][tt];

                if(x1==x2&&y1==y2)

                    h-=bs[x1][y1][tt];

                if(h>vis[x1][y1][x2][y2][tt])

                {

                    if(vis[x1][y1][x2][y2][tt]==-1)

                    {

                        q.push(node(x1,y1,x2,y2,tt));

                    }

                    vis[x1][y1][x2][y2][tt]=h;

                    ans=max(h,ans);

                }

            }

        }

    }

}

int main(){

int tt;

scanf("%d",&tt);

while(tt--)

{

    scanf("%d%d",&n,&m);

    memset(ma,0,sizeof(ma));

    for(int i=1;i<=n;i++)

    {

        scanf("%s",s);

        for(int k=0;k<m;k++)

        {

            if(s[k]=='.')

            {

                ma[i][k+1]=1;

            }

        }

    }

    int p;

    scanf("%d",&p);

    ans=0;

    memset(vis,-1,sizeof(vis));

    memset(bs,0,sizeof(bs));

    for(int i=1;i<=p;i++)

    {

        scanf("%d%d%d%d",&t,&x,&y,&v);

        bs[x][y][t]+=v;

    }

    bfs();

    printf("%d\n",ans);

}

}

　　

相关文章