SHARE
TWEET

Untitled

a guest Jan 26th, 2020 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. // READING INPUT
  6. #define SCD(t) fscanf(stdin, "%d",&t)
  7. #define SCLD(t) fscanf(stdin, "%ld",&t)
  8. #define SCLLD(t) fscanf(stdin, "%lld",&t)
  9. #define SCC(t) fscanf(stdin, "%col",&t)
  10. #define SCS(t) fscanf(stdin, "%s",t)
  11. #define SCF(t) fscanf(stdin, "%f",&t)
  12. #define SCLF(t) fscanf(stdin, "%lf",&t)
  13. // CHECKING BOUNDS
  14. #define IN(i,l,r) (l<i&&i<r)
  15. #define LINR(i,l,r) (l<=i&&i<=r)
  16. #define LIN(i,l,r) (l<=i&&i<r)
  17. #define INR(i,l,r) (l<i&&i<=r)
  18. // LOOPS
  19. #define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
  20. #define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
  21. #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
  22. #define WHILEZ int T; SCD(T); while(T--)
  23. // MISC
  24. #define all(cont) cont.begin(), cont.end()
  25. #define rall(cont) cont.end(), cont.begin()
  26. #define by(T, x) [](const T& a, const T& b) { return a.x < b.x; }
  27. #define PB push_back
  28. #define INF 1000000000
  29.  
  30. typedef pair<int,int> ii;
  31. typedef pair<int, ii> iii;
  32. typedef vector<int> vi;
  33. typedef vector<vi> vvi;
  34. typedef vector<ii> vii;
  35. typedef long long ll;
  36.  
  37. // Offset Arrays
  38. const int fx[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
  39. const int fxx[8][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1}, {-1,-1}};
  40. const int cx[6][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}, {-1, 0, 0}, {0, -1, 0}, {0, 0, -1}};
  41. const int UNVISITED = -1;
  42.  
  43. class BigArr {
  44.     public:
  45.     char blueprint[100][100][100];
  46.     int ans[100][100][100];
  47.     int dist[100][100][100];      
  48. };
  49.  
  50. int main() {
  51.     BigArr *arr = new BigArr;
  52.     int r[100];
  53.     int c[100];
  54.     vector<iii> stairs[56];
  55.     int f, row, col;
  56.     SCD(f);
  57.     for (int i = 0; i < f; i++) {
  58.         SCD(row);
  59.         SCD(col);
  60.         r[i] = row - 2;
  61.         c[i] = col - 2;
  62.         getchar();
  63.         for (int j = 0; j < row; j++) {
  64.             for (int k = 0; k < col; k++) {
  65.                 char ch;
  66.                 SCC(ch);
  67.                 if (!(j == 0 || j == row - 1 || k == 0 || k == col - 1)) {
  68.                     arr->blueprint[i][j - 1][k - 1] = ch;
  69.                     arr->ans[i][j - 1][k - 1] = UNVISITED;
  70.                     if (ch != '.' && ch != '#') {
  71.                         if (isupper(ch)) {
  72.                             stairs[ch - 'A'].PB(iii(i, ii(j - 1, k - 1)));
  73.                         } else {
  74.                             stairs[ch - 'a' + 26].PB(iii(i, ii(j - 1, k - 1)));
  75.                         }
  76.                     }
  77.                 }
  78.             }
  79.             getchar();
  80.         }
  81.     }
  82.     vector<vector<iii> > corners;
  83.     int components = 0;
  84.     for (int i = 0; i < f; i++) {
  85.         for (int j = 0; j < r[i]; j++) {
  86.             for (int k = 0; k < c[i]; k++) {
  87.                 if (arr->blueprint[i][j][k] != '#' && arr->ans[i][j][k] == UNVISITED) {
  88.                     queue<iii> q;
  89.                     q.push(iii(i, ii(j, k)));
  90.                     arr->ans[i][j][k] = components;
  91.                     corners.PB(vector<iii>());
  92.                     while (!q.empty()) {
  93.                         int curF = q.front().first;
  94.                         int curR = q.front().second.first;
  95.                         int curC = q.front().second.second;
  96.                         q.pop();
  97.                         bool hasAdjacentWall = false;
  98.                         for (int i = 0; i < 4; i++) {
  99.                             int nextF = curF;
  100.                             int nextR = curR + fx[i][0];
  101.                             int nextC = curC + fx[i][1];
  102.                             if (LIN(nextR, 0, r[nextF]) && LIN(nextC, 0, c[nextF])) {
  103.  
  104.                                 if (arr->ans[nextF][nextR][nextC] == UNVISITED) {
  105.                                     if (arr->blueprint[nextF][nextR][nextC] != '#') {
  106.                                         arr->ans[nextF][nextR][nextC] = components;
  107.                                         q.push(iii(nextF, ii(nextR, nextC)));
  108.                                     } else hasAdjacentWall = true;
  109.                                 }
  110.                             }
  111.                         }
  112.                         if (hasAdjacentWall) {
  113.                             corners[components].PB(iii(curF, ii(curR, curC)));
  114.                         }
  115.                         char ch = arr->blueprint[curF][curR][curC];
  116.                         if (ch != '#' && ch != '.') {
  117.                             int stair = isupper(ch) ? ch - 'A' : ch - 'a' + 26;
  118.                             for (int l = 0; l < stairs[stair].size(); l++) {
  119.                                 int nextF = stairs[stair][l].first;
  120.                                 int nextR = stairs[stair][l].second.first;
  121.                                 int nextC = stairs[stair][l].second.second;
  122.                                 if (arr->ans[nextF][nextR][nextC] == UNVISITED) {
  123.                                     arr->ans[nextF][nextR][nextC] = components;
  124.                                     q.push(iii(nextF, ii(nextR, nextC)));
  125.                                 }
  126.                             }
  127.                         }
  128.                     }
  129.                     components++;
  130.                 }
  131.             }
  132.         }
  133.     }
  134.    
  135.     priority_queue<ii, vii, greater<ii> > pq;
  136.     vi dijkstra(components, INF);
  137.     unordered_set<int> src;
  138.     unordered_set<int> dest;
  139.     for (int i = 0; i < r[0]; i++) {
  140.         for (int j = 0; j < c[0]; j++) {
  141.             if (arr->ans[0][i][j] != UNVISITED) {
  142.                 int u = arr->ans[0][i][j];
  143.                 src.insert(u);
  144.             }
  145.         }
  146.     }
  147.     for (unordered_set<int>::iterator itr = src.begin(); itr != src.end(); itr++) {
  148.         int u = *itr;
  149.         pq.push(ii(0, u));
  150.         dijkstra[u] = 0;
  151.     }
  152.  
  153.     for (int i = 0; i < r[f - 1]; i++) {
  154.         for (int j = 0; j < c[f - 1]; j++) {
  155.             if (arr->ans[0][i][j] != UNVISITED) {
  156.                 int u = arr->ans[f - 1][i][j];
  157.                 dest.insert(u);
  158.             }
  159.         }
  160.     }
  161.    
  162.     vvi adjList = vvi(components, vi());
  163.     vvi adjMatrix = vvi(components, vi(components, INF));
  164.     for (int u = 0; u < components; u++) {
  165.         queue<iii> q;
  166.         memset(arr->dist, UNVISITED, sizeof arr->dist);
  167.        
  168.         for (int i = 0; i < corners[u].size(); i++) {
  169.             int floor = corners[u][i].first, row = corners[u][i].second.first, column = corners[u][i].second.second;
  170.             arr->dist[floor][row][column] = 0;
  171.             q.push(iii(floor, ii(row, column)));
  172.         }
  173.         while (!q.empty()) {
  174.             int curF = q.front().first;
  175.             int curR = q.front().second.first;
  176.             int curC = q.front().second.second;
  177.             int curD = arr->dist[curF][curR][curC];
  178.             q.pop();
  179.             for (int i = 0; i < 4; i++) {
  180.                 int nextF = curF;
  181.                 int nextR = curR + fx[i][0];
  182.                 int nextC = curC + fx[i][1];
  183.                 if (LIN(nextR, 0, r[nextF]) && LIN(nextC, 0, c[nextF])) {
  184.                     if (arr->dist[nextF][nextR][nextC] == UNVISITED) {
  185.  
  186.                         if (arr->blueprint[nextF][nextR][nextC] == '#') {
  187.                             arr->dist[nextF][nextR][nextC] = curD + 1;
  188.                             q.push(iii(nextF, ii(nextR, nextC)));
  189.                         } else if (arr->ans[nextF][nextR][nextC] != u) {
  190.                             int v = arr->ans[nextF][nextR][nextC];
  191.                             if (adjMatrix[u][v] == INF) adjList[u].PB(v);
  192.                             adjMatrix[u][v] = min(adjMatrix[u][v], curD);
  193.                         }
  194.                     }
  195.                 }
  196.             }
  197.         }
  198.     }
  199.     // for (int i = 0; i < f; i++) {
  200.     //     for (int j = 0; j < r[i]; j++) {
  201.     //         for (int k = 0; k < c[i]; k++) {
  202.     //             fprintf(stdout, "%c", arr->ans[i][j][k] + 'A');
  203.     //         }
  204.     //         fprintf(stdout, "\n");
  205.     //     }
  206.     //     fprintf(stdout, "\n");
  207.     // }
  208.     // for (int i = 0; i < components; i++) {
  209.     //     fprintf(stdout, "%d : ", i);
  210.     //     for (int j = 0; j < adjList[i].size(); j++) {
  211.     //         int u = i, v = adjList[i][j];
  212.     //         fprintf(stdout, "%d = %d, ", v, adjMatrix[u][v]);
  213.     //     }
  214.     //     fprintf(stdout, "\n");
  215.     // }
  216.     // for (set<int>::iterator itr = dest.begin(); itr != dest.end(); itr++) {
  217.     //     fprintf(stdout, "%d ", *itr);
  218.     // }
  219.     // fprintf(stdout, "\n");
  220.     while (!pq.empty()) {
  221.         int d = pq.top().first;
  222.         int u = pq.top().second;
  223.         // fprintf(stdout, "processing %d with shortest distance %d\n",u, d);
  224.         pq.pop();
  225.         if (d > dijkstra[u]) continue;
  226.         if (dest.find(u) != dest.end()) {
  227.             fprintf(stdout, "%d", d);
  228.             return 0;
  229.         }
  230.         for (int i = 0; i < adjList[u].size(); i++) {
  231.             int v = adjList[u][i];
  232.             int w = adjMatrix[u][v];
  233.             if (dijkstra[v] > dijkstra[u] + w) {
  234.                 // fprintf(stdout, "found a shorter path for %d : %d\n", v, dijkstra[u] + w);
  235.                 dijkstra[v] = dijkstra[u] + w;
  236.                 pq.push(ii(dijkstra[v], v));
  237.             }
  238.         }
  239.     }
  240.    
  241.    
  242.     // for (int i = 0; i < components; i++) {
  243.     //     fprintf(stdout, "%d: ", i);
  244.     //     for (int j = 0; j < adjList[i].size(); j++) {
  245.     //         fprintf(stdout, "%d - %d, ", adjList[i][j], adjMatrix[i][j]);
  246.     //     }
  247.     //     fprintf(stdout, "\n");
  248.     // }
  249.  
  250.     // for (int i = 0; i < components; i++) {
  251.     //     fprintf(stdout, "corners of component %d:\n", i);
  252.     //     while (!vq[i].empty()) {
  253.     //         fprintf(stdout, "%d %d %d\n", vq[i].front().first, vq[i].front().second.first, vq[i].front().second.second);
  254.     //         vq[i].pop();
  255.     //     }
  256.     // }
  257.     fprintf(stdout, "DAMN, THE ABSCONDER ABSCONDS AGAIN!");
  258.     return 0;
  259. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top