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 路修远 阅读(1199) 评论(0)  编辑 收藏 引用 所属分类: 路修远

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年4月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

转载,请标明出处!谢谢~~

常用链接

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

阅读排行榜

评论排行榜