• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			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 閱讀(329) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年8月>
            
	
            日一二三四五六
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



97久久国产亚洲精品超碰热|
香蕉久久永久视频|
国产精品久久波多野结衣|
久久精品成人免费网站|
久久精品成人免费国产片小草|
亚洲精品高清一二区久久|
一本一本久久A久久综合精品|
久久久青草久久久青草|
久久久这里有精品|
精品久久久久久无码中文野结衣|
久久久久亚洲精品日久生情|
国产69精品久久久久9999APGF|
久久亚洲精品国产精品|
国产一区二区精品久久凹凸|
亚洲中文字幕伊人久久无码|
欧美伊香蕉久久综合类网站|
久久亚洲中文字幕精品一区|
国产三级精品久久|
久久精品国产亚洲AV电影|
色老头网站久久网|
国产高清国内精品福利99久久|
人妻精品久久无码区|
香港aa三级久久三级老师2021国产三级精品三级在
|
久久性生大片免费观看性|
欧美大香线蕉线伊人久久|
久久久久久国产a免费观看黄色大片|
好属妞这里只有精品久久|
亚洲国产精品成人久久|
久久精品久久久久观看99水蜜桃|
四虎影视久久久免费|
精品久久久无码中文字幕|
国产亚洲精午夜久久久久久|
久久亚洲欧美日本精品|
久久99精品综合国产首页|
91久久精一区二区三区大全|
久久青青草原亚洲av无码app|
久久久久亚洲AV成人网人人网站
|
亚洲国产精品无码久久SM|
欧美日韩精品久久久久|
精品人妻伦九区久久AAA片69|
一本色综合久久|