晚上团队训练赛的题
和普通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
",ans);
}
}