API tools faq
paste
bibaboba12345

a` c

bibaboba12345
Sep 7th, 2021
192
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.98 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <string>
  3. #include <random>
  4. #include <vector>
  5. #include <deque>
  6. using namespace std;
  7. const long long MOD = 1e9 + 7, N = 17;
  8. long long matr[52][52], col[52][52], vis[52][52], conn[20][20], d[52][52], n, m, cnt;
  9. bool fl;
  10. char z;
  11. long long dp[1 << 20][20];
  12. vector<pair<int, int>> q;
  13. deque<pair<int, int>> q1;
  14. int check(int mask, int u) {
  15. return mask & (1 << u);
  16. }
  17.  
  18. int main()
  19. {
  20. cin >> n >> m;
  21. for (int i = 0; i < n; i++) {
  22. for (int j = 0; j < m; j++) {
  23. cin >> z;
  24. if (z == 'X') {
  25. matr[i][j] = 1;
  26. }
  27. if (z == 'S') {
  28. matr[i][j] = 0;
  29. }
  30. if (z == '.') {
  31. matr[i][j] = -1;
  32. }
  33. }
  34. }
  35. cnt = 1;
  36. for (int i = 0; i < n; i++) {
  37. for (int j = 0; j < m; j++) {
  38. if (matr[i][j] == 1 && col[i][j] == 0) {
  39. col[i][j] = cnt;
  40. q.clear();
  41. q.push_back({ i,j });
  42. int l = 0;
  43. while (l < q.size()) {
  44. int x = q[l].first;
  45. int y = q[l].second;
  46. col[x][y] = cnt;
  47. if (x > 0) {
  48. if (!vis[x - 1][y] && matr[x - 1][y] > 0) {
  49. q.push_back({ x - 1,y });
  50. vis[x - 1][y] = 1;
  51. }
  52. }
  53. if (y > 0) {
  54. if (!vis[x][y - 1] && matr[x][y - 1] > 0) {
  55. q.push_back({ x,y - 1 });
  56. vis[x][y - 1] = 1;
  57. }
  58. }
  59. if (y < m) {
  60. if (!vis[x][y + 1] && matr[x][y + 1] > 0) {
  61. q.push_back({ x,y + 1 });
  62. vis[x][y + 1] = 1;
  63. }
  64. }
  65. if (x < n) {
  66. if (!vis[x + 1][y] && matr[x + 1][y] > 0) {
  67. q.push_back({ x + 1,y });
  68. vis[x + 1][y] = 1;
  69. }
  70. }
  71. l++;
  72. }
  73. cnt++;
  74. }
  75. }
  76. }
  77.  
  78. for (int i = 0; i < cnt; i++) {
  79. for (int j = 0; j < cnt; j++) {
  80. conn[i][j] = 1e15;
  81. }
  82. }
  83. for (int v = 0; v < cnt - 1; v++) {
  84. q1.clear();
  85. for (int i = 0; i < n; i++) {
  86. for (int j = 0; j < m; j++) {
  87. if (col[i][j] - 1 == v) {
  88. d[i][j] = 0;
  89. q1.push_back({ i,j });
  90. vis[i][j] = 1;
  91. }
  92. else {
  93. d[i][j] = 122;
  94. vis[i][j] = 0;
  95. }
  96. }
  97. }
  98.  
  99. while (!q1.empty()) {
  100. int x = q1.front().first;
  101. int y = q1.front().second;
  102. q1.pop_front();
  103. if (x >= n || y >= m) {
  104. continue;
  105. }
  106. if (x > 0) {
  107. if (matr[x - 1][y] == 0) {
  108. d[x - 1][y] = min(d[x - 1][y], d[x][y] + 1);
  109. if (!vis[x - 1][y]) {
  110. q1.push_back({ x - 1,y });
  111. vis[x - 1][y] = 1;
  112. }
  113. }
  114. if (matr[x - 1][y] == 1) {
  115. d[x - 1][y] = min(d[x - 1][y], d[x][y]);
  116. if (!vis[x - 1][y]) {
  117. q1.push_front({ x - 1,y });
  118. vis[x - 1][y] = 1;
  119. }
  120. }
  121. }
  122. if (y > 0) {
  123. if (matr[x][y - 1] == 0) {
  124. d[x][y - 1] = min(d[x][y - 1], d[x][y] + 1);
  125. if (!vis[x][y - 1]) {
  126. q1.push_back({ x, y - 1 });
  127. vis[x][y - 1] = 1;
  128. }
  129. }
  130. if (matr[x][y - 1] == 1) {
  131. d[x][y - 1] = min(d[x][y - 1], d[x][y]);
  132. if (!vis[x][y - 1]) {
  133. q1.push_front({ x,y - 1 });
  134. vis[x][y - 1] = 1;
  135. }
  136. }
  137. }
  138. if (y < m) {
  139. if (matr[x][y + 1] == 0) {
  140. d[x][y + 1] = min(d[x][y + 1], d[x][y] + 1);
  141. if (!vis[x][y + 1]) {
  142. q1.push_back({ x,y + 1 });
  143. vis[x][y + 1] = 1;
  144. }
  145. }
  146. if (matr[x][y + 1] == 1) {
  147. d[x][y + 1] = min(d[x][y + 1], d[x][y]);
  148. if (!vis[x][y + 1]) {
  149. q1.push_front({ x,y + 1 });
  150. vis[x][y + 1] = 1;
  151. }
  152. }
  153. }
  154. if (x < n) {
  155. if (matr[x + 1][y] == 0) {
  156. d[x + 1][y] = min(d[x + 1][y], d[x][y] + 1);
  157. if (!vis[x + 1][y]) {
  158. q1.push_back({ x + 1,y });
  159. vis[x + 1][y] = 1;
  160. }
  161. }
  162. if (matr[x + 1][y] == 1) {
  163. d[x + 1][y] = min(d[x + 1][y], d[x][y]);
  164. if (!vis[x + 1][y]) {
  165. q1.push_front({ x + 1,y });
  166. vis[x + 1][y] = 1;
  167. }
  168. }
  169. }
  170. }
  171.  
  172. for (int i1 = 0; i1 < n; i1++) {
  173. for (int j1 = 0; j1 < m; j1++) {
  174. if (matr[i1][j1] == 1) {
  175. conn[v][col[i1][j1] - 1] = min(conn[v][col[i1][j1] - 1], d[i1][j1]);
  176. }
  177. }
  178. }
  179. }
  180.  
  181. for (int i = 0; i <= (1 << (cnt)); i++) {
  182. for (int j = 0; j < cnt; j++) {
  183. dp[i][j] = 1e15;
  184. }
  185. }
  186. for (int i = 0; i < cnt - 1; i++) {
  187. dp[1 << i][i] = 0;
  188. }
  189. /*for (int mask = 1; mask < 1 << (cnt); mask++) {
  190. for (int v = 0; v < cnt-1; v++) {
  191. if (check(mask, v)) {
  192. for (int u = 0; u < cnt-1; u++) {
  193. if (!check(mask, u)) {
  194. dp[mask ^ (1 << u)][u] = min(dp[mask ^ (1 << u)][u], dp[mask][v] + conn[u][v]);
  195. }
  196. }
  197. }
  198. }
  199. }*/
  200.  
  201. for (int mask = 1; mask < (1 << (cnt - 1)) - 1; mask++) {
  202. for (int v = 0; v < (cnt - 1); v++) {
  203. if (check(mask, v)) {
  204. for (int u = 0; u < cnt - 1; u++) {
  205. if (!check(mask, u)) {
  206. dp[mask ^ (1 << u)][u] = min(dp[mask ^ (1 << u)][u], dp[mask][v] + conn[v][u]);
  207. }
  208. }
  209. }
  210. }
  211. }
  212.  
  213. long long ans = 1e15;
  214. for (int i = 0; i < cnt - 1; i++) {
  215. ans = min(ans, dp[(1 << (cnt - 1)) - 1][i]);
  216. }
  217.  
  218. cout << ans;
  219. return 0;
  220. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
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!