• <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的好題目!
                  開始想到用優先隊列,無情的還是過了, 只不過時間用了2000ms多,差點就掛了~杯具的優先
                  后來一想,其實可以直接bfs, 有情的是意料之外的沒有出現TE,而是AC,徹底無語的是只用了500ms多!!!!
                  大呼優先之哀哉……
                  至于bfs的做法如下:
                        1,開始點進棧
                        2,開始點能直接到達(不花時間的)的所有的點進棧
                        3,分兩步
                           3.1 開始點不能直接到達(要時間)的點進棧
                           3.2 將這個點能直接到達(不花時間的)的所有的點進棧
                           3.3 跳轉到3
                       4 跳轉到1
                     注:開始點為當前出棧的第一個點
                    不明白這個過程的可以看代碼(雖然代碼有點……,還可以進一步簡化, 以后不能老想著優先了,誰優先誰杯具,當然不是說我們的廣大女同胞……)
              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 路修遠 閱讀(1338) 評論(0)  編輯 收藏 引用 所屬分類: 路修遠
            <2010年6月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            轉載,請標明出處!謝謝~~

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            文章檔案

            搜索

            •  

            最新評論

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

              畫個圖,刪去最后一條邊 2 4 后的結果應該是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
            • --路修遠
            • 5.?re: HDU 2433 最短路
            • 你這樣可以AC????刪除<U,V>不僅改變 u,v最短路啊、、、求解
            • --attacker

            閱讀排行榜

            評論排行榜

            热综合一本伊人久久精品| 东方aⅴ免费观看久久av| 青青草原综合久久大伊人| 国产精品永久久久久久久久久| 久久精品国产网红主播| 综合人妻久久一区二区精品| 亚洲精品无码专区久久同性男| 久久午夜无码鲁丝片午夜精品| 久久国产精品免费一区| 国产激情久久久久影院| 精品久久人人妻人人做精品| 亚洲一区二区三区日本久久九| 色综合久久88色综合天天| 亚洲国产成人久久综合一| 国内精品久久久久久久涩爱 | 97超级碰碰碰碰久久久久| 精品亚洲综合久久中文字幕| 精品久久久久久中文字幕| 99久久国产亚洲高清观看2024 | 色妞色综合久久夜夜| 久久久久久久91精品免费观看| 18禁黄久久久AAA片| 久久综合久久自在自线精品自| 大伊人青草狠狠久久| 久久久久99精品成人片| 久久精品国产亚洲AV不卡| 国产69精品久久久久777| 久久国产成人午夜AV影院| 奇米影视7777久久精品人人爽| 久久久久人妻一区精品色| 国产精品成人99久久久久91gav| 亚洲AV伊人久久青青草原| 精品久久久久久无码中文字幕一区 | 国产欧美久久一区二区| 亚洲精品成人网久久久久久| 久久国产乱子伦免费精品| 亚洲国产成人精品91久久久 | 亚洲精品美女久久久久99| 久久国产精品-国产精品| 久久午夜无码鲁丝片秋霞 | 狠狠色综合网站久久久久久久高清|