【HDU 4771 Stealing Harry Potter's Precious】BFS+状压

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

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

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

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

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

【HDU 4771 Stealing Harry Potter's Precious】BFS+状压

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

【HDU 4771 Stealing Harry Potter's Precious】BFS+状压【HDU 4771 Stealing Harry Potter's Precious】BFS+状压
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 const int MAX_N=100;
 6 int n,m,k;
 7 int sx,sy;
 8 int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
 9 char G[MAX_N+2][MAX_N+2];
10 int cur_step;
11 
12 struct Node
13 {
14     int x,y,step,g;//每个点的坐标、走到这里的步数、到这一点已找到的宝藏数
15     Node(){}
16     Node(int xx,int yy,int ss,int gg):x(xx),y(yy),step(ss),g(gg){}
17 };
18 
19 int bfs()
20 {
21     int get=0;//全局已找到的宝藏数,小于这个数的结点视为“过期”
22     queue<Node> que;
23     que.push(Node(sx,sy,0,0));
24     cur_step=-1;//全局当前的步数
25     while(!que.empty())
26     {
27         Node cur=que.front();
28         que.pop();
29         //当此点步数小于等于到达某一个宝藏的步数(即和这个宝藏在搜索树中“同层”),剪枝
30         if(cur.step<=cur_step&&cur.g<get) continue;
31         int has=0;//这一点的四个可扩展结点中有没有是宝藏的
32         for(int i=0;i<4;i++)
33         {
34             int nx=cur.x+dx[i];
35             int ny=cur.y+dy[i];
36             if(nx<1||ny<1||nx>n||ny>m) continue;
37             if(G[nx][ny]=='#') continue;
38             if(cur.g<get) continue;//宝藏数过期
39             if(G[nx][ny]=='*')//是宝藏
40             {
41                 has++;
42                 sx=nx;
43                 sy=ny;
44             }
45         }
46         if(has)
47         {//一旦四个结点有一个是宝藏,则只将这一个入队,由于没有设vis数组!!!同层其他宝藏会在之后被推入队列的
48             cur.g++;
49             get=cur.g;
50             G[sx][sy]='.';
51             cur_step=cur.step+1;
52             if(get==k) return cur.step+1;
53             que.push(Node(sx,sy,cur.step+1,cur.g));
54             continue;
55         }
56         //当四个结点都不是宝藏时,根据盲目式搜索策略,只好全部推入队列,就在这里推入了很多无用但又无法提前预知的点
57         for(int i=0;i<4;i++)
58         {
59             int nx=cur.x+dx[i];
60             int ny=cur.y+dy[i];
61             if(nx<1||ny<1||nx>n||ny>m) continue;
62             if(G[nx][ny]=='#') continue;
63             if(cur.g<get) continue;
64             que.push(Node(nx,ny,cur.step+1,cur.g));
65         }
66     }
67     if(get<k) return -1;
68 }
69 
70 int main()
71 {
72     //freopen("1002.txt","r",stdin);
73     while((scanf("%d%d",&n,&m)!=EOF)&&(!(n==0&&m==0)))
74     {
75         for(int i=1;i<=n;i++)
76         {
77             getchar();
78             for(int j=1;j<=m;j++)
79             {
80                 scanf("%c",&G[i][j]);
81                 if(G[i][j]=='@')
82                 {
83                     sx=i;
84                     sy=j;
85                 }
86             }
87         }
88         scanf("%d",&k);
89         for(int i=0;i<k;i++)
90         {
91             int x,y;
92             scanf("%d%d",&x,&y);
93             G[x][y]='*';//宝藏标记为*
94         }
95         printf("%d\n",bfs());
96     }
97     return 0;
98 }
BFS 剪枝 无状压

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

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

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

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

【HDU 4771 Stealing Harry Potter&#39;s Precious】BFS+状压

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 const int MAX_N=100;
 6 int n,m,k;
 7 int sx,sy,goal;
 8 int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
 9 int b[]={1,2,4,8,16};//原作者的写法,这个数组有大用~
10 char G[MAX_N+2][MAX_N+2];
11 int vis[MAX_N+2][MAX_N+2][20];//第三维是状压,表示当前已得宝藏状态 1111~0000
12 char str[105];
13 
14 struct Node
15 {
16     int x,y,step,get;//走到这一点的步数,到这一点的已得宝藏状态
17     Node(){}
18     Node(int xx,int yy,int ss,int gg):x(xx),y(yy),step(ss),get(gg){}
19 };
20 
21 int bfs()
22 {
23     memset(vis,0,sizeof(vis));
24     queue<Node> que;
25     que.push(Node(sx,sy,0,0));
26     vis[sx][sy][0]=1;
27     while(!que.empty())
28     {
29         Node cur=que.front();
30         que.pop();
31         for(int i=0;i<4;i++)
32         {
33             int nx=cur.x+dx[i];
34             int ny=cur.y+dy[i];
35             if(nx<1||ny<1||nx>n||ny>m) continue;
36             if(G[nx][ny]=='#') continue;
37 
38             Node next(nx,ny,cur.step+1,cur.get);
39             if(G[nx][ny]<=8) next.get|=G[nx][ny];//找到一处宝藏,追加到当前宝藏状态
40             if(vis[nx][ny][next.get]) continue;//同一点同一宝藏状态,只入队一次
41             vis[nx][ny][next.get]=1;
42             if(next.get==goal) return next.step;//找到全部宝藏,返回
43             que.push(next);
44         }
45     }
46     return -1;
47 }
48 
49 int main()
50 {
51     //freopen("1002.txt","r",stdin);
52     while(scanf("%d%d",&n,&m)==2)
53     {
54         if(n==0&&m==0) break;
55         for(int i=1;i<=n;i++)
56         {
57             scanf("%s",str);
58             int cnt=1;
59             for(int j=0;str[j]!='\0';j++)
60             {
61                 if(str[j]=='#') G[i][cnt++]='#';
62                 else if(str[j]=='.') G[i][cnt++]='.';
63                 else if(str[j]=='@')
64                 {
65                     G[i][cnt++]='@';
66                     sx=i;
67                     sy=cnt-1;
68                 }
69             }
70         }
71         scanf("%d",&k);
72         goal=b[k]-1;//通过k和b数组得到目标状态(1111,111,11,1,0之一)
73         while(k--)
74         {//按先后顺序,把每个宝藏所在点的状态设为(1,10,100,1000之一)
75             int x,y;
76             scanf("%d%d",&x,&y);
77             G[x][y]=b[k];
78         }
79         printf("%d\n",bfs());
80     }
81     return 0;
82 }

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

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

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

上一篇:一个安卓编译器「Bug」引发的血案:调试时method中return语句不能断点问题排查


下一篇:【POJ 3669 Meteor Shower】简单BFS