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


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年7月>
            
	
            日一二三四五六
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



99久久无码一区人妻a黑|
久久久久久人妻无码|
国产精品一区二区久久精品涩爱|
欧美色综合久久久久久|
一本色道久久综合狠狠躁|
91久久婷婷国产综合精品青草|
久久久久久久99精品免费观看|
国产精品99久久不卡|
亚洲精品乱码久久久久久蜜桃图片|
亚洲国产精品一区二区久久|
亚洲精品第一综合99久久|
7国产欧美日韩综合天堂中文久久久久
|
久久综合国产乱子伦精品免费|
一本久久a久久精品综合夜夜|
久久婷婷五月综合国产尤物app|
久久青青草原综合伊人|
无码久久精品国产亚洲Av影片|
久久se这里只有精品|
2020最新久久久视精品爱|
亚洲国产精品18久久久久久|
久久人人超碰精品CAOPOREN|
久久被窝电影亚洲爽爽爽|
浪潮AV色综合久久天堂|
久久成人小视频|
亚洲国产成人久久综合碰|
久久se精品一区二区影院|
久久国产精品一区二区|
久久久久亚洲精品无码蜜桃|
亚洲色婷婷综合久久|
伊人久久大香线蕉综合5g|
一级女性全黄久久生活片免费|
久久久久九九精品影院|
精品久久久久久无码人妻热|
99久久精品国产一区二区|
91久久香蕉国产熟女线看|
91麻精品国产91久久久久|
精品国产综合区久久久久久|
超级碰久久免费公开视频|
久久国产热这里只有精品|
免费精品久久久久久中文字幕|
久久久久久国产a免费观看黄色大片
|