Guest User

Untitled

a guest
Apr 8th, 2017
240
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.81 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FRE(i,a,b) for(i = a; i <= b; i++)
  5. #define FRL(i,a,b) for(i = a; i < b; i++)
  6. #define mem(t, v) memset ((t) , v, sizeof(t))
  7. #define all(x) x.begin(),x.end()
  8. #define un(x) x.erase(unique(all(x)), x.end())
  9. #define sf(n) scanf("%d", &n)
  10. #define sff(a,b) scanf("%d %d", &a, &b)
  11. #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
  12. #define sl(n) scanf("%lld", &n)
  13. #define sll(a,b) scanf("%lld %lld", &a, &b)
  14. #define slll(a,b,c) scanf("%lld %lld %lld", &a, &b, &c)
  15. #define D(x) cerr << #x " = " << (x) << '\n'
  16. #define DBG cerr << "Hi" << '\n'
  17. #define pb push_back
  18. #define PI acos(-1.00)
  19. #define xx first
  20. #define yy second
  21. #define eps 1e-9
  22.  
  23. typedef unsigned long long int ULL;
  24. typedef long long int LL;
  25. typedef pair<int,int> pii;
  26. typedef pair<LL,LL> pll;
  27.  
  28.  
  29. inline int setBit(int N, int pos) { return N=N | (1<<pos); }
  30. inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
  31. inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }
  32.  
  33. //int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
  34. //int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1}; //Four & Eight Direction
  35.  
  36. int ways;
  37. int kx[30], ky[30];
  38.  
  39. bool vis[210][210];
  40. int n, m, filled, options[210][210], distFromCentre[210][210];
  41. pii centre;
  42. vector<pii> sltn;
  43.  
  44. inline bool ok(int r, int c)
  45. {
  46. if(r >= 0 && r < n && c >= 0 && c < m && vis[r][c] == false)
  47. return true;
  48. return false;
  49. }
  50.  
  51. void init()
  52. {
  53. centre.xx = (n+1)/2 - 1;
  54. centre.yy = (m+1)/2 - 1;
  55.  
  56. ways = 0;
  57. for(int x = -3; x<=3; x++)
  58. {
  59. for(int y = -3; y<=3; y++)
  60. {
  61. int sum = abs(x) + abs(y);
  62. if(sum == 2 || sum == 3)
  63. {
  64. kx[ways] = x;
  65. ky[ways] = y;
  66. ways++;
  67. }
  68. }
  69. }
  70. for(int i = 0; i<n; i++)
  71. {
  72. for(int j = 0; j<m; j++)
  73. {
  74. for(int d = 0; d<ways; d++)
  75. {
  76. options[i][j] += ok(i+kx[d], j+ky[d]);
  77. }
  78. distFromCentre[i][j] = abs(centre.xx - i) + abs(centre.yy - j);
  79. }
  80. }
  81. }
  82.  
  83.  
  84. inline bool cmp(pii a, pii b)
  85. {
  86. if(options[a.xx][a.yy] == options[b.xx][b.yy])
  87. {
  88. if(distFromCentre[a.xx][a.yy] < distFromCentre[b.xx][b.yy])
  89. return true;
  90. else
  91. return false;
  92. }
  93. return options[a.xx][a.yy] < options[b.xx][b.yy];
  94. }
  95.  
  96. inline void update(int r, int c, int v)
  97. {
  98. filled += v;
  99. if(v == 1)
  100. vis[r][c] = true;
  101. else
  102. vis[r][c] = false;
  103. for(int d = 0; d<ways; d++)
  104. {
  105. pii nw = {r+kx[d], c+ky[d]};
  106. if(ok(nw.xx,nw.yy))
  107. options[nw.xx][nw.yy] += v;
  108. }
  109. }
  110.  
  111. bool backtrack(int r, int c)
  112. {
  113. // cout << r << " " << c << endl;
  114. update(r,c,1);
  115. vector<pii> nxt;
  116. for(int d = 0; d<ways; d++)
  117. {
  118. pii nw = {r+kx[d], c+ky[d]};
  119. if(ok(nw.xx,nw.yy))
  120. nxt.pb(nw);
  121. }
  122. if(nxt.size() == 0)
  123. {
  124. if(filled == n*m && ((r+c) == 2 || (r+c) == 3))
  125. {
  126. sltn.pb({r,c});
  127. return true;
  128. }
  129. update(r,c,-1);
  130. return false;
  131. }
  132. sort(all(nxt),cmp);
  133. for(int i = 0; i<nxt.size(); i++)
  134. {
  135. if(backtrack(nxt[i].xx, nxt[i].yy))
  136. {
  137. sltn.pb({r,c});
  138. return true;
  139. }
  140. }
  141. update(r,c,-1);
  142. return false;
  143. }
  144.  
  145. int main()
  146. {
  147. //freopen("in.txt","r",stdin);
  148. //freopen("out.txt","w",stdout);
  149. int i, j, cs, t;
  150. sff(n,m);
  151. init();
  152. if(backtrack(0,0))
  153. {
  154.  
  155. for(int i = (int)sltn.size()-1; i>=0; i--)
  156. printf("%d %d\n",sltn[i].xx+1,sltn[i].yy+1);
  157. }
  158. else
  159. puts("-1");
  160. return 0;
  161. }
Add Comment
Please, Sign In to add comment