hdu 2757 Ocean Currents

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, -1, 0, 1, 1, 1, 0, -1};
 14 int yi[8] = {0, 1, 1, 1, 0, -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