abdukodir

Untitled

Nov 4th, 2015
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.21 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <vector>
  5. #include <string>
  6. #include <map>
  7. #include <queue>
  8. #include <stack>
  9. #include <cstring>
  10. #include <algorithm>
  11. #define sc scanf
  12. #define pr printf
  13. #define pb push_back
  14. #define mp std::make_pair
  15. #define fr first
  16. #define se second
  17.  
  18. using namespace std;
  19.  
  20. typedef std::pair<int, int> pii;
  21. typedef std::pair<double, double> pdd;
  22.  
  23. const int MN = 1010;
  24. const long long M = -(1LL << 50);
  25. const long long MAX_LONG = std::numeric_limits<long long>::max();
  26. const long long MIN_LONG = std::numeric_limits<long long>::min() + (1LL << 54);
  27. const int MAX_INT = std::numeric_limits<int>::max();
  28. const int MIN_INT = std::numeric_limits<int>::min();
  29.  
  30. int n, m;
  31. int x_1, y_1, x_2, y_2;
  32. vector< int >g[MN];
  33. bool u[MN][MN];
  34. bool flag = false;
  35. char s[MN][MN];
  36. vector< pii >path;
  37.  
  38. void dfs(int x, int y) {
  39. if (x < 0 || y < 0 || x >= n || y >= m || u[x][y]) {
  40. return;
  41. }
  42. //pr("%d %d %d\n", x, y, u[x][y]);
  43. u[x][y] = true;
  44. if (x + 1 == x_2 && y + 1 == y_2) {
  45. pr("YES\n");
  46. flag = true;
  47. }
  48. if (!flag)dfs(x - 1, y);
  49. if (!flag)dfs(x + 1, y);
  50. if (!flag)dfs(x, y - 1);
  51. if (!flag)dfs(x, y + 1);
  52. if (flag) {
  53. path.pb({x, y});
  54. }
  55. /*
  56. c[x] = cnt;
  57. for (int i = 0; i < g[x].size(); i++) {
  58. int to = g[x][i];
  59. if (!u[to]) {
  60. dfs(to, x);
  61. }
  62. }
  63. */
  64. }
  65.  
  66. int main() {
  67. //freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
  68. //freopen("path.in", "r", stdin); freopen("path.out", "w", stdout);
  69. sc("%d%d%d%d%d%d", &m, &n, &y_1, &x_1, &y_2, &x_2);
  70. for (int i = 0; i < n; i++) {
  71. sc(" %s", s[i]);
  72. for (int j = 0; j < m; j++) {
  73. if (s[i][j] == '*') {
  74. u[i][j] = true;
  75. }
  76. }
  77. }
  78. /*
  79. for (int i=0; i < m; i++) {
  80. int a, b;
  81. sc("%d%d", &a, &b);
  82. g[a].pb(b);
  83. g[b].pb(a);
  84. }*/
  85. dfs(--x_1, --y_1);
  86. if (!flag) {
  87. pr("NO\n");
  88. }
  89. else {
  90. for (int i = path.size() - 1; i >= 0; i--) {
  91. pr("%d %d\n", path[i].se + 1, path[i].fr + 1);
  92. }
  93. }
  94. return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment