2013杭州区域赛现场赛二水。。。

类似“胜利大逃亡”的搜索问题,有若干个宝藏分布在不同位置,问从起点遍历过所有k个宝藏的最短时间。

思路就是,从起点出发,搜索到最近的一个宝藏,然后以这个位置为起点,搜索下一个最近的宝藏,直至找到全部k个宝藏。有点贪心的感觉。

由于求最短时间,BFS更快捷,但耗内存,这道题就卡在这里了。。。

这里记录了我几次剪枝的历史。。。题目要求内存上限32768KB,就差最后600KB了。。。但我从理论上觉得已经不能再剪了,留下的结点都是盲目式搜索必然要访问的结点。

在此贴上剪枝到33292KB的代码,注释里说明了剪掉的部分(剪枝策略可能还有不正确的地方,仅供参考)

 #include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAX_N=;
int n,m,k;
int sx,sy;
int dx[]={,,,-},dy[]={,-,,};
char G[MAX_N+][MAX_N+];
int cur_step; struct Node
{
int x,y,step,g;//每个点的坐标、走到这里的步数、到这一点已找到的宝藏数
Node(){}
Node(int xx,int yy,int ss,int gg):x(xx),y(yy),step(ss),g(gg){}
}; int bfs()
{
int get=;//全局已找到的宝藏数,小于这个数的结点视为“过期”
queue<Node> que;
que.push(Node(sx,sy,,));
cur_step=-;//全局当前的步数
while(!que.empty())
{
Node cur=que.front();
que.pop();
//当此点步数小于等于到达某一个宝藏的步数(即和这个宝藏在搜索树中“同层”),剪枝
if(cur.step<=cur_step&&cur.g<get) continue;
int has=;//这一点的四个可扩展结点中有没有是宝藏的
for(int i=;i<;i++)
{
int nx=cur.x+dx[i];
int ny=cur.y+dy[i];
if(nx<||ny<||nx>n||ny>m) continue;
if(G[nx][ny]=='#') continue;
if(cur.g<get) continue;//宝藏数过期
if(G[nx][ny]=='*')//是宝藏
{
has++;
sx=nx;
sy=ny;
}
}
if(has)
{//一旦四个结点有一个是宝藏,则只将这一个入队,由于没有设vis数组!!!同层其他宝藏会在之后被推入队列的
cur.g++;
get=cur.g;
G[sx][sy]='.';
cur_step=cur.step+;
if(get==k) return cur.step+;
que.push(Node(sx,sy,cur.step+,cur.g));
continue;
}
//当四个结点都不是宝藏时,根据盲目式搜索策略,只好全部推入队列,就在这里推入了很多无用但又无法提前预知的点
for(int i=;i<;i++)
{
int nx=cur.x+dx[i];
int ny=cur.y+dy[i];
if(nx<||ny<||nx>n||ny>m) continue;
if(G[nx][ny]=='#') continue;
if(cur.g<get) continue;
que.push(Node(nx,ny,cur.step+,cur.g));
}
}
if(get<k) return -;
} int main()
{
//freopen("1002.txt","r",stdin);
while((scanf("%d%d",&n,&m)!=EOF)&&(!(n==&&m==)))
{
for(int i=;i<=n;i++)
{
getchar();
for(int j=;j<=m;j++)
{
scanf("%c",&G[i][j]);
if(G[i][j]=='@')
{
sx=i;
sy=j;
}
}
}
scanf("%d",&k);
for(int i=;i<k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x][y]='*';//宝藏标记为*
}
printf("%d\n",bfs());
}
return ;
}

BFS 剪枝 无状压

就在无计可施时,队友建议我改用DFS,但目测会超时或爆栈;而且总觉得原思路是对的,问题在优化上。

这时重新看题,发现我居然忽略了一个条件k<=4~~~~~~~~~~有经验的人大概早就会想到状压了,然而我经验还太少,并是没想到,想到了也写不出来。。。

之后找题解,发现很多是用BFS求出起点和宝藏的最短路,然后再DFS或枚举所有路径。并是没有想通这个思路。

再找,终于发现有和我相同思路的了,感谢原作者~ http://blog.csdn.net/u011932355/article/details/40819317 于是参照这篇把自己的改成了状压版,然后,就得到了内存和时间都少了一个数量级的结果。。。状压大法好~

 #include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAX_N=;
int n,m,k;
int sx,sy,goal;
int dx[]={,,,-},dy[]={,-,,};
int b[]={,,,,};//原作者的写法,这个数组有大用~
char G[MAX_N+][MAX_N+];
int vis[MAX_N+][MAX_N+][];//第三维是状压,表示当前已得宝藏状态 1111~0000
char str[]; struct Node
{
int x,y,step,get;//走到这一点的步数,到这一点的已得宝藏状态
Node(){}
Node(int xx,int yy,int ss,int gg):x(xx),y(yy),step(ss),get(gg){}
}; int bfs()
{
memset(vis,,sizeof(vis));
queue<Node> que;
que.push(Node(sx,sy,,));
vis[sx][sy][]=;
while(!que.empty())
{
Node cur=que.front();
que.pop();
for(int i=;i<;i++)
{
int nx=cur.x+dx[i];
int ny=cur.y+dy[i];
if(nx<||ny<||nx>n||ny>m) continue;
if(G[nx][ny]=='#') continue; Node next(nx,ny,cur.step+,cur.get);
if(G[nx][ny]<=) next.get|=G[nx][ny];//找到一处宝藏,追加到当前宝藏状态
if(vis[nx][ny][next.get]) continue;//同一点同一宝藏状态,只入队一次
vis[nx][ny][next.get]=;
if(next.get==goal) return next.step;//找到全部宝藏,返回
que.push(next);
}
}
return -;
} int main()
{
//freopen("1002.txt","r",stdin);
while(scanf("%d%d",&n,&m)==)
{
if(n==&&m==) break;
for(int i=;i<=n;i++)
{
scanf("%s",str);
int cnt=;
for(int j=;str[j]!='\0';j++)
{
if(str[j]=='#') G[i][cnt++]='#';
else if(str[j]=='.') G[i][cnt++]='.';
else if(str[j]=='@')
{
G[i][cnt++]='@';
sx=i;
sy=cnt-;
}
}
}
scanf("%d",&k);
goal=b[k]-;//通过k和b数组得到目标状态(1111,111,11,1,0之一)
while(k--)
{//按先后顺序,把每个宝藏所在点的状态设为(1,10,100,1000之一)
int x,y;
scanf("%d%d",&x,&y);
G[x][y]=b[k];
}
printf("%d\n",bfs());
}
return ;
}

这个状压是把当前的宝藏访问状态作为vis数组的第三维存入,这样用vis数组对于我来说是第一次,而我的无状压版本大概就是因为没设vis数组,所以本身就增加了很多无用节点的推入,取出后再丢弃就不叫剪枝了。。。因为还是被推入队列了。。。

比赛时一直纠结一道题是我的不对,感谢两位队友的指教。

场下这样的过程还是比较利于学习的,关键是在纠结的过程中暴露了自己哪些基础知识还不清楚,给自己提供了补习的方向。

最新文章

  1. 移动web
  2. uva 1339
  3. .net_ckeditor+ckfinder的图片上传配置
  4. phpcms 01
  5. thinkphp框架 查询语言
  6. HTML5学习(十一)---服务器发送事件
  7. SharePoint Security and Permission System Overview
  8. [Practical Git] Navigate git command pager output with Unix less commands
  9. ASP.NET 常识
  10. python中 __name__及__main()__的使用
  11. Bzoj 2393: Cirno的完美算数教室 容斥原理,深搜
  12. [译]在Asp.Net Core 中使用外部登陆(google、微博...)
  13. Linux常见命令(用户和组_待补充完善)
  14. 玩转FFmpeg的7个小技巧
  15. 各种Handler
  16. python 文件与数据格式化
  17. Python——管道通信
  18. Linux常用命令大全(转)
  19. Eclipse Maven pom.xml 警告No grammar constraints (DTD or XML schema)
  20. js快速排序算法

热门文章

  1. 压缩、解压缩流GZipStream
  2. UNIX网络编程---TCP客户/服务器程序示例(五)
  3. 通过项目逐步深入了解Mybatis&lt;四&gt;
  4. &lt;ListView&gt;分列显示
  5. CSS布局方案之圣杯布局
  6. 解读JavaScript代码 var ie = !-[1,]
  7. strcpy与memcpy的区别
  8. hdu2095 像水题的不错题 异或运算
  9. Node.js 入门教程和学习资源汇总
  10. C#.NET面向对象(语法点)