• <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

            題目分析與算法原型
                     這題難度也不算太大，但是卻寫了很久，也調(diào)了很久，主要就是順時針和逆時針的DFS的坐標(biāo)處理，看了Discuss里面有大牛的代碼到了8k，心中不免有些膽顫，于是就多花了時間思考如何寫的精簡一些，然而事實上也用了將近120行左右代碼（算不上精簡了），呵呵，主要就是DFS那塊（BFS基本沒問題），對于每次，我用了兩個數(shù)組，兩個方向（一個是當(dāng)前的另一個是上次的），作為參數(shù)來判斷下次的坐標(biāo)，拿逆時針轉(zhuǎn)的來說，對于當(dāng)前的點若為‘#’則下次鐵定向右轉(zhuǎn)（對于當(dāng)前方向來說），順時針的情況剛好相反，個人感覺自己的DFS函數(shù)還不夠簡練，相信有更好的記錄方法，呵呵

            Code:

              1            #include<stdio.h>
              2#include<string.h>
              3#define max 45
              4//left,right,ll,rr數(shù)組中下標(biāo)對應(yīng)的0,1,2,3分別表示當(dāng)前方向為上，左（右），下，右（左）
              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//  當(dāng)前方向  向左或右旋轉(zhuǎn)數(shù)組，前進(jìn)一步,當(dāng)前方向，上次的方向，當(dāng)前的坐標(biāo)
             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)//往左轉(zhuǎn)過來的
             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)//往右轉(zhuǎn)過來的      
             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 閱讀(325) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年10月>
            
	
            日一二三四五六
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456
            

            

					

            導(dǎo)航
            

					

            統(tǒng)計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



国产精品美女久久久久久2018|
久久亚洲av无码精品浪潮|
精品国产一区二区三区久久|
久久久久久国产a免费观看不卡|
久久无码AV中文出轨人妻|
久久国产亚洲高清观看|
久久亚洲2019中文字幕|
久久久综合九色合综国产|
精品多毛少妇人妻AV免费久久
|
久久福利资源国产精品999|
激情伊人五月天久久综合|
亚洲国产天堂久久综合|
91久久精品视频|
a高清免费毛片久久|
漂亮人妻被中出中文字幕久久|
99久久夜色精品国产网站|
久久影院综合精品|
人妻无码αv中文字幕久久琪琪布|
色成年激情久久综合|
国产精品久久久久9999高清|
亚洲午夜久久久久久久久久|
亚洲七七久久精品中文国产|
国产午夜福利精品久久|
AV狠狠色丁香婷婷综合久久
|
av国内精品久久久久影院|
久久国产免费直播|
香蕉久久夜色精品国产尤物|
国产精品热久久无码av|
久久婷婷国产麻豆91天堂|
国产精品18久久久久久vr
|
久久青青国产|
久久久久噜噜噜亚洲熟女综合|
 久久综合狠狠综合久久激情 |
久久精品国产免费一区|
狠狠色丁香婷综合久久|
色偷偷888欧美精品久久久|
久久99热精品|
99久久99久久精品国产片果冻|
国产精品热久久无码av|
青青青青久久精品国产h久久精品五福影院1421
|
狠狠久久综合伊人不卡|