首页 > 搜索 > BFS搜索 > hdu 2128 Tempter of the Bone II-BFS-[解题报告]C++
2013
12-29

hdu 2128 Tempter of the Bone II-BFS-[解题报告]C++

Tempter of the Bone II

问题描述 :

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze was changed and the way he came in was lost.He realized that the bone was a trap, and he tried desperately to get out of this maze.

The maze was a rectangle with the sizes of N by M. The maze is made up of a door,many walls and many explosives. Doggie need to reach the door to escape from the tempter. In every second, he could move one block to one of the upper, lower, left or right neighboring blocks. And if the destination is a wall, Doggie need another second explode and a explosive to explode it if he had some explosives. Once he entered a block with explosives,he can take away all of the explosives. Can the poor doggie survive? Please help him.

输入:

The input consists of multiple test cases. The first line of each test case contains two integers N, M,(2 <= N, M <= 8). which denote the sizes of the maze.The next N lines give the maze layout, with each line containing M characters. A character is one of the following:

‘X’: a block of wall;
‘S’: the start point of the doggie;
‘D’: the Door;
‘.’: an empty block;
’1′–’9′:explosives in that block.

Note,initially he had no explosives.

The input is terminated with two 0′s. This test case is not to be processed.

输出:

The input consists of multiple test cases. The first line of each test case contains two integers N, M,(2 <= N, M <= 8). which denote the sizes of the maze.The next N lines give the maze layout, with each line containing M characters. A character is one of the following:

‘X’: a block of wall;
‘S’: the start point of the doggie;
‘D’: the Door;
‘.’: an empty block;
’1′–’9′:explosives in that block.

Note,initially he had no explosives.

The input is terminated with two 0′s. This test case is not to be processed.

样例输入:

4 4
SX..
XX..
....
1..D
4 4
S.X1
....
..XX
..XD
0 0

样例输出:

-1
9

题目链接 :http://acm.hdu.edu.cn/showproblem.php?pid=2128

思路:这题判重比较麻烦,我是这样做的:每个状态记录炸弹数目以及爆破点的坐标映射,还要有一个访问数组来标记已经取过的炸弹的位置(下次经过就不能再取了),由于要求时间最短,可以考虑优先队列。

#include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<queue>
 using namespace std;
 struct Node {
     int x,y,time;
     bool operator < (const Node &p) const {
         return p.time<time;
     }
     int key;//炸药
     int count;//所有爆破位置的坐标的映射(有点瞎搞的味道,hd数据弱,应该也会有冲突的吧)
     bool visited[9][9];//记录每个状态爆破的位置,有可能重复走
 } st;
 char map[9][9];
 bool mark[9][9][66][2222];//标记
 int n,m;
 int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
 int ex,ey;
 
 bool bfs() {
     memset(mark,false,sizeof(mark));
     mark[st.x][st.y][st.key][st.count]=true;
     Node p,q;
     priority_queue<Node>Q;
     Q.push(st);
     while(!Q.empty()) {
         p=Q.top();
         Q.pop();
         if(p.x==ex&&p.y==ey) {
             printf("%d\n",p.time);
             return true;
         }
         for(int i=0; i<4; i++) {
             q=p;
             q.x=p.x+dir[i][0];
             q.y=p.y+dir[i][1];
             q.time=p.time+1;
             if(q.x<1||q.x>n||q.y<1||q.y>m)continue;
             if(map[q.x][q.y]=='.') {
                 if(!mark[q.x][q.y][q.key][q.count]) {
                     mark[q.x][q.y][q.key][q.count]=true;
                     Q.push(q);
                 }
             } else if(map[q.x][q.y]=='X') {
                 if(!q.visited[q.x][q.y]) {
                     if(q.key>0) {
                         q.key--,q.count+=(q.x*q.y+8*(q.x+q.y));
                         q.time++;
                         q.visited[q.x][q.y]=true;
                         if(!mark[q.x][q.y][q.key][q.count]) {
                             mark[q.x][q.y][q.key][q.count]=true;
                             Q.push(q);
                         }
                     }
                 } else if(!mark[q.x][q.y][q.key][q.count]) {
                     mark[q.x][q.y][q.key][q.count]=true;
                     Q.push(q);
                 }
             } else {
                 if(!q.visited[q.x][q.y]) {
                     q.visited[q.x][q.y]=true;
                     q.key+=map[q.x][q.y]-'0';
                 }
                 if(!mark[q.x][q.y][q.key][q.count]) {
                     mark[q.x][q.y][q.key][q.count]=true;
                     Q.push(q);
                 }
             }
         }
     }
     return false;
 }
 
 
 int main() {
  //  freopen("1.txt","r",stdin);
     while(scanf("%d%d",&n,&m),(n+m)) {
         for(int i=1; i<=n; i++) {
             scanf("%s",map[i]+1);
             for(int j=1; j<=m; j++) {
                 if(map[i][j]=='S') {
                     map[i][j]='.';
                     st.x=i;
                     st.y=j;
                     st.time=st.key=st.count=0;
                     memset(st.visited,false,sizeof(st.visited));
                     st.visited[st.x][st.y]=true;
                 } else if(map[i][j]=='D') {
                     map[i][j]='.';
                     ex=i,ey=j;
                 }
             }
         }
         if(!bfs())puts("-1");
     }
     return 0;
 }

 

解题转自:http://www.cnblogs.com/wally/archive/2013/06/05/3118717.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测