fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef int ll;
  4. ll n;
  5. char a[15][15], b[15][15];
  6. set <char> r[15], c[15];
  7. map <pair<ll,ll>, set <char>> cannot;
  8. void solve(ll x, ll y);
  9. ll f=0;
  10. char temp;
  11. int i=0;
  12. ll leftgret=0, leftsmal=0, upgret=0, upsmal=0;
  13. void backtrack(ll x, ll y)
  14. {
  15.  
  16. if (b[x][y]!='-')
  17. {
  18. if (y==1)
  19. {
  20. backtrack(x-2, 2*n-1);
  21. }
  22. else
  23. {
  24. backtrack(x, y-2);
  25. }
  26. }
  27. else
  28. {
  29. temp=a[x][y];
  30. leftgret=0, leftsmal=0, upgret=0, upsmal=0;
  31. if (y>=1&&a[x][y-1]=='>')
  32. {
  33. leftgret=1;
  34. }
  35. if (y>=1&&a[x][y-1]=='<')
  36. {
  37. leftsmal=1;
  38. }
  39. if (x>=1&&a[x-1][y]=='v')
  40. {
  41. upgret=1;
  42. }
  43. if (x>=1&&a[x-1][y]=='^')
  44. {
  45. upsmal=1;
  46. }
  47. f=0;
  48. for (i = 49; i <49+n ; ++i)
  49. {
  50. if (cannot[{x,y}].find(i) == cannot[{x,y}].end() && r[x].find(i)!=r[x].end()&&c[y].find(i)!=c[y].end()&&((leftgret&&i<a[x][y-2])||!leftgret)&&(!leftsmal||(leftsmal&&i>a[x][y-2]))&&(!upgret||(upgret&&i<a[x-2][y]))&&(!upsmal||(upsmal&&i>a[x-2][y])))
  51. {
  52. f=1;
  53. a[x][y]=i;
  54. r[x].erase(i);
  55. c[y].erase(i);
  56. r[x].insert(temp);
  57. c[y].insert(temp);
  58. cannot[{x, y}].insert(i);
  59. break;
  60. }
  61. }
  62. if (!f)
  63. {
  64. r[x].insert(temp);
  65. c[y].insert(temp);
  66. while(!cannot[{x, y}].empty())
  67. {
  68. cannot[{x, y}].erase(cannot[{x, y}].begin());
  69. }
  70. if (y==1)
  71. {
  72. backtrack(x-2, 2*n-1);
  73. }
  74. else
  75. {
  76.  
  77. backtrack(x, y-2);
  78. }
  79. }
  80. else
  81. {
  82. // while(!cannot[{x, y}].empty())
  83. // {
  84. // cannot[{x, y}].erase(cannot[{x, y}].begin());
  85. // }
  86. if (y==2*n-1)
  87. {
  88. solve(x+2, 1);
  89. }
  90. else
  91. {
  92. solve(x, y+2);
  93. }
  94. }
  95.  
  96. }
  97. return;
  98. }
  99. void solve(ll x, ll y)
  100. {
  101. if (x>2*n-1||y>2*n-1)
  102. {
  103. return;
  104. }
  105. if (b[x][y]=='-')
  106. {
  107. leftgret=0, leftsmal=0, upgret=0, upsmal=0;
  108. if (y>=1&&a[x][y-1]=='>')
  109. {
  110. leftgret=1;
  111. }
  112. if (y>=1&&a[x][y-1]=='<')
  113. {
  114. leftsmal=1;
  115. }
  116. if (x>=1&&a[x-1][y]=='v')
  117. {
  118. upgret=1;
  119. }
  120. if (x>=1&&a[x-1][y]=='^')
  121. {
  122. upsmal=1;
  123. }
  124. f=0;
  125. for (i = 49; i <49+n ; ++i)
  126. {
  127. if (r[x].find(i)!=r[x].end()&&c[y].find(i)!=c[y].end()&&((leftgret&&i<a[x][y-2])||!leftgret)&&(!leftsmal||(leftsmal&&i>a[x][y-2]))&&(!upgret||(upgret&&i<a[x-2][y]))&&(!upsmal||(upsmal&&i>a[x-2][y])))
  128. {
  129. f=1;
  130. a[x][y]=i;
  131. r[x].erase(i);
  132. c[y].erase(i);
  133. break;
  134. }
  135. }
  136.  
  137. if (!f)
  138. {
  139. if (y==1)
  140. {
  141. backtrack(x-2, 2*n-1);
  142. }
  143. else
  144. {
  145. backtrack(x, y-2);
  146. }
  147. }
  148. else
  149. {
  150. if (y==2*n-1)
  151. {
  152. solve(x+2, 1);
  153. }
  154. else
  155. {
  156. solve(x, y+2);
  157. }
  158. }
  159. }
  160. else
  161. {
  162. leftgret=0, leftsmal=0, upgret=0, upsmal=0, f=0;
  163. if (y>=1&&a[x][y-1]=='>')
  164. {
  165. leftgret=1;
  166. }
  167. if (y>=1&&a[x][y-1]=='<')
  168. {
  169. leftsmal=1;
  170. }
  171. if (x>=1&&a[x-1][y]=='v')
  172. {
  173. upgret=1;
  174. }
  175. if (x>=1&&a[x-1][y]=='^')
  176. {
  177. upsmal=1;
  178. }
  179. if (((leftgret&&b[x][y]<a[x][y-2])||!leftgret)&&(!leftsmal||(leftsmal&&b[x][y]>a[x][y-2]))&&(!upgret||(upgret&&b[x][y]<a[x-2][y]))&&(!upsmal||(upsmal&&b[x][y]>a[x-2][y])))
  180. {
  181. f=1;
  182. }
  183. if (!f)
  184. {
  185. if (y==1)
  186. {
  187. backtrack(x-2, 2*n-1);
  188. }
  189. else
  190. {
  191. backtrack(x, y-2);
  192. }
  193. }
  194. else
  195. {
  196. if (y==2*n-1)
  197. {
  198. solve(x+2, 1);
  199. }
  200. else
  201. {
  202. solve(x, y+2);
  203. }
  204. }
  205.  
  206. }
  207. return;
  208.  
  209. }
  210. int main()
  211. {
  212. ios_base::sync_with_stdio(false);
  213. cin.tie(NULL);
  214. cin >> n;
  215. for (int i = 1; i < 2*n; ++i)
  216. {
  217. for (int j = 49; j < n+49; ++j)
  218. {
  219. r[i].insert(j);
  220. c[i].insert(j);
  221.  
  222. }
  223. }
  224. for (int i = 1; i < 2*n; ++i)
  225. {
  226. for (int j = 1; j < 2*n; ++j)
  227. {
  228. cin >> a[i][j];
  229. b[i][j]=a[i][j];
  230. if (a[i][j]<49+n&&a[i][j]>48)
  231. {
  232. cannot[{i,j}].insert(a[i][j]);
  233. r[i].erase(r[i].find(a[i][j]));
  234. c[j].erase(c[j].find(a[i][j]));
  235. }
  236. }
  237. }
  238. solve(1,1);
  239. for(ll i=1; i<2*n; i++)
  240. {
  241. while(!r[i].empty())
  242. {
  243. r[i].erase(r[i].begin());
  244. }
  245.  
  246. while(!c[i].empty())
  247. {
  248. c[i].erase(c[i].begin());
  249. }
  250. }
  251.  
  252. for(ll i=0; i<2*n; i++)
  253. {
  254. for(ll j=0; j<2*n; j++)
  255. {
  256. while(!cannot[{i,j}].empty())
  257. {
  258. cannot[{i,j}].erase(cannot[{i,j}].begin());
  259. }
  260. }
  261. }
  262. for (int i = 1; i < 2*n; i+=2)
  263. {
  264. for (int j = 1; j < 2*n; j+=2)
  265. {
  266. cout << a[i][j];
  267. }
  268. cout <<"\n";
  269. }
  270.  
  271. // cout << flag;
  272. return 0;
  273. }
Success #stdin #stdout 0s 4548KB
stdin
Standard input is empty
stdout
Standard output is empty