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

            A Za, A Za, Fighting...

            堅信:勤能補拙

            PKU 1475 Pushing Boxes

            問題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=1475

            思路:
            很復(fù)雜的一題,從discuss知道可以采用嵌套的BFS來做,不過始終不知道如何下手
            通過這題,發(fā)現(xiàn)自己對于復(fù)雜問題的coding能力比較弱,不能很好的理清其中的邏輯關(guān)系,需要多多鍛煉

            這題的關(guān)鍵是抓住box的每一次擴展,都對應(yīng)地存在一個person的起始位置,兩者需要同時記錄

            參考:
            http://www.chhaya.me/?p=147

            代碼:
              1 #include<stdio.h>
              2 #include<stdlib.h>
              3 #include<string.h>
              4 #define MAX_LEN 21
              5 /* north, south, east, west */
              6 const int dx[] = {-1100};
              7 const int dy[] = {001-1};
              8 const char dir_box[] = "NSEW";
              9 const char dir_psn[] = "nsew";
             10 int r, c;
             11 int px, py, bx, by, btx, bty;
             12 char map[MAX_LEN][MAX_LEN];
             13 struct EACH {
             14     int x, y;
             15     int id;
             16     int pre;
             17     int dir;
             18 };
             19 struct EACH cur_each, tmp_each, cur_psn, tmp_psn, box_queue[MAX_LEN*MAX_LEN], psn_queue[MAX_LEN*MAX_LEN];
             20 struct {
             21     int x, y;
             22 }persons[MAX_LEN*MAX_LEN];
             23 int visited_box[MAX_LEN][MAX_LEN];
             24 int visited_psn[MAX_LEN][MAX_LEN];
             25 int cnt[MAX_LEN*MAX_LEN];
             26 char seq[MAX_LEN*MAX_LEN][MAX_LEN*MAX_LEN];
             27 
             28 int
             29 is_valid_box(struct EACH item, int dir)
             30 {
             31     int tmpx, tmpy;
             32     if(item.x<0 || item.x>=|| item.y<0 || item.y>=|| map[item.x][item.y]=='#')
             33         return 0;
             34     /* see if there exists a position for person to push */
             35     tmpx = item.x-2*dx[dir];
             36     tmpy = item.y-2*dy[dir];
             37     if(tmpx<0 || tmpx>=|| tmpy<0 || tmpy>=|| map[tmpx][tmpy]=='#')
             38         return 0;
             39     return 1;
             40 }
             41 
             42 int
             43 is_valid_psn(int psnx, int psny, int boxx, int boxy)
             44 {
             45     if(psnx<0 || psnx>=|| psny<0 || psny>=|| map[psnx][psny]=='#')
             46         return 0;
             47     /* path of person can't cover the box */
             48     if(psnx==boxx && psny==boxy)
             49         return 0;
             50     return 1;
             51 }
             52 
             53 int
             54 psn_bfs(int startx, int starty, int endx, int endy, int dir, int index)
             55 {
             56     int i, head, tail;
             57     struct EACH tmp;
             58     memset(visited_psn, 0sizeof(visited_psn));
             59     head = -1;
             60     tail = 0;
             61     psn_queue[tail].x = startx;
             62     psn_queue[tail].y = starty;
             63     psn_queue[tail].pre = -1;
             64     visited_psn[startx][starty] = 1;
             65     while(head < tail) {
             66         ++head;
             67         cur_psn = psn_queue[head];
             68         if(cur_psn.x==endx && cur_psn.y==endy) {
             69             /* record */
             70             /* here 'index' should plus 1, according to box_bfs */
             71             persons[index+1].x = cur_psn.x + dx[dir];
             72             persons[index+1].y = cur_psn.y + dy[dir];
             73             cnt[index+1= 0;
             74             tmp = cur_psn;
             75             while(tmp.pre != -1) {
             76                 seq[index+1][cnt[index+1]++= dir_psn[tmp.dir];
             77                 tmp = psn_queue[tmp.pre];
             78             }
             79             return 1;
             80         }
             81         for(i=0; i<4; i++) {
             82             tmp_psn.x = cur_psn.x + dx[i];
             83             tmp_psn.y = cur_psn.y + dy[i];
             84             if(is_valid_psn(tmp_psn.x, tmp_psn.y, endx+dx[dir], endy+dy[dir]) && !visited_psn[tmp_psn.x][tmp_psn.y]) {
             85                 ++tail;
             86                 tmp_psn.pre = head;
             87                 tmp_psn.dir = i;
             88                 psn_queue[tail] = tmp_psn;
             89                 visited_psn[tmp_psn.x][tmp_psn.y] = 1;
             90             }
             91         }
             92     }
             93     return 0;
             94 }
             95 
             96 void
             97 output(struct EACH *end)
             98 {
             99     int i, index;
            100     if(end->pre == -1)
            101         return;
            102     output(box_queue+(end->pre));
            103     index = end->id;
            104     for(i=cnt[index]-1; i>=0; i--)
            105         printf("%c", seq[index][i]);
            106     printf("%c", dir_box[end->dir]);
            107 }
            108 
            109 void
            110 box_bfs()
            111 {
            112     int i, psn_rt, head, tail;
            113     head = -1;
            114     tail = 0;
            115     memset(visited_box, 0sizeof(visited_box));
            116     box_queue[tail].x = bx;
            117     box_queue[tail].y = by;
            118     box_queue[tail].pre = -1;
            119     box_queue[tail].id = tail;
            120     visited_box[bx][by] = 1;
            121     persons[tail].x = px;
            122     persons[tail].y = py;
            123     while(head < tail) {
            124         ++head;
            125         cur_each = box_queue[head];
            126         if(cur_each.x==btx && cur_each.y==bty) {
            127             /* output */
            128             output(box_queue+head);
            129             return;
            130         }
            131         for(i=0; i<4; i++) {
            132             tmp_each.x = cur_each.x + dx[i];
            133             tmp_each.y = cur_each.y + dy[i];
            134             if(is_valid_box(tmp_each, i) && !visited_box[tmp_each.x][tmp_each.y]) {
            135                 /* bfs for person */
            136                 psn_rt = psn_bfs(persons[head].x, persons[head].y, tmp_each.x-2*dx[i], tmp_each.y-2*dy[i], i, tail);
            137                 if(psn_rt) {
            138                     ++tail;
            139                     tmp_each.dir = i;
            140                     tmp_each.pre = head;
            141                     tmp_each.id = tail;
            142                     box_queue[tail] = tmp_each;
            143                     visited_box[tmp_each.x][tmp_each.y] = 1;
            144                 }
            145             }
            146         }
            147     }
            148     printf("Impossible.");
            149 }
            150 
            151 int
            152 main(int argc, char **argv)
            153 {
            154     int i, j, tests = 0;
            155     while(scanf("%d %d"&r, &c) != EOF) {
            156         if(r==0 && c==0)
            157             break;
            158         for(i=0; i<r; i++) {
            159             scanf("%s", map[i]);
            160             for(j=0; j<c; j++) {
            161                 if(map[i][j] == 'S') {
            162                     px = i;
            163                     py = j;
            164                 } else if(map[i][j] == 'B') {
            165                     bx = i;
            166                     by = j;
            167                 } else if(map[i][j] == 'T') {
            168                     btx = i;
            169                     bty = j;
            170                 }
            171             }
            172         }
            173         printf("Maze #%d\n"++tests);
            174         /* bfs */
            175         box_bfs();
            176         printf("\n\n");
            177     }
            178 }

            posted on 2010-08-05 12:14 simplyzhao 閱讀(269) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導(dǎo)航

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久成人国产精品| 亚洲狠狠婷婷综合久久蜜芽| 欧美熟妇另类久久久久久不卡 | 久久福利片| 精品久久久中文字幕人妻| 久久亚洲精品成人AV| 国产成人无码精品久久久免费| 一本久久综合亚洲鲁鲁五月天| 久久国产精品无码一区二区三区| 99久久国产综合精品五月天喷水| 国产精品99久久久精品无码| 欧美亚洲另类久久综合婷婷| 久久精品国产一区| 精品久久久久久久无码| 日日噜噜夜夜狠狠久久丁香五月| 国产农村妇女毛片精品久久| 久久精品亚洲精品国产色婷 | 热久久视久久精品18| 久久se这里只有精品| 国产精品18久久久久久vr| 人人狠狠综合久久亚洲88| 久久久久亚洲AV成人片| 久久国产成人午夜AV影院| 国产精品女同久久久久电影院| 久久精品无码一区二区三区日韩| 99久久精品免费观看国产| 久久精品国产清高在天天线| 中文字幕久久波多野结衣av| 久久亚洲精品无码VA大香大香| 一本色综合久久| 色8激情欧美成人久久综合电| 狠狠色综合网站久久久久久久| a高清免费毛片久久| 四虎国产精品免费久久久| 国产精品久久久久久一区二区三区 | 久久久久久久久波多野高潮| 日本欧美国产精品第一页久久| 久久亚洲天堂| 欧美一区二区三区久久综合| 人妻无码久久一区二区三区免费| 久久中文骚妇内射|