Advertisement
Guest User

Untitled

a guest
Dec 14th, 2014
269
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.26 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/stack:16777216")
  3. #include <string>
  4. #include <vector>
  5. #include <map>
  6. #include <list>
  7. #include <iterator>
  8. #include <set>
  9. #include <queue>
  10. #include <iostream>
  11. #include <sstream>
  12. #include <stack>
  13. #include <deque>
  14. #include <cmath>
  15. #include <memory.h>
  16. #include <cstdlib>
  17. #include <cstdio>
  18. #include <cctype>
  19. #include <algorithm>
  20. #include <utility>
  21. #include <time.h>
  22. using namespace std;
  23.  
  24. #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
  25. #define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
  26. #define REP(i, N) FOR(i, 0, N)
  27. #define RREP(i, N) RFOR(i, N, 0)
  28. #define FILL(A,value) memset(A,value,sizeof(A))
  29.  
  30. #define ALL(V) V.begin(), V.end()
  31. #define SZ(V) (int)V.size()
  32. #define PB push_back
  33. #define MP make_pair
  34. #define Pi 3.14159265358979
  35. #define nice sdagasdgadsg
  36.  
  37. typedef long long Int;
  38. typedef unsigned long long UINT;
  39. typedef vector <int> VI;
  40. typedef pair <int, int> PII;
  41.  
  42. const int INF = 1000000000;
  43. const int MAX = 300007;
  44. const int MAX2 = 7000;
  45. const int BASE = 1000000000;
  46.  
  47.  
  48. int d[207][207];
  49. bool canMove[207][207][4];
  50.  
  51. pair<int,int> q[207 * 207];
  52.  
  53. int main()
  54. {
  55. #ifndef ONLINE_JUDGE
  56. //freopen("in.txt", "r", stdin);
  57. #endif
  58.  
  59. //freopen("domino-on-torus.in" , "r", stdin);
  60. //freopen("domino-on-torus.out", "w",stdout);
  61.  
  62. string s;
  63. cout << "N" << endl;
  64. cin >> s;
  65.  
  66. int n = 10;
  67.  
  68. int x = 0;
  69. int y = 0;
  70.  
  71. FOR(i,0,207)
  72. FOR(j,0,207)
  73. FOR(k,0,4)
  74. canMove[i][j][k] = 1;
  75.  
  76. int iter = 0;
  77.  
  78. while (1)
  79. {
  80. ++iter;
  81.  
  82. if (iter == 1307)throw -1;
  83.  
  84. //cout << x << ' ' << y << ' ' << n << endl;
  85.  
  86. int l = 0;
  87. int r = 1;
  88.  
  89. FOR(i,0,n + 1)
  90. {
  91. FOR(j,0,n + 1)
  92. {
  93. d[i][j] = -1;
  94. }
  95. }
  96.  
  97. d[n - 1][n - 1] = 0;
  98. q[0] = MP(n - 1,n - 1);
  99. while (l < r)
  100. {
  101. int X = q[l].first;
  102. int Y = q[l].second;
  103. ++l;
  104. if (canMove[X][Y][1] && X < n && d[X + 1][Y] == -1)
  105. {
  106. d[X + 1][Y] = d[X][Y] + 1;
  107. q[r++] = MP(X + 1, Y);
  108. }
  109. if (canMove[X][Y][0] && Y < n && d[X][Y + 1] == -1)
  110. {
  111. d[X][Y + 1] = d[X][Y] + 1;
  112. q[r++] = MP(X, Y + 1);
  113. }
  114. if (canMove[X][Y][3] && X > 0 && d[X - 1][Y] == -1)
  115. {
  116. d[X - 1][Y] = d[X][Y] + 1;
  117. q[r++] = MP(X - 1, Y);
  118. }
  119.  
  120. if (canMove[X][Y][2] && Y > 0 && d[X][Y - 1] == -1)
  121. {
  122. d[X][Y - 1] = d[X][Y] + 1;
  123. q[r++] = MP(X, Y - 1);
  124. }
  125. if (d[x][y] != -1) break;
  126. }
  127.  
  128. //if (d[x][y] == -1) throw -1;
  129.  
  130. if (d[x][y] == 0)
  131. {
  132. cout << "N" << endl;
  133. cin >> s;
  134. if (s == "end")
  135. {
  136. return 0;
  137. }
  138. if (s == "ok")
  139. {
  140. ++x;
  141. ++n;
  142. }
  143. if (s == "no")
  144. {
  145. canMove[n - 1][n - 1][1] = false;
  146. canMove[n][n - 1][3] = false;
  147. ++n;
  148. }
  149. }
  150. else
  151. {
  152. if (x < n && canMove[x][y][1] && d[x + 1][y] == d[x][y] - 1)
  153. {
  154. cout << "N" << endl;
  155. cin >> s;
  156. if (s == "ok")
  157. {
  158. ++x;
  159. n = max(n , x + 1);
  160. }
  161. else
  162. {
  163. canMove[x][y][1] = 0;
  164. canMove[x + 1][y][3] = 0;
  165. }
  166. continue;
  167. }
  168.  
  169. if (y < n && canMove[x][y][0] && d[x][y + 1] == d[x][y] - 1)
  170. {
  171. cout << "E" << endl;
  172. cin >> s;
  173. if (s == "ok")
  174. {
  175. ++y;
  176. n = max(n , y + 1);
  177. }
  178. else
  179. {
  180. canMove[x][y][0] = 0;
  181. canMove[x][ y + 1][2] = 0;
  182. }
  183. continue;
  184. }
  185.  
  186.  
  187. if (x > 0 && canMove[x][y][3] && d[x - 1][y] == d[x][y] - 1)
  188. {
  189. cout << "S" << endl;
  190. cin >> s;
  191. if (s == "ok")
  192. {
  193. --x;
  194. //n = max(n , x + 1);
  195. }
  196. else
  197. {
  198. canMove[x][y][3] = 0;
  199. canMove[x - 1][y][1] = 0;
  200. }
  201. continue;
  202. }
  203.  
  204. if (y > 0 && canMove[x][y][2] && d[x][y - 1] == d[x][y] - 1)
  205. {
  206. cout << "W" << endl;
  207. cin >> s;
  208. if (s == "ok")
  209. {
  210. --y;
  211. //n = max(n , x + 1);
  212. }
  213. else
  214. {
  215. canMove[x][y][2] = 0;
  216. canMove[x][y - 1][0] = 0;
  217. }
  218. continue;
  219. }
  220. }
  221.  
  222. }
  223.  
  224. return 0;
  225. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement