fork download
copy 
  1. /**
  2. I'm employing the very fabric of the universe here!
  3. */
  4. #include<bits/stdc++.h>
  5. #define endl '\n'
  6. #define pb push_back
  7. #define fr first
  8. #define sc second
  9. #define ll long long int
  10. #define bit(idx) idx&(-idx)
  11. #define pll pair<ll, ll>
  12. using namespace std;
  13.  
  14. const ll MAXN = 1e3 + 5;
  15.  
  16. ll n;
  17. pll A[MAXN][MAXN];
  18. char S[MAXN][MAXN];
  19.  
  20. void print(){
  21. 	for(int i = 1; i <= n; i ++){
  22. 		for(int j = 1; j <= n; j ++){
  23. 			cout << S[i][j] << " ";
  24. 		} cout << endl;
  25. 	}
  26. }
  27.  
  28. void rec1(ll bx, ll by, ll nx, ll ny){
  29. 	if(nx - 1 > 0 && A[nx - 1][ny].fr == bx && A[nx - 1][ny].sc == by && S[nx - 1][ny] == '#'){
  30. 		S[nx - 1][ny] = 'D';
  31. 		rec1(bx, by, nx - 1, ny);
  32. 	}
  33. 	if(nx + 1 < n + 1 && A[nx + 1][ny].fr == bx && A[nx + 1][ny].sc == by && S[nx + 1][ny] == '#'){
  34. 		S[nx + 1][ny] = 'U';
  35. 		rec1(bx, by, nx + 1, ny);
  36. 	}
  37. 	if(ny - 1 > 0 && A[nx][ny - 1].fr == bx && A[nx][ny - 1].sc == by && S[nx][ny - 1] == '#'){
  38. 		S[nx][ny - 1] = 'R';
  39. 		rec1(bx, by, nx, ny - 1);
  40. 	}
  41. 	if(ny + 1 < n + 1 && A[nx][ny + 1].fr == bx && A[nx][ny + 1].sc == by && S[nx][ny + 1] == '#'){
  42. 		S[nx][ny + 1] = 'L';
  43. 		rec1(bx, by, nx, ny + 1);
  44. 	}
  45. }
  46.  
  47. bool ok(int x, int y){
  48. 	if(x - 1 > 0 && A[x - 1][y].fr == -1 && A[x - 1][y].sc == -1 && S[x - 1][y] == '#'){
  49. 		S[x][y] = 'U';
  50. 		S[x - 1][y] = 'D';
  51. 		return true;
  52. 	}
  53. 	if(x + 1 < n + 1 && A[x + 1][y].fr == -1 && A[x + 1][y].sc == -1 && S[x + 1][y] == '#'){
  54. 		S[x][y] = 'D';
  55. 		S[x + 1][y] = 'U';
  56. 		return true;
  57. 	}
  58. 	if(y - 1 > 0 && A[x][y - 1].fr == -1 && A[x][y - 1].sc == -1 && S[x][y - 1] == '#'){
  59. 		S[x][y] = 'L';
  60. 		S[x][y - 1] = 'R';
  61. 		return true;
  62. 	}
  63. 	if(y + 1 < n + 1 && A[x][y + 1].fr == -1 && A[x][y + 1].sc == -1 && S[x][y + 1] == '#'){
  64. 		S[x][y] = 'R';
  65. 		S[x][y + 1] = 'L';
  66. 		return true;
  67. 	}
  68. 	return false;
  69. }
  70.  
  71. int main(){
  72. 	ios_base::sync_with_stdio(NULL); cin.tie(); cout.tie();
  73. 	cin >> n;
  74. 	for(int i = 1; i <= n; i ++){
  75. 		for(int j = 1; j <= n; j ++){
  76. 			ll x, y; cin >> x >> y;
  77. 			A[i][j] = {x, y};
  78. 			if(x == i && y == j){
  79. 				S[i][j] = 'X';
  80. 			}
  81. 			else{
  82. 				S[i][j] = '#';
  83. 			}
  84. 		}
  85. 	}
  86. 	print();
  87. 	for(int i = 1; i <= n; i ++){
  88. 		for(int j = 1; j <= n; j ++){
  89. 			if(S[i][j] == 'X'){
  90. 				rec1(i, j, i, j);
  91. 			}
  92. 		}
  93. 	}
  94. 	print();
  95. 	for(int i = 1; i <= n; i ++){
  96. 		for(int j = 1; j <= n; j ++){
  97. 			if(A[i][j].fr == -1 && A[i][j].sc == -1 && S[i][j] == '#'){
  98. 				if(ok(i, j) == false){
  99. 					cout << " INVALID\n";
  100. 					return 0;
  101. 				}
  102. 			}
  103. 		}
  104. 	}
  105. 	for(int i = 1; i <= n; i ++){
  106. 		for(int j = 1; j <= n; j ++){
  107. 			if(S[i][j] == '#'){
  108. 				cout << "INVALID\n";
  109. 				return 0;
  110. 			}
  111. 		}
  112. 	}
  113. 	cout << "VALID\n";
  114. 	for(int i = 1; i <= n; i ++){
  115. 		for(int j = 1; j <= n; j ++){
  116. 			cout << S[i][j];
  117. 		} cout << endl;
  118. 	}
  119. }
  120. /**
  121. 2
  122. 1 1 1 1
  123. 2 2 2 2
  124.  
  125. VALID
  126. XL
  127. RX
  128. ---------
  129. 3
  130. -1 -1 -1 -1 -1 -1
  131. -1 -1  2  2 -1 -1
  132. -1 -1 -1 -1 -1 -1
  133.  
  134. VALID
  135. RRD
  136. UXD
  137. ULL
  138. */
Success #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
VALID
https://ideone.com/OgTmuL
language:
C++14 (gcc 8.3)
created:
4 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!