Gym - 100625J Jailbreak 最短路+搜索

http://codeforces.com/gym/100625/attachments/download/3213/2013-benelux-algorithm-programming-contest-bapc-13-en.pdf

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

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

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

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

 #pragma comment(linker, "/STACK:1000000000")

 #include <iostream>

 #include <cstdio>

 #include <fstream>

 #include <algorithm>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <string>

 #include <cstring>

 #include <map>

 #include <stack>

 #include <set>

 #define LL long long

 #define MAXN 100005

 #define MOD 1000000007

 #define INF 0x3f3f3f3f

 #define eps 1e-8

 using namespace std;

 char a[][];

 int n, m;

 int w[], ds[], dt[];

 bool vis[][];

 vector<int> door;

 queue<int> Q;

 const int step[][] = { , , , , -, , , - };

 void dfs(int x, int y, int d, int *f){

     for (int i = ; i < ; i++){

         int u = x + step[i][];

         int v = y + step[i][];

         if (vis[u][v] || a[u][v] == '*' || u <  || v <  || u >= n || v >= m) continue;

         f[m * u + v] = d;

         vis[u][v] = true;

         if (a[u][v] == '#'){

             f[m * u + v]++;

             Q.push(m * u + v);

         }

         else{

             dfs(u, v, d, f);

         }

     }

 }

 void bfs(int *f){

     while (!Q.empty()){

         int p = Q.front();

         int x = p / m, y = p % m;

         Q.pop();

         //dfs一次相当于代价加一

         dfs(x, y, f[m * x + y], f);

     }

 }

 int main()

 {

 #ifndef ONLINE_JUDGE

     freopen("in.txt", "r", stdin);

     //freopen("out.txt", "w", stdout);

 #endif // OPEN_FILE

     int T;

     scanf("%d", &T);

     while (T--){

         scanf("%d%d", &n, &m);

         for (int i = ; i < n; i++){

             scanf("%s", &a[i]);

         }

         memset(w, INF, sizeof(w));

         memset(ds, INF, sizeof(ds));

         memset(dt, INF, sizeof(dt));

         memset(vis, , sizeof(vis));

         door.clear();

         bool apos = false;

         int s = , t = ;

         for (int i = ; i < n; i++){

             for (int j = ; j < m; j++){

                 if ((i ==  || j ==  || i == n -  || j == m - ) && (a[i][j] == '.' || a[i][j] == '$')){

                     Q.push(m * i + j);

                     w[m * i + j] = ;

                     vis[i][j] == true;

                 }

             }

         }

         for (int i = ; i < n; i++){

             for (int j = ; j < m; j++){

                 if (a[i][j] == '*') continue;

                 if ((i ==  || j ==  || i == n -  || j == m - ) && a[i][j] == '#'){

                     w[m * i + j] = ;

                     Q.push(m * i + j);

                     vis[i][j] = true;

                 }

                 if (a[i][j] == '#'){

                     door.push_back(m * i + j);

                 }

                 if (a[i][j] == '$'){

                     if (!apos){

                         s = m * i + j;

                         ds[s] = ;

                         apos = true;

                     }

                     else{

                         t = m * i + j;

                         dt[t] = ;

                     }

                 }

             }

         }

         bfs(w);

         memset(vis, , sizeof(vis));

         vis[s / m][s % m] = true;

         Q.push(s);

         bfs(ds);

         memset(vis, , sizeof(vis));

         vis[t / m][t % m] = true;

         Q.push(t);

         bfs(dt);

         int ans = w[s] + w[t];

         for (int i = ; i < door.size(); i++){

             ans = min(ans, ds[door[i]] + dt[door[i]] + w[door[i]] - );

         }

         printf("%d\n", ans);

     }

 }

巴特西

Gym - 100625J Jailbreak 最短路+搜索

最新文章

热门文章