青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            午夜精品福利电影| 另类亚洲自拍| 久久视频一区二区| 久久爱www.| 久久久午夜电影| 麻豆久久久9性大片| 免费观看在线综合色| 欧美 日韩 国产精品免费观看| 久久欧美中文字幕| 欧美 亚欧 日韩视频在线| 亚洲福利小视频| 欧美大片免费观看在线观看网站推荐| 欧美激情一区二区三级高清视频 | 91久久精品国产91久久| 亚洲欧洲精品成人久久奇米网| av72成人在线| 午夜久久tv| 欧美高清视频一区| 亚洲无线视频| 欧美~级网站不卡| 国产精品九九久久久久久久| 国产中文一区二区| 99天天综合性| 老司机成人网| 亚洲视频在线视频| 免费不卡在线视频| 国产精品资源| 夜夜嗨av一区二区三区网站四季av| 香蕉乱码成人久久天堂爱免费| 欧美h视频在线| 亚洲一区二区视频在线| 久久综合九色综合网站| 国产精品免费小视频| 亚洲国产日韩欧美在线99| 午夜亚洲性色福利视频| 欧美大片专区| 久久不见久久见免费视频1| 欧美日韩国内| 亚洲国产欧美一区二区三区同亚洲| 亚洲欧洲99久久| 亚洲欧洲日本一区二区三区| 欧美影院视频| 国产欧美一区二区在线观看| 亚洲色图综合久久| 91久久精品国产91性色tv| 久久er精品视频| 国产亚洲欧美一级| 欧美亚洲在线播放| 亚洲视频综合| 国产精品成人播放| 一本色道久久综合亚洲精品小说 | 欧美成人国产一区二区| 亚洲精品美女在线观看播放| 久久精品九九| 国产亚洲网站| 久久国产精品久久国产精品| 一区二区三区四区在线| 欧美日韩久久| 国产精品99久久99久久久二8 | 亚洲午夜免费视频| 亚洲欧洲在线播放| 欧美日韩www| 亚洲少妇自拍| 亚洲特级片在线| 国产精品日本欧美一区二区三区| 亚洲图色在线| 亚洲日本欧美天堂| 欧美日韩国产在线| 亚洲一区二区三区精品动漫| 日韩亚洲视频在线| 国产精品久久久久久久9999| 午夜精品国产更新| 欧美一区二区三区免费看| 国产欧美精品| 老鸭窝毛片一区二区三区| 久久裸体艺术| 亚洲日本aⅴ片在线观看香蕉| 亚洲国产日韩一级| 欧美日韩在线直播| 欧美在线免费| 麻豆精品91| 一区二区三区免费看| 亚洲一级二级| 亚洲高清av| 99国产精品国产精品久久| 国产精品女人久久久久久| 久久婷婷综合激情| 欧美精品123区| 欧美一区二区成人6969| 久久久777| 夜夜嗨av色一区二区不卡| 亚洲小说欧美另类婷婷| 狠狠狠色丁香婷婷综合激情| 亚洲高清免费在线| 国产精品色网| 亚洲国产成人不卡| 国产免费成人| 亚洲欧洲综合另类在线| 国产精品一区二区视频| 免费一级欧美片在线播放| 欧美视频你懂的| 麻豆成人综合网| 国产精品日韩一区二区| 亚洲大片精品永久免费| 国产欧美一区二区三区视频| 亚洲精品一二| 影音先锋一区| 亚洲欧美精品在线观看| 亚洲毛片网站| 国产精品久久久久久一区二区三区| 亚洲国产日本| 亚洲一区日韩在线| 亚洲美女在线国产| 久久国产精彩视频| 亚洲中无吗在线| 欧美a级片网站| 久久嫩草精品久久久精品一| 欧美性大战xxxxx久久久| 欧美激情在线狂野欧美精品| 国产日韩精品一区二区三区| 亚洲精品一区二区三区婷婷月| 很黄很黄激情成人| 午夜日韩激情| 亚洲欧美日韩专区| 欧美日韩视频专区在线播放 | 亚洲欧美激情视频在线观看一区二区三区| 欧美一级片在线播放| 亚洲视频免费看| 欧美精品一区二区三区四区| 鲁鲁狠狠狠7777一区二区| 国产精品久久久久久av福利软件| 最新亚洲激情| 亚洲免费观看高清在线观看 | 亚洲在线1234| 欧美丝袜一区二区| 亚洲人成人一区二区在线观看| 1024日韩| 久久综合色天天久久综合图片| 久久理论片午夜琪琪电影网| 国产欧美日韩另类视频免费观看| 亚洲视频电影在线| 午夜在线观看免费一区| 国产精品综合av一区二区国产馆| 亚洲午夜免费视频| 性欧美video另类hd性玩具| 国产精品欧美经典| 亚洲欧美日韩视频一区| 久久黄色级2电影| 韩国一区电影| 六月天综合网| 一本久道久久综合狠狠爱| 亚洲欧美日韩国产另类专区| 国产精品亚洲片夜色在线| 羞羞答答国产精品www一本| 久久精品72免费观看| 好看的日韩av电影| 久久久蜜桃一区二区人| 亚洲东热激情| 亚洲一区二区三区色| 国产区欧美区日韩区| 久久久综合香蕉尹人综合网| 亚洲国产岛国毛片在线| 亚洲欧美激情一区| 加勒比av一区二区| 欧美理论在线播放| 欧美一区二区在线视频| 欧美国产专区| 亚洲欧美资源在线| 一区在线观看视频| 亚洲成色777777女色窝| 久久国产一区二区| 嫩草影视亚洲| 中国日韩欧美久久久久久久久| 国产精品v一区二区三区| 亚洲精品极品| 欧美在线免费一级片| 在线观看亚洲精品| 欧美日韩一区二区免费在线观看| 亚洲永久精品国产| 另类图片综合电影| 亚洲自拍电影| 亚洲精品乱码久久久久久蜜桃麻豆 | 国产精品黄色在线观看| 久久精品五月| 亚洲另类在线视频| 久久伊人精品天天| 中文在线资源观看视频网站免费不卡| 午夜视频在线观看一区二区| 久久亚洲精品网站| 亚洲在线视频观看| 极品av少妇一区二区| 欧美日韩亚洲另类| 欧美电影电视剧在线观看| 亚洲在线观看免费| 亚洲精品国产精品国产自| 久久久欧美精品sm网站| 亚洲欧美激情四射在线日| 一本色道久久综合狠狠躁篇怎么玩| 国产一区二区激情| 欧美午夜欧美|