程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> hdu 2757 Ocean Currents

hdu 2757 Ocean Currents

編輯:關於C語言

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

 

摘自 路修遠

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved