pku 3083

2009年8月10日

题目链接：PKU 3083 Children of the Candy Corn

分类：DFS+BFS

题目分析与算法原型
         这题难度也不算太大，但是却写了很久，也调了很久，主要就是顺时针和逆时针的DFS的坐标处理，看了Discuss里面有大牛的代码到了8k，心中不免有些胆颤，于是就多花了时间思考如何写的精简一些，然而事实上也用了将近120行左右代码（算不上精简了），呵呵，主要就是DFS那块（BFS基本没问题），对于每次，我用了两个数组，两个方向（一个是当前的另一个是上次的），作为参数来判断下次的坐标，拿逆时针转的来说，对于当前的点若为‘#’则下次铁定向右转（对于当前方向来说），顺时针的情况刚好相反，个人感觉自己的DFS函数还不够简练，相信有更好的记录方法，呵呵

Code:

  1#include<stdio.h>
  2#include<string.h>
  3#define max 45
  4//left,right,ll,rr数组中下标对应的0,1,2,3分别表示当前方向为上，左（右），下，右（左）
  5int left[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
  6int right[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
  7int ll[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
  8int rr[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
  9int step[4][2]={{-1,0},{1,0},{0,-1},{0,1}},n,w,h,beg[2],res1,res2,res3,min,pub;
 10char map[max][max];
 11bool flag[max][max];
 12
 13struct node
 14{
 15    int x,y,step;
 16}queue[max*max];
 17
 18bool check(int x,int y)
 19{
 20    if(x>=0&&x<=h-1&&y>=0&&y<=w-1)return true;
 21    else return false;
 22}
 23//  当前方向  向左或右旋转数组，前进一步,当前方向，上次的方向，当前的坐标
 24void dfs(int d[4][2],int dd[4][2],int now,int last,int pos[2])
 25{
 26    int p[2];
 27    if(map[pos[0]][pos[1]]=='E')
 28    {
 29        pub++;
 30        return ;
 31    }
 32    if(map[pos[0]][pos[1]]=='S'||map[pos[0]][pos[1]]=='.')
 33    {
 34        pub++;
 35        p[0]=pos[0]+d[now][0];
 36        p[1]=pos[1]+d[now][1];
 37        dfs(d,dd,(now+1)%4,now,p);
 38    }
 39    else if(map[pos[0]][pos[1]]=='#'||!check(pos[0],pos[1]))
 40    {
 41        int kk=(now-1+4)%4;
 42        if(now==(last+1)%4)//往左转过来的
 43        {
 44            p[0]=pos[0]-d[last][0]+dd[kk][0];
 45            p[1]=pos[1]-d[last][1]+dd[kk][1];
 46        }
 47        else if(now==(last-1+4)%4)//往右转过来的      
 48        {
 49            p[0]=pos[0]+d[last][0]+dd[kk][0];
 50            p[1]=pos[1]+d[last][1]+dd[kk][1];
 51        }
 52        dfs(d,dd,kk,now,p);
 53    }
 54    return ;
 55}
 56
 57int bfs()
 58{
 59    int i,front=0,rear=1;
 60    queue[0].x=beg[0];
 61    queue[0].y=beg[1];
 62    queue[0].step=1;
 63    flag[beg[0]][beg[1]]=true;
 64    while(front<rear)
 65    {
 66        for(i=0;i<4;i++)
 67        {
 68            int x=queue[front].x,y=queue[front].y;
 69            x+=step[i][0];
 70            y+=step[i][1];
 71            if(!flag[x][y]&&check(x,y)&&map[x][y]!='#')
 72            {
 73                flag[x][y]=true;
 74                queue[rear].x=x;
 75                queue[rear].y=y;
 76                queue[rear].step=queue[front].step+1;
 77                if(map[x][y]=='E')return queue[rear].step; 
 78                rear++;
 79            }
 80        }
 81        front++;
 82    }
 83}
 84int main()
 85{
 86    int i,j,kk;
 87    scanf("%d",&n);
 88    while(n--)
 89    {
 90        scanf("%d%d",&w,&h);
 91        memset(flag,false,sizeof(flag));
 92        min=1;
 93        for(i=0;i<h;i++)
 94            for(j=0;j<w;j++)
 95            {
 96                scanf(" %c",&map[i][j]);
 97                if(map[i][j]=='S')
 98                {
 99                    beg[0]=i;
100                    beg[1]=j;
101                }
102            }
103            if(beg[0]==h-1)kk=0; //上
104            else if(beg[0]==0)kk=1; //下
105            else if(beg[1]==w-1)kk=2;  //左
106            else if(beg[1]==0)kk=3;  //右
107            pub=0;
108            dfs(left,ll,kk,(kk-1+4)%4,beg);
109            res1=pub;
110            pub=0;
111            if(kk==3)kk=1;
112            else if(kk==1)kk=3;
113            dfs(right,rr,kk,(kk-1+4)%4,beg);
114            res2=pub;
115            res3=bfs();
116            printf("%d %d %d\n",res1,res2,res3);
117    }
118    return 1;
119}
120
121

posted on 2009-08-10 18:01 蜗牛也Coding 阅读(322) 评论(0)  编辑 收藏 引用


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


<2009年8月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜