fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std; 
  4.  
  5. string path;  
  6. //           	    (x - 1, y)
  7. //   (x, y - 1)      (x, y)        (x, y + 1)
  8. //           	    (x + 1, y)
  9.  
  10. int ans;  
  11. bool visited[8][8];  
  12.  
  13. bool ok(int x, int y) {
  14. 	return (1 <= x && x <= 7 && 1 <= y && y <= 7 && !visited[x][y]); 
  15. }
  16.  
  17. void backtrack(int i, int x, int y) {
  18. 	// tới ô đích nhưng chưa đi đủ 48 bước
  19. 	if (i < 48 && x == 7 && y == 1) return;
  20.  
  21.  	// đã đi đủ 48 bước
  22. 	if (i == 48) {
  23. 		if (x == 7 && y == 1) ans++; 
  24. 		return; 
  25. 	}
  26.  
  27. 	bool ok_left = ok(x, y - 1); 
  28. 	bool ok_right = ok(x, y + 1); 
  29. 	bool ok_up = ok(x - 1, y); 
  30. 	bool ok_down = ok(x + 1, y); 
  31.  
  32.  	// bị chặn trái và phải nhưng có thể đi lên xuống
  33. 	if (!ok_left && !ok_right && ok_up && ok_down) return; 
  34. 	// bị chặn trên dưới nhưng có thể đi trái phải
  35.  	if (!ok_up && !ok_down && ok_left && ok_right) return;  
  36.  
  37. 	visited[x][y] = true;   
  38.  
  39.  	// qua trái
  40. 	if (path[i] == 'L' || path[i] == '?') {
  41. 		if (ok_left) backtrack(i + 1, x, y - 1); 
  42. 	}
  43.  
  44. 	// qua phải
  45. 	if (path[i] == 'R' || path[i] == '?') {
  46. 		if (ok_right) backtrack(i + 1, x, y + 1);  
  47. 	}
  48.  
  49. 	// xuống dưới
  50. 	if (path[i] == 'D' || path[i] == '?') {
  51. 		if (ok_down) backtrack(i + 1, x + 1, y);  
  52. 	}
  53.  
  54. 	// lên trên
  55. 	if (path[i] == 'U' || path[i] == '?') {
  56. 		if (ok_up) backtrack(i + 1, x - 1, y);
  57. 	}
  58.  
  59. 	// bước quay lui
  60. 	visited[x][y] = false; 
  61. }
  62.  
  63. int main() {
  64. 	ios::sync_with_stdio(false); 
  65. 	cin.tie(nullptr); 
  66. 	cin >> path;   
  67. 	ans = 0;   
  68. 	backtrack(0, 1, 1);  
  69. 	cout << ans << '\n'; 
  70. 	return 0; 
  71. }
Success #stdin #stdout 0.06s 5288KB
comments (?)
stdin
copy 
??????R??????U??????????????????????????LD????D?
stdout
copy 
201
https://ideone.com/dRSsr1
language:
C++14 (gcc 8.3)
created:
70 days ago
visibility:
secret

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!