fork(5) download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. #include <utility>
  4. #define down 10
  5. #define left -1
  6. #define right 1
  7. #define up -10
  8. using namespace std;
  9.  
  10. void print(int n, int m, int** matrix)
  11. {
  12. 	for (int i = 0; i < n; i++)
  13. 	{
  14. 		for (int j = 0; j < m; j++)
  15. 		{
  16. 			if (matrix[i][j] == 0 || matrix[i][j] == 1)
  17. 				cout << matrix[i][j] << " ";
  18. 			else
  19. 				cout << (char)matrix[i][j] << " ";
  20. 		}
  21. 		cout << endl;
  22. 	}
  23. }
  24.  
  25. bool search(int n, int m, int** matrix, stack<pair<int,int>>& route, int dir)
  26. {
  27. 	pair<int, int> npos = make_pair(dir / 10 + route.top().first, dir % 10 + route.top().second);
  28. 	if (npos.first < 0 || npos.first >= n || npos.second < 0 || npos.second >= m || matrix[npos.first][npos.second] != 0)
  29. 		return false;
  30. 	else
  31. 	{
  32. 		route.push(npos);
  33. 		matrix[npos.first][npos.second] = 1;
  34. 		if (npos.first == n - 1)
  35. 			return true;
  36. 		else
  37. 		{
  38. 			int* priorityDirs;
  39. 			switch (dir)
  40. 			{
  41. 				case down:
  42. 					priorityDirs = new int[3]{left, down, right};
  43. 					break;
  44. 				case left:
  45. 					priorityDirs = new int[3]{left, down, up};
  46. 					break;
  47. 				case right:
  48. 					priorityDirs = new int[3]{down, right, up};
  49. 					break;
  50. 				case up:
  51. 					priorityDirs = new int[3]{left, right, up};
  52. 					break;
  53. 			}
  54. 			bool found = true;
  55. 			for (int i = 0; i < 3; i++)
  56. 			{
  57. 				found = search(n, m, matrix, route, priorityDirs[i]);
  58. 				if (found)
  59. 					return true;
  60. 			}
  61. 			matrix[npos.first][npos.second] = 0;
  62. 			route.pop();
  63. 			return false;
  64. 		}
  65. 	}
  66. }
  67.  
  68. stack<pair<int,int>> findRoute(int n, int m, int** matrix, int begin)
  69. {
  70. 	stack<pair<int,int>> route;
  71. 	route.push(make_pair(0, begin));
  72. 	if (n != 1 && !search(n, m, matrix, route, down))
  73. 		throw -1;
  74. 	return route;
  75. }
  76.  
  77. int main() 
  78. {
  79. 	ios::sync_with_stdio(false);
  80. 	int n, m;
  81. 	scanf("%d%d", &n, &m);
  82. 	int** matrix = new int*[n];
  83. 	for (int i = 0; i < n; i++)
  84. 		matrix[i] = new int[m];
  85. 	for (int i = 0; i < n; i++)
  86. 		for (int j = 0; j < m; j++)
  87. 			scanf("%d", &matrix[i][j]);
  88. 	bool possible = true;
  89. 	int symbol = -1;
  90. 	for (int i = 0; i < m; i++)
  91. 	{
  92. 		if (matrix[0][i] == 0)
  93. 		{
  94. 			symbol++;
  95. 			try
  96. 			{
  97. 				stack<pair<int,int>> route = findRoute(n, m, matrix, i);
  98. 				while (!route.empty())
  99. 				{
  100. 					pair<int, int> pos = route.top();
  101. 					matrix[pos.first][pos.second] = 'a' + symbol;
  102. 					route.pop();
  103. 				}
  104. 			}
  105. 			catch (...)
  106. 			{
  107. 				possible = false;
  108. 				break;
  109. 			}
  110. 		}
  111. 	}
  112. 	cout << (possible ? "YES" : "NO") << endl;
  113. 	/*
  114. 	if (possible)
  115. 		print(n, m, matrix);
  116. 	*/
  117. 	return 0;
  118. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
1 5
0 0 1 1 0
stdout
copy 
YES
https://ideone.com/tyPmML
Лабиринт! (д/з)
language:
C++14 (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!