Advertisement
Guest User

Untitled

a guest
Sep 24th, 2017
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.93 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <vector>
  5. #include <queue>
  6. #include <math.h>
  7. #include <algorithm>
  8. using namespace std;
  9. typedef pair<int, int> pii;
  10. vector<pii> o_stair1_que;
  11. vector<pii> o_stair2_que;
  12. queue<int> stair1;
  13. queue<int> stair2;
  14. vector<pii> person;
  15. vector<pii> stair;
  16. int fin_t[2];
  17. int map[11][11];
  18. int n;
  19. int n_person;
  20. int ans = 1e9;
  21. int calc_dist(int x1 , int y1, int x2, int y2)
  22. {
  23. return abs(x1 - x2) + abs(y1 - y2);
  24. }
  25. void init()
  26. {
  27. stair.clear();
  28. person.clear();
  29. o_stair1_que.clear();
  30. o_stair2_que.clear();
  31. while (!stair1.empty())
  32. {
  33. stair1.pop();
  34. }
  35. while (!stair2.empty())
  36. {
  37. stair2.pop();
  38. }
  39. memset(map, 0, sizeof(map));
  40. memset(fin_t, 0, sizeof(fin_t));
  41. }
  42. bool comparator(pii x, pii y)
  43. {
  44. return x.second < y.second;
  45. }
  46. void solve(int depth, int s)
  47. {
  48. if (depth == n_person)
  49. {
  50. int val1 = -1;
  51. int val2 = -1;
  52. bool waiting1[10];
  53. bool waiting2[10];
  54. memset(waiting1, false, sizeof(waiting1));
  55. memset(waiting2, false, sizeof(waiting2));
  56. if (!o_stair1_que.empty())
  57. {
  58. vector<pii> stair1_que;
  59. for (int i = 0; i < o_stair1_que.size(); i++)
  60. {
  61. stair1_que.push_back(make_pair(o_stair1_que[i].first, o_stair1_que[i].second));
  62. }
  63. sort(stair1_que.begin(), stair1_que.end(), comparator);
  64. int timE = 0;
  65. int n_stair1 = o_stair1_que.size();
  66. int fin_stair1 = 0;
  67. while (1)
  68. {
  69. vector<pii>::iterator iter;
  70. queue<int> temp;
  71. if (n_stair1 == fin_stair1)
  72. {
  73. break;
  74. }
  75. while (!stair1.empty())
  76. {
  77. if (stair1.front() != timE)
  78. {
  79. temp.push(stair1.front());
  80. }
  81. else
  82. {
  83. if (val1 < stair1.front())
  84. {
  85. val1 = stair1.front();
  86. }
  87. fin_stair1++;
  88. }
  89. stair1.pop();
  90. }
  91. while (!temp.empty())
  92. {
  93. stair1.push(temp.front());
  94. temp.pop();
  95. }
  96. for (iter = stair1_que.begin(); iter != stair1_que.end(); iter++)
  97. {
  98. if ((*iter).second == timE && stair1.size() < 3 && !waiting1[(*iter).first])
  99. {
  100. stair1.push((timE + 1) + fin_t[0]);
  101. }
  102. else if ((*iter).second == timE && stair1.size() < 3 && waiting1[(*iter).first])
  103. {
  104. stair1.push((timE)+fin_t[0]);
  105. }
  106. else if ((*iter).second == timE && stair1.size() == 3)
  107. {
  108. waiting1[(*iter).first] = true;
  109. (*iter).second = stair1.front();
  110. }
  111. }
  112. timE++;
  113. }
  114. }
  115. if (!o_stair2_que.empty())
  116. {
  117. vector<pii> stair2_que;
  118. for (int i = 0; i < o_stair2_que.size(); i++)
  119. {
  120. stair2_que.push_back(make_pair(o_stair2_que[i].first, o_stair2_que[i].second));
  121. }
  122. sort(stair2_que.begin(), stair2_que.end(), comparator);
  123. int timE = 0;
  124. int n_stair2 = o_stair2_que.size();
  125. int fin_stair2= 0;
  126. while (1)
  127. {
  128. vector<pii>::iterator iter;
  129. queue<int> temp;
  130. if (n_stair2 == fin_stair2)
  131. {
  132. break;
  133. }
  134. while (!stair2.empty())
  135. {
  136. if (stair2.front() != timE)
  137. {
  138. temp.push(stair2.front());
  139. }
  140. else
  141. {
  142. if (val2 < stair2.front())
  143. {
  144. val2 = stair2.front();
  145. }
  146. fin_stair2++;
  147. }
  148. stair2.pop();
  149. }
  150. while (!temp.empty())
  151. {
  152. stair2.push(temp.front());
  153. temp.pop();
  154. }
  155. for (iter = stair2_que.begin(); iter != stair2_que.end(); iter++)
  156. {
  157. if ((*iter).second == timE && stair2.size() < 3 && !waiting2[(*iter).first])
  158. {
  159. stair2.push((timE + 1) + fin_t[1]);
  160. }
  161. else if ((*iter).second == timE && stair2.size() < 3 && waiting2[(*iter).first])
  162. {
  163. stair2.push((timE) + fin_t[1]);
  164. }
  165. else if ((*iter).second == timE && stair2.size() == 3)
  166. {
  167. waiting2[(*iter).first] = true;
  168. (*iter).second = stair2.front();
  169. }
  170. }
  171. timE++;
  172. }
  173. }
  174. int max = 0;
  175. if (val1 > val2)
  176. {
  177. max = val1;
  178. }
  179. else
  180. {
  181. max = val2;
  182. }
  183. if (ans > max) ans = max;
  184. return;
  185. }
  186. //0번계단 이용
  187. int dist = calc_dist(person[depth].first, person[depth].second, stair[0].first, stair[0].second);
  188. o_stair1_que.push_back(make_pair(depth, dist));
  189. solve(depth + 1, 0);
  190. o_stair1_que.pop_back();
  191. //1번계단 이용
  192. dist = calc_dist(person[depth].first, person[depth].second, stair[1].first, stair[1].second);
  193. o_stair2_que.push_back(make_pair(depth, dist));
  194. solve(depth + 1, 1);
  195. o_stair2_que.pop_back();
  196. }
  197. int main(void)
  198. {
  199. //freopen("sample_input.txt", "r", stdin);
  200. int tc;
  201. scanf("%d", &tc);
  202. for (int t = 1; t <= tc; t++)
  203. {
  204. scanf("%d", &n);
  205. init();
  206. int idx = 0;
  207. ans = 1e9;
  208. for (int i = 1; i <= n; i++)
  209. {
  210. for (int j = 1; j <= n; j++)
  211. {
  212. int exist;
  213. scanf("%d", &exist);
  214. if (exist == 1)
  215. {
  216. person.push_back(make_pair(i, j));
  217. }
  218. if (exist > 1)
  219. {
  220. stair.push_back(make_pair(i, j));
  221. fin_t[idx++] = exist;
  222. }
  223. }
  224. }
  225. n_person = person.size();
  226. solve(0, 0);
  227. printf("#%d %d\n", t, ans);
  228. }
  229. return 0;
  230. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement