Gym - 100625J Jailbreak 最短路+搜索-白红宇

Gym - 100625J Jailbreak 最短路+搜索

阅读量：5226 次

发布时间：2019-06-14

本文共 3185 字，大约阅读时间需要 10 分钟。

题意：给你一幅图，让两个人从里面走出来的代价最小。经过 . 没有消耗，经过 # 耗费一个代价，* 不能通过。

思路：比赛时以为是类似于两条路之和最小的那种题，所以没有仔细去想，下来后听了别人提了下思路，也看了下别人的代码，明白了。分两种情况考虑，一种是相遇，一种是不相遇。如果存在不相遇这种答案的话，那结果就是他们俩的最短路之和，相遇的话，就是他们俩到相遇的地方的最短路之和加上相遇的door到外面的最短路减2。这是陈力琪他们队做的，我也是看了他们的代码。

　　所以求三遍最短路，第一遍w[i] 表示i这个点到外面的最小代价。第二遍 ds[i] 表示从s(第一个人位置)到i的最小代价，第三遍 dt[i] 表示从t到i的最短路。按照上面的说法得出答案就可以了。

　　比较有意思是这里的搜索，因为 . 是不需要代价的，所以在bfs的时候每下一步就直接dfs一次找到下一个#所在的位置再把代价+1入队。在求w[i]的时候，因为距离可能为0，所以得先把边界上的 . 入队，不然w[i]就会求错。

1 #pragma comment(linker, "/STACK:1000000000")  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 #include 
        
           6 #include 
         
            7 #include 
          
            8 #include 
           
             9 #include 
            
              10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #define LL long long 16 #define MAXN 100005 17 #define MOD 1000000007 18 #define INF 0x3f3f3f3f 19 #define eps 1e-8 20 using namespace std; 21 char a[105][105]; 22 int n, m; 23 int w[10005], ds[10005], dt[10005]; 24 bool vis[105][105]; 25 vector
                  
                    door; 26 queue
                   
                     Q; 27 const int step[4][2] = { 1, 0, 0, 1, -1, 0, 0, -1 }; 28 void dfs(int x, int y, int d, int *f){ 29 for (int i = 0; i < 4; i++){ 30 int u = x + step[i][0]; 31 int v = y + step[i][1]; 32 if (vis[u][v] || a[u][v] == '*' || u < 0 || v < 0 || u >= n || v >= m) continue; 33 f[m * u + v] = d; 34 vis[u][v] = true; 35 if (a[u][v] == '#'){ 36 f[m * u + v]++; 37 Q.push(m * u + v); 38 } 39 else{ 40 dfs(u, v, d, f); 41 } 42 } 43 } 44 void bfs(int *f){ 45 while (!Q.empty()){ 46 int p = Q.front(); 47 int x = p / m, y = p % m; 48 Q.pop(); 49 //dfs一次相当于代价加一 50 dfs(x, y, f[m * x + y], f); 51 } 52 } 53 int main() 54 { 55 #ifndef ONLINE_JUDGE 56 freopen("in.txt", "r", stdin); 57 //freopen("out.txt", "w", stdout); 58 #endif // OPEN_FILE 59 int T; 60 scanf("%d", &T); 61 while (T--){ 62 scanf("%d%d", &n, &m); 63 for (int i = 0; i < n; i++){ 64 scanf("%s", &a[i]); 65 } 66 memset(w, INF, sizeof(w)); 67 memset(ds, INF, sizeof(ds)); 68 memset(dt, INF, sizeof(dt)); 69 memset(vis, 0, sizeof(vis)); 70 door.clear(); 71 bool apos = false; 72 int s = 0, t = 0; 73 for (int i = 0; i < n; i++){ 74 for (int j = 0; j < m; j++){ 75 if ((i == 0 || j == 0 || i == n - 1 || j == m - 1) && (a[i][j] == '.' || a[i][j] == '$')){ 76 Q.push(m * i + j); 77 w[m * i + j] = 0; 78 vis[i][j] == true; 79 } 80 } 81 } 82 for (int i = 0; i < n; i++){ 83 for (int j = 0; j < m; j++){ 84 if (a[i][j] == '*') continue; 85 if ((i == 0 || j == 0 || i == n - 1 || j == m - 1) && a[i][j] == '#'){ 86 w[m * i + j] = 1; 87 Q.push(m * i + j); 88 vis[i][j] = true; 89 } 90 if (a[i][j] == '#'){ 91 door.push_back(m * i + j); 92 } 93 if (a[i][j] == '$'){ 94 if (!apos){ 95 s = m * i + j; 96 ds[s] = 0; 97 apos = true; 98 } 99 else{100 t = m * i + j;101 dt[t] = 0;102 }103 }104 }105 }106 bfs(w);107 memset(vis, 0, sizeof(vis));108 vis[s / m][s % m] = true;109 Q.push(s);110 bfs(ds);111 memset(vis, 0, sizeof(vis));112 vis[t / m][t % m] = true;113 Q.push(t);114 bfs(dt);115 int ans = w[s] + w[t];116 for (int i = 0; i < door.size(); i++){117 ans = min(ans, ds[door[i]] + dt[door[i]] + w[door[i]] - 2);118 }119 printf("%d\n", ans);120 }121 }

转载于:https://www.cnblogs.com/macinchang/p/4718108.html

你可能感兴趣的文章