fork(1) download
copy 
  1. #include <iostream>
  2. #include <cassert>
  3. using namespace std;
  4.  
  5. const int N = 5;
  6. const int M = 5;
  7. char Matrix[N][M];
  8.  
  9. typedef pair<int,int> point;
  10. #define x first
  11. #define y second
  12.  
  13. bool valid(point test){
  14.     return test.x>=0 && test.x < N && test.y >= 0 && test.y < M && Matrix[test.x][test.y];
  15. }
  16.  
  17. point add(point cur,int dir){
  18. 	switch (dir){
  19. 	   case 0: return point(cur.x + 1, cur.y);
  20. 	   case 1: return point(cur.x - 1, cur.y);
  21. 	   case 2: return point(cur.x, cur.y + 1);
  22. 	   case 3: return point(cur.x, cur.y - 1);
  23. 	   default: assert(false); //wrong dir
  24. 	}
  25. }
  26. char Used[N][M];
  27.  
  28. bool dfs(point cur, point goal, int countStep){
  29. 	countStep++;
  30. 	Used[cur.x][cur.y] = 1;
  31. 	for (int i=0;i<4;i++){
  32. 		point nnew = add(cur,i);
  33. 		if (!valid(nnew))
  34. 			continue;
  35. 		if (nnew == goal && countStep>2){
  36. 			cout << "path find, step = " << countStep<<endl;
  37. 			cout << cur.x<<" "<<cur.y<<endl;
  38. 			return true;
  39. 		}
  40. 		if (Used[nnew.x][nnew.y])
  41. 			continue;
  42. 		if (dfs(nnew,goal,countStep)){
  43. 			cout << cur.x<<" "<<cur.y<<endl;
  44. 			return true;
  45. 		}
  46. 	}
  47.    	return false;
  48. }
  49.  
  50. int main() {
  51. 	// Init
  52. 	   Matrix[2][3] = 1;
  53. 	   Matrix[2][2] = 1;
  54. 	   Matrix[1][1] = 1;
  55. 	   Matrix[1][2] = 1;
  56. 	   Matrix[2][1] = 1;
  57. 	//
  58. 	point cur = point(2,3);
  59. 	assert(valid(cur));
  60. 	if (!dfs(cur, cur,0))
  61. 		cout <<"No path"<<endl;
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 3412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
No path
https://ideone.com/5d4nsu
language:
C++ (gcc 8.3)
created:
8 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!