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
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ALA0Hk
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!