API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jan 26th, 2020
127
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.73 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!