fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. char grid[25][25];
  6.  
  7. int n, posy, posx;
  8.  
  9. bool sol;
  10.  
  11. bool canMove(int x, int y)
  12. {
  13. 	return (grid[x + 1][y] == '.' && x + 1 < n + 1)
  14. 		|| (grid[x - 1][y] == '.' && x - 1 > 0)
  15. 		|| (grid[x][y + 1] == '.' && y + 1 < n + 1)
  16. 		|| (grid[x][y - 1] == '.' && y - 1 > 0);
  17. }
  18.  
  19. vector<string> ans;
  20. bool valid(int x, int y)
  21. {
  22. 	return x > 0 && x < n + 1 && y > 0 && y < n + 1 && grid[x][y] == '.';
  23. }
  24. bool solve(int x, int y)
  25. {
  26. 	//basecase
  27. 	if(sol)	return 1;
  28. 	if(!canMove(x, y))
  29. 	{
  30. 		for(int i = 1 ; i <= n; ++i)
  31. 			for(int j = 1; j <= n; ++j)
  32. 				if(grid[i][j] == '.')
  33. 					return 0;
  34. 		sol = 1;			
  35. 		return 1;
  36. 	}
  37. 	if(valid(x + 1, y))
  38. 	{
  39. 		int end = n;
  40. 		//Do
  41. 		for(int i = x + 1; i <= n; ++i)
  42. 		{
  43. 			if(valid(i, y))
  44. 			{
  45. 				grid[i][y] = 'x';
  46. 				end = i;
  47. 			}
  48. 			else
  49. 			{
  50. 				break;
  51. 			}
  52. 		}
  53. 		ans.push_back("Down");
  54.  
  55. 		//Recurse
  56. 		if(solve(end, y))
  57. 			return 1;
  58.  
  59. 		//Undo
  60. 		for(int i = end; i > x; --i)
  61. 			grid[i][y] = '.';
  62. 		ans.pop_back();
  63. 	}
  64. 	if(valid(x - 1, y))
  65. 	{
  66. 		int end = 1;
  67. 		//Do
  68. 		for(int i = x - 1; i >= 1; --i)
  69. 		{
  70. 			if(valid(i, y))
  71. 			{
  72. 				grid[i][y] = 'x';
  73. 				end = i;
  74. 			}
  75. 			else
  76. 			{
  77. 				break;
  78. 			}
  79. 		}
  80. 		ans.push_back("UP");
  81.  
  82. 		//Recurse
  83. 		if(solve(end, y))
  84. 			return 1;
  85.  
  86. 		//Undo
  87. 		for(int i = end; i < x; ++i)
  88. 			grid[i][y] = '.';
  89. 		ans.pop_back();
  90. 	}
  91. 	if(valid(x, y + 1))
  92. 	{
  93. 		int end = n;
  94. 		//Do
  95. 		for(int i = y + 1; i <= n; ++i)
  96. 		{
  97. 			if(valid(x, i))
  98. 			{
  99. 				grid[x][i] = 'x';
  100. 				end = i;
  101. 			}
  102. 			else
  103. 			{
  104. 				break;
  105. 			}
  106. 		}
  107. 		ans.push_back("Right");
  108.  
  109. 		//Recurse
  110. 		if(solve(x, end))
  111. 			return 1;
  112.  
  113. 		//Undo
  114. 		for(int i = end; i > y; --i)
  115. 			grid[x][i] = '.';
  116. 		ans.pop_back();
  117. 	}
  118. 	if(valid(x, y - 1))
  119. 	{
  120. 		int end = 1;
  121. 		//Do
  122. 		for(int i = y - 1; i >= 1; --i)
  123. 		{
  124. 			if(valid(x, i))
  125. 			{
  126. 				grid[x][i] = 'x';
  127. 				end = i;
  128. 			}
  129. 			else
  130. 			{
  131. 				break;
  132. 			}
  133. 		}
  134. 		ans.push_back("Left");
  135.  
  136. 		//Recurse
  137. 		if(solve(x, end))
  138. 			return 1;
  139.  
  140. 		//Undo
  141. 		for(int i = end; i < y; ++i)
  142. 			grid[x][i] = '.';
  143. 		ans.pop_back();
  144. 	}
  145. 	return 0;
  146. }
  147. int main()
  148. {
  149. 	cout << "note: this code works on an N*N matrix and is 1-based\n";
  150. 	cout << "enter the grid size \n";
  151. 	cin >> n;
  152. 	cout << "enter the coordinate of the y-axis \n";
  153. 	cin >> posy;
  154. 	cout << "enter the coordinate of the x-axis \n";
  155. 	cin >> posx;
  156. 	//input
  157. 	for(int i = 1 ; i <= n ; ++i)
  158. 		for(int j = 1; j <= n; ++j)
  159. 			cin >> grid[i][j];
  160.  
  161. 	//processing
  162. 	grid[posy][posx] = 'x';
  163. 	solve(posy, posx);
  164.  
  165. 	//output
  166. 	if(ans.size())
  167. 		for(int i = 0 ; i < ans.size(); ++i)
  168. 			cout << ans[i] << " ";
  169. 	else
  170. 		puts("Cant");
  171. 	return 0;
  172. }
Success #stdin #stdout 0s 4808KB
comments (?)
stdin
copy 
6 5 2
..##..
...#..
.#....
......
......
...#..
stdout
copy 
note: this code works on an N*N matrix and is 1-based
enter the grid size 
enter the coordinate of the y-axis 
enter the coordinate of the x-axis 
UP Right Down Left UP Left Down Left UP Right Down Right Down Right UP Left Down
https://ideone.com/AbeS0n
Fancade Game code
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!