POJ 3984 方法一【BFS+Stack 记录路径】

刚学搜索,总是不开窍,看了介绍,自己磨了两小时才写出来。后面会有DFS和改进后的方法。想通过这道水题,把搜索入了门先。
蓝桥大赛还有几天,再看看,自己水死了。
自己的代码:  1 #include<iostream>
  2 #include<queue>
  3 #include<stack>
  4 using namespace std;
  5 //===================================================================
  6 int maze[5][5];
  7 bool mark[5][5];
  8 struct Point 
  9 {
 10     int x,y;
 11 };
 12 
 13 int dir[4][2]={0,1,0,-1,1,0,-1,0};
 14 Point dis[5][5];
 15 stack<Point> S;
 16 int map[5][5];
 17 //=====================================================================
 18 
 19 bool InMap(int i,int j)
 20 {
 21     if(i>=0&& i<=4 && j>=0 && j<=4) return true;
 22     else return  false;
 23 }
 24 
 25 void func(int i, int j)
 26 {
 27     if(i==0 && j==0)
 28     {
 29          printf("(0, 0)\n");
 30          return ;
 31     }
 32     Point t;
 33     t.x=i;
 34     t.y=j;
 35     S.push(t);
 36     func(dis[i][j].x,dis[i][j].y);    //递归放入栈,不知道怎么倒序输出
 37 
 38 }
 39 
 40 void BFS()
 41 {
 42     queue<Point> Q;
 43 
 44     Point cur,m,q;
 45     cur.x=0;
 46     cur.y=0;
 47     mark[0][0]=1;
 48     Q.push(cur);
 49     dis[0][0].x=0;
 50     dis[0][0].y=0;
 51     int xt,yt;
 52 
 53     while(!Q.empty())
 54     {
 55         m=Q.front();
 56         Q.pop();
 57 
 58         for(int i=0;i<4;i++)
 59         {
 60             xt=m.x+dir[i][0];
 61             yt=m.y+dir[i][1];
 62             if(xt==4 && yt==4) 
 63             {
 64                 func(m.x,m.y);//放入栈
 65                 return ;
 66             }
 67             if(InMap(xt,yt) && mark[xt][yt]==0 && maze[xt][yt]==0)//判断下面一层的结点是否符合
 68             {
 69 
 70                 dis[xt][yt].x=m.x;//记录每上次的结点,这样才可以把整个拎起来
 71                 dis[xt][yt].y=m.y;//用dis[][]点来记录每个节点的父节点,因为遍历过就会mark=1,所以只会有一个父节,不会被覆盖
 72                 mark[xt][yt]=1;//访问过后
 73                 q.x=xt;
 74                 q.y=yt;
 75                 Q.push(q);
 76 
 77             }
 78         }
 79     }
 80 }
 81 
 82 int main()
 83 {
 84     int i,j;
 85 
 86     //freopen("in.txt","r",stdin);
 87     for(i=0;i<5;i++)
 88         for(j=0;j<5;j++)
 89             scanf("%d",&maze[i][j]);
 90 
 91     BFS();
 92 
 93     while(!S.empty())//打印路径
 94     {
 95         printf("(%d, %d)\n",S.top().x,S.top().y);
 96         S.pop();
 97     }
 98     printf("(4, 4)\n");
 99 
100 
101 
102 
103 
104 
105 }

posted on 2012-05-14 23:02 四也 阅读(580) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜