• <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(),當然你也可以用dfs,只要你不怕超時或者你的剪枝夠強大
                  最好開一個三維的數組,記錄每一個格子的每一個方向上的最小值,直到bfs完成
                  具體看代碼,不做過多的解釋。
              1 #include <iostream>
              2 #include <queue>
              3 using namespace std;
              4 struct node
              5 {
              6        int x, y;
              7        int step, dir;
              8 };
              9 int n, m;
             10 int xi[4= {01-10};
             11 int yi[4= {100-1};
             12 int vist[82][82][4];
             13 char map[82][82];
             14 node start;
             15 queue <node> q;
             16 bool check(int dx, int dy)
             17 {
             18      if(dx >= 1 && dx <= n && dy >= 1 && dy <= m) return true;
             19      else return false;
             20 }
             21 bool find(node a)
             22 {
             23      if ((a.x == 1 || a.x == n || a.y == 1 || a.y == m)) return true;
             24      else return false;
             25 }
             26 int bfs()
             27 {
             28      while (!q.empty())q.pop();
             29      memset(vist, 0sizeof(vist));
             30      start.dir = -1;
             31      start.step = 0;
             32      q.push(start);
             33      node now, next;
             34      bool flag = true;
             35      int tmp;
             36      while (!q.empty())
             37      {
             38            now = q.front();
             39            q.pop();
             40            if (find(now)) return now.step;
             41            
             42            flag = false;
             43            for (int i = 0 ; i < 4; i++)
             44            {
             45               if (now.dir == i) continue;
             46               if (now.dir >=0 && 3-now.dir == i) continue;
             47               next.x = now.x + xi[i];
             48               next.y = now.y + yi[i];
             49               next.step = now.step + 1;
             50               if (check(next.x, next.y) && map[next.x][next.y] == '.' )
             51               {
             52                  if (vist[next.x][next.y][i] == 0)  
             53                  {
             54                     vist[next.x][next.y][i] = next.step;
             55                     next.dir = i;
             56                     q.push(next);
             57                  }
             58                  else if (vist[next.x][next.y][i] > next.step)
             59                  {
             60                     vist[next.x][next.y][i] = next.step;
             61                     next.dir = i;
             62                     q.push(next);
             63                  }
             64                  flag = true;
             65               }
             66            }
             67            if (!flag)
             68            {
             69               int i = now.dir;
             70               if (i < 0return 0;
             71               next.x = now.x + xi[i];
             72               next.y = now.y + yi[i];
             73               next.step = now.step + 1;
             74               if (check(next.x, next.y) && map[next.x][next.y] == '.' )
             75               {
             76                  if (vist[next.x][next.y][i] == 0)  
             77                  {
             78                     vist[next.x][next.y][i] = next.step;
             79                     next.dir = i;
             80                     q.push(next);
             81                  }
             82                  else if (vist[next.x][next.y][i] > next.step)
             83                  {
             84                     vist[next.x][next.y][i] = next.step;
             85                     next.dir = i;
             86                     q.push(next);
             87                  }
             88                  flag = true;
             89               }
             90            }
             91      }
             92      return -1;
             93 }
             94 int main()
             95 {
             96     int cas;
             97     scanf("%d"&cas);
             98     while (cas--)
             99     {
            100           scanf("%d%d"&n, &m);
            101           int i, j;
            102           for (i = 1; i <= n; i++)
            103               scanf("%s", map[i]+1);
            104           for (i = 1; i <= n; i++)
            105           for (j = 1; j <= m; j++)
            106           {
            107               if (map[i][j] == '@')
            108               {
            109                  start.x = i;
            110                  start.y = j;
            111                  map[i][j] = '.';
            112               }
            113           }
            114           int ans = bfs();
            115           printf("%d\n", ans);
            116     }
            117 return 0;
            118 }
            119 
            posted on 2012-04-13 18:34 路修遠 閱讀(1315) 評論(0)  編輯 收藏 引用 所屬分類: 路修遠
            <2013年1月>
            303112345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

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

            常用鏈接

            留言簿(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

            閱讀排行榜

            評論排行榜

            久久人人爽人人爽人人爽 | 久久久SS麻豆欧美国产日韩| 国产成人精品久久亚洲| 久久丝袜精品中文字幕| 久久久久久国产a免费观看黄色大片| 久久久久久久久久久久久久| 国产V综合V亚洲欧美久久| 久久99精品久久久久久噜噜| 久久综合给合久久狠狠狠97色| 国内精品久久久久久久亚洲 | 久久99国产精品久久久| 亚洲а∨天堂久久精品| 丁香狠狠色婷婷久久综合| 日本五月天婷久久网站| 一级做a爱片久久毛片| 色8久久人人97超碰香蕉987| 手机看片久久高清国产日韩| 美女写真久久影院| 精品无码久久久久久午夜| 久久精品国产清自在天天线| 久久精品?ⅴ无码中文字幕| 久久国产精品成人影院| 亚洲va久久久噜噜噜久久| 久久青青草视频| 久久亚洲欧洲国产综合| 99久久无码一区人妻| 国产精品久久久亚洲| 日韩人妻无码精品久久免费一 | 国产精品内射久久久久欢欢| 久久精品人人做人人妻人人玩| 中文国产成人精品久久不卡| 色天使久久综合网天天| 无码8090精品久久一区 | 一级a性色生活片久久无少妇一级婬片免费放 | 天天爽天天狠久久久综合麻豆| 久久亚洲中文字幕精品一区| 日韩一区二区三区视频久久| 久久综合伊人77777| 亚洲精品久久久www| 久久无码AV一区二区三区| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 |