fork(4) download
  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
stdin
1 5
0 0 1 1 0
stdout
YES