• <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>
            posts - 14,  comments - 11,  trackbacks - 0
                  bfs的好題目!
                  開始想到用優(yōu)先隊(duì)列,無情的還是過了, 只不過時間用了2000ms多,差點(diǎn)就掛了~杯具的優(yōu)先
                  后來一想,其實(shí)可以直接bfs, 有情的是意料之外的沒有出現(xiàn)TE,而是AC,徹底無語的是只用了500ms多!!!!
                  大呼優(yōu)先之哀哉……
                  至于bfs的做法如下:
                        1,開始點(diǎn)進(jìn)棧
                        2,開始點(diǎn)能直接到達(dá)(不花時間的)的所有的點(diǎn)進(jìn)棧
                        3,分兩步
                           3.1 開始點(diǎn)不能直接到達(dá)(要時間)的點(diǎn)進(jìn)棧
                           3.2 將這個點(diǎn)能直接到達(dá)(不花時間的)的所有的點(diǎn)進(jìn)棧
                           3.3 跳轉(zhuǎn)到3
                       4 跳轉(zhuǎn)到1
                     注:開始點(diǎn)為當(dāng)前出棧的第一個點(diǎn)
                    不明白這個過程的可以看代碼(雖然代碼有點(diǎn)……,還可以進(jìn)一步簡化, 以后不能老想著優(yōu)先了,誰優(yōu)先誰杯具,當(dāng)然不是說我們的廣大女同胞……)
              1 #include <iostream>
              2 #include <queue>
              3 using namespace std;
              4 struct node
              5 {
              6        int x, y, time;
              7        /*friend bool operator < (node a, node b)
              8        {
              9               return a.time > b.time;
             10        }*/
             11 };
             12 int n, m;
             13 int xi[8= {-1-101110-1};
             14 int yi[8= {01110-1-1-1};
             15 char map[1005][1005];
             16 bool vist[1005][1005];
             17 bool check(int dx, int dy)
             18 {
             19      if (dx >= 0 && dy >=0 && dx < n && dy < m) return true;
             20      return false;
             21 }
             22 queue <node> q;
             23 int bfs(node now, node end)
             24 {
             25     while (!q.empty())q.pop();
             26     now.time = 0;
             27     q.push(now);
             28     
             29     for (int i = 0; i < n; i++)
             30     for (int j = 0; j < m; j++)
             31         vist[i][j] = false;
             32     vist[now.x][now.y] = true;
             33     node next, tmp;
             34     bool flag = false;
             35     while (!q.empty())
             36     {
             37           now = q.front();
             38           tmp = now;
             39           if (now.x == end.x && now.y == end.y) return now.time;
             40           q.pop();
             41           flag = false;
             42           while (1)
             43           {
             44                 next.x = tmp.x + xi[map[tmp.x][tmp.y]-'0'];
             45                 next.y = tmp.y + yi[map[tmp.x][tmp.y]-'0'];
             46                 if (check(next.x, next.y) && !vist[next.x][next.y])
             47                 {
             48                    if (next.x == end.x && next.y == end.y) return tmp.time;
             49                    next.time = tmp.time;
             50                    vist[next.x][next.y] = true;
             51                    q.push(next);
             52                    tmp = next;
             53                 }else break;
             54           }
             55           for (int i = 0; i < 8; i++)
             56           {
             57               next.x = now.x + xi[i];
             58               next.y = now.y + yi[i];
             59               if (check(next.x, next.y) && !vist[next.x][next.y])
             60               {
             61                  if (map[now.x][now.y] - '0' == i) next.time = now.time;
             62                  else next.time = now.time + 1;
             63                  if (next.x == end.x && next.y == end.y) return next.time;
             64                  vist[next.x][next.y] = true;
             65                  q.push(next);
             66                  tmp = next;
             67                  while (1)
             68                  {
             69                        next.x = tmp.x + xi[map[tmp.x][tmp.y]-'0'];
             70                        next.y = tmp.y + yi[map[tmp.x][tmp.y]-'0'];
             71                        if (check(next.x, next.y) && !vist[next.x][next.y])
             72                        {
             73                           if (next.x == end.x && next.y == end.y) return tmp.time;
             74                           next.time = tmp.time;
             75                           vist[next.x][next.y] = true;
             76                           q.push(next);
             77                           tmp = next;
             78                        }else break;
             79                   }
             80               }
             81           }
             82     }
             83     return 0;
             84 }
             85 int main()
             86 {
             87     while (scanf("%d%d"&n, &m) != EOF)
             88     {
             89           int i, j;
             90           for (i = 0; i < n; i++)
             91               scanf("%s", map[i]);
             92           int T;
             93           scanf("%d"&T);
             94           node now, end;
             95           for (i = 0; i < T; i++)
             96           {
             97               scanf("%d%d%d%d"&now.x, &now.y, &end.x, &end.y);
             98               now.time = 0;
             99               now.x --;
            100               now.y --;
            101               end.x --;
            102               end.y --;
            103               if (now.x == end.x && now.y == end.y)
            104               {
            105                  printf("0\n");
            106               }else printf("%d\n", bfs(now, end));
            107           }
            108     }
            109 return 0;
            110 }
            111 

            posted on 2012-04-22 20:23 路修遠(yuǎn) 閱讀(1338) 評論(0)  編輯 收藏 引用 所屬分類: 路修遠(yuǎn)
            <2010年6月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            轉(zhuǎn)載,請標(biāo)明出處!謝謝~~

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            文章檔案

            搜索

            •  

            最新評論

            • 1.?re: HDU 2433 最短路
            • @test
              的確這組數(shù)據(jù)應(yīng)該輸出20的
            • --YueYueZha
            • 2.?re: HDU 2433 最短路
            • 這方法應(yīng)該不對。 看下面這組數(shù)據(jù)
              4 4
              1 2
              2 3
              3 4
              2 4

              畫個圖,刪去最后一條邊 2 4 后的結(jié)果應(yīng)該是20,但是此方法的輸出是19
            • --test
            • 3.?re: HDU 2433 最短路
            • ans = ans + sum_u + sum_v - sum[u] - sum[v],
              這個公式不是很理解啊,不知道博主怎么想的啊,謝謝咯
            • --姜
            • 4.?re: HDU 2433 最短路
            • @attacker
              the i-th line is the new SUM after the i-th road is destroyed
            • --路修遠(yuǎn)
            • 5.?re: HDU 2433 最短路
            • 你這樣可以AC????刪除<U,V>不僅改變 u,v最短路啊、、、求解
            • --attacker

            閱讀排行榜

            評論排行榜

            亚洲欧美精品伊人久久| 欧美黑人激情性久久| 午夜精品久久久久久中宇| 伊人久久大香线蕉av一区| 99精品国产综合久久久久五月天| 久久精品aⅴ无码中文字字幕不卡| 潮喷大喷水系列无码久久精品| 国产福利电影一区二区三区,免费久久久久久久精 | 一本色道久久88精品综合| 久久香蕉超碰97国产精品| 亚洲国产成人精品久久久国产成人一区二区三区综 | 狠狠干狠狠久久| 亚洲日本va中文字幕久久| 热re99久久精品国产99热| 久久天堂AV综合合色蜜桃网 | 久久久无码精品午夜| 亚洲va久久久噜噜噜久久狠狠| 久久电影网2021| 国产成年无码久久久免费| 狠狠人妻久久久久久综合蜜桃| 国产精品一区二区久久不卡| 欧美一级久久久久久久大| 久久精品一区二区三区不卡| 无码任你躁久久久久久老妇App| 久久久久久久综合日本亚洲| 久久久噜噜噜久久熟女AA片| 99精品久久精品一区二区| 久久久国产一区二区三区| 日韩AV毛片精品久久久| 一本大道加勒比久久综合| 久久亚洲精品人成综合网| 囯产精品久久久久久久久蜜桃 | 亚洲精品无码久久千人斩| 热RE99久久精品国产66热| 精品欧美一区二区三区久久久| 国产日产久久高清欧美一区| 精品久久久噜噜噜久久久| 天天爽天天狠久久久综合麻豆| 亚洲精品乱码久久久久久| 99久久精品国产一区二区| 伊人色综合久久天天人手人婷|