0
Your rating: None

CodeChef submission 19878 (C++ 4.0.0-8)

CodeChef submission 19878 (C++ 4.0.0-8) plaintext list. Status: AC, problem B1, contest APRIL09. By srinivas (srinivas), 2009-04-12 16:30:05.
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <map>
  6. #include <queue>
  7. #include <set>
  8. #include <stack>
  9. #include <vector>
  10. using namespace std;
  11. #define For(i,a,b) for (i=a; i != b; ++i)
  12. #define Rep(i,n) For(i,0,n)
  13. #define set(a,c) memset(a,c,sizeof(a))
  14. #define GI ({int t;scanf("%d",&t);t;})
  15. typedef pair<int,int> ii;
  16. priority_queue<ii> Q;
  17. char S[1001][1001];
  18. bool reach[1001][1001];
  19. int dist[1001][1001];
  20. int ans[1001][1001];
  21. int st, dst;
  22. int main() {
  23.   int m = GI, n = GI;
  24.   int i, j;
  25.   queue<int> Qu;
  26.   Rep(i,m)
  27.     Rep(j,n) {
  28.     cin >> S[i][j];
  29.     if (S[i][j] == '$')
  30.       dst = i*n + j;
  31.     else if (S[i][j] == '@')
  32.       st = i*n + j;
  33.     else if (S[i][j] == 'D') {
  34.       Qu.push(i*n+j);
  35.       reach[i][j] = 1;
  36.       dist[i][j] = 0;
  37.     }
  38.   }
  39.   while (!Qu.empty()) {
  40.     int cur = Qu.front();
  41.     Qu.pop();
  42.     int u = cur / n;
  43.     int v = cur % n;
  44.     if (u > 0 && !reach[u-1][v]) {
  45.       reach[u-1][v] = 1;
  46.       dist[u-1][v] = dist[u][v] + 1;
  47.       Qu.push((u-1)*n+v);
  48.     }
  49.     if (v > 0 && !reach[u][v-1]) {
  50.       reach[u][v-1] = 1;
  51.       dist[u][v-1] = dist[u][v] + 1;
  52.       Qu.push(u*n + v - 1);
  53.     }
  54.     if (u < m-1 && !reach[u+1][v]) {
  55.       reach[u+1][v] = 1;
  56.       dist[u+1][v]= dist[u][v] + 1;
  57.       Qu.push((u+1)*n + v);
  58.     }
  59.     if (v < n-1 && !reach[u][v+1]) {
  60.       reach[u][v+1] = 1;
  61.       dist[u][v+1]= dist[u][v] + 1;
  62.       Qu.push(u*n + v + 1);
  63.     }
  64.   }
  65.   Q.push(ii(dist[st/n][st%n],st));
  66.   ans[st/n][st%n] = dist[st/n][st%n];
  67.   Rep(i,m*n) {
  68.     if (i == st)
  69.       continue;
  70.     ans[i/n][i%n] = -1;
  71.   }
  72.   set(reach,0);
  73.   while (!Q.empty()) {
  74.     ii top = Q.top();
  75.     int d = top.first;
  76.     Q.pop();
  77.     int u = top.second / n;
  78.     int v = top.second % n;
  79.     if (u*n+v == dst)
  80.       break;
  81.     if (reach[u][v])
  82.       continue;
  83.     reach[u][v] = 1;
  84.     if (u > 0) {
  85.       if (ans[u-1][v] < min(d,dist[u-1][v])) {
  86. 	ans[u-1][v] = min(d,dist[u-1][v]);
  87. 	Q.push(ii(ans[u-1][v],(u-1)*n+v));
  88.       }
  89.     }
  90.     if (v > 0) {
  91.       if (ans[u][v-1] < min(d,dist[u][v-1])) {
  92. 	ans[u][v-1] = min(d,dist[u][v-1]);
  93. 	Q.push(ii(ans[u][v-1],(u)*n+v-1));
  94.       }
  95.     }
  96.     if (u < m-1) {
  97.       if (ans[u+1][v] < min(d,dist[u+1][v])) {
  98. 	ans[u+1][v] = min(d,dist[u+1][v]);
  99. 	Q.push(ii(ans[u+1][v],(u+1)*n+v));
  100.       }
  101.     }
  102.     if (v < n-1) {
  103.       if (ans[u][v+1] < min(d,dist[u][v+1])) {
  104. 	ans[u][v+1] = min(d,dist[u][v+1]);
  105. 	Q.push(ii(ans[u][v+1],(u)*n+v+1));
  106.       }
  107.     }
  108.   }
  109.   cout << ans[dst/n][dst%n] << endl;
  110. }
  111.

Comments