• <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(),當(dāng)然你也可以用dfs,只要你不怕超時(shí)或者你的剪枝夠強(qiáng)大
                  最好開一個(gè)三維的數(shù)組,記錄每一個(gè)格子的每一個(gè)方向上的最小值,直到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 路修遠(yuǎn) 閱讀(1315) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 路修遠(yuǎn)
            <2012年4月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

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

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            文章檔案

            搜索

            •  

            最新評(píng)論

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

              畫個(gè)圖,刪去最后一條邊 2 4 后的結(jié)果應(yīng)該是20,但是此方法的輸出是19
            • --test
            • 3.?re: HDU 2433 最短路
            • ans = ans + sum_u + sum_v - sum[u] - sum[v],
              這個(gè)公式不是很理解啊,不知道博主怎么想的啊,謝謝咯
            • --姜
            • 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

            閱讀排行榜

            評(píng)論排行榜

            久久久SS麻豆欧美国产日韩| 99久久99这里只有免费费精品| 国产成人精品白浆久久69| 国产Av激情久久无码天堂| 9久久9久久精品| 蜜臀久久99精品久久久久久| 中文字幕无码久久久| 国内精品久久久久久99蜜桃| 国产日韩久久免费影院| 无码人妻久久一区二区三区免费丨| 精品综合久久久久久97超人 | 99久久无色码中文字幕人妻| 久久男人Av资源网站无码软件| 国产视频久久| 欧美丰满熟妇BBB久久久| 国产精品美女久久久久AV福利| 久久综合香蕉国产蜜臀AV| 久久亚洲色一区二区三区| 2020久久精品国产免费| 女人高潮久久久叫人喷水| 日韩一区二区久久久久久| 97久久国产露脸精品国产| 青春久久| 久久天天躁狠狠躁夜夜2020老熟妇| 久久国产精品99精品国产| 久久只有这精品99| 日韩中文久久| 久久精品国产一区二区三区| 99久久中文字幕| 91精品国产高清91久久久久久| 欧美精品乱码99久久蜜桃| 免费一级欧美大片久久网| 久久精品18| 欧美一级久久久久久久大片| 国产午夜福利精品久久| 国产精品嫩草影院久久| 久久99国产精品久久久| 久久亚洲综合色一区二区三区| 久久国产精品久久| a级毛片无码兔费真人久久| 激情综合色综合久久综合|