• <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)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年6月>
            
	
            日一二三四五六
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久久久国色AV免费看图片|
日本人妻丰满熟妇久久久久久|
久久精品水蜜桃av综合天堂|
国产午夜精品久久久久九九电影|
久久国产精品国产自线拍免费|
一本大道久久香蕉成人网|
性做久久久久久久久久久|
亚洲色欲久久久综合网|
久久精品欧美日韩精品|
日本精品久久久中文字幕|
久久久精品国产亚洲成人满18免费网站
|
伊人久久一区二区三区无码|
久久青青色综合|
久久久久久久97|
成人a毛片久久免费播放|
久久精品亚洲福利|
亚洲伊人久久成综合人影院
|
少妇内射兰兰久久|
久久久噜噜噜久久熟女AA片|
欧美一区二区三区久久综|
97久久精品人人做人人爽|
久久亚洲电影|
久久久精品午夜免费不卡|
久久亚洲天堂|
99久久精品费精品国产一区二区|
久久亚洲精品无码观看不卡|
一本久久知道综合久久|
日本久久久久久中文字幕|
亚洲一级Av无码毛片久久精品|
成人久久精品一区二区三区|
久久人做人爽一区二区三区|
99久久这里只精品国产免费|
日本亚洲色大成网站WWW久久|
麻豆精品久久久一区二区|
国内精品久久久久久久97牛牛|
亚洲熟妇无码另类久久久|
精品久久人人爽天天玩人人妻|
久久亚洲AV无码西西人体|
欧美性大战久久久久久|
久久天天躁狠狠躁夜夜2020老熟妇
|
久久婷婷五月综合色奶水99啪|