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


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年2月>
            
	
            日一二三四五六
            31123456
            78910111213
            14151617181920
            21222324252627
            28123456
            78910111213
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久久久久久综合狠狠综合|
久久久久久av无码免费看大片|
久久国产精品偷99|
国产成人无码久久久精品一|
色欲久久久天天天综合网|
一极黄色视频久久网站|
色欲综合久久躁天天躁|
人妻系列无码专区久久五月天|
激情久久久久久久久久|
久久91精品综合国产首页|
国产成人综合久久精品尤物|
国产99久久九九精品无码|
精品熟女少妇aⅴ免费久久|
99久久精品免费|
久久久久久av无码免费看大片|
欧美亚洲另类久久综合婷婷
|
久久精品黄AA片一区二区三区|
久久久久久精品免费看SSS|
午夜人妻久久久久久久久|
久久精品无码专区免费青青|
国内精品久久九九国产精品|
日本三级久久网|
思思久久99热免费精品6|
国产精品成人久久久|
午夜天堂精品久久久久|
99久久国产热无码精品免费久久久久|
99久久精品免费国产大片|
中文字幕精品无码久久久久久3D日动漫|
久久亚洲AV无码精品色午夜|
婷婷久久香蕉五月综合加勒比|
久久精品国产99国产精偷|
免费一级欧美大片久久网|
亚洲色欲久久久综合网东京热|
精品无码久久久久久午夜|
青青草原综合久久大伊人导航|
色婷婷久久综合中文久久蜜桃av|
99精品久久久久久久婷婷|
久久久久波多野结衣高潮|
91久久精品视频|
久久精品aⅴ无码中文字字幕不卡
久久精品aⅴ无码中文字字幕重口
|
精品久久久久久无码专区|