Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <string>
- #include <map>
- #include <queue>
- #include <stack>
- #include <cstring>
- #include <algorithm>
- #define sc scanf
- #define pr printf
- #define pb push_back
- #define mp std::make_pair
- #define fr first
- #define se second
- using namespace std;
- typedef std::pair<int, int> pii;
- typedef std::pair<double, double> pdd;
- const int MN = 1010;
- const long long M = -(1LL << 50);
- const long long MAX_LONG = std::numeric_limits<long long>::max();
- const long long MIN_LONG = std::numeric_limits<long long>::min() + (1LL << 54);
- const int MAX_INT = std::numeric_limits<int>::max();
- const int MIN_INT = std::numeric_limits<int>::min();
- int n, m;
- int x_1, y_1, x_2, y_2;
- vector< int >g[MN];
- bool u[MN][MN];
- bool flag = false;
- char s[MN][MN];
- vector< pii >path;
- void dfs(int x, int y) {
- if (x < 0 || y < 0 || x >= n || y >= m || u[x][y]) {
- return;
- }
- //pr("%d %d %d\n", x, y, u[x][y]);
- u[x][y] = true;
- if (x + 1 == x_2 && y + 1 == y_2) {
- pr("YES\n");
- flag = true;
- }
- if (!flag)dfs(x - 1, y);
- if (!flag)dfs(x + 1, y);
- if (!flag)dfs(x, y - 1);
- if (!flag)dfs(x, y + 1);
- if (flag) {
- path.pb({x, y});
- }
- /*
- c[x] = cnt;
- for (int i = 0; i < g[x].size(); i++) {
- int to = g[x][i];
- if (!u[to]) {
- dfs(to, x);
- }
- }
- */
- }
- int main() {
- //freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
- //freopen("path.in", "r", stdin); freopen("path.out", "w", stdout);
- sc("%d%d%d%d%d%d", &m, &n, &y_1, &x_1, &y_2, &x_2);
- for (int i = 0; i < n; i++) {
- sc(" %s", s[i]);
- for (int j = 0; j < m; j++) {
- if (s[i][j] == '*') {
- u[i][j] = true;
- }
- }
- }
- /*
- for (int i=0; i < m; i++) {
- int a, b;
- sc("%d%d", &a, &b);
- g[a].pb(b);
- g[b].pb(a);
- }*/
- dfs(--x_1, --y_1);
- if (!flag) {
- pr("NO\n");
- }
- else {
- for (int i = path.size() - 1; i >= 0; i--) {
- pr("%d %d\n", path[i].se + 1, path[i].fr + 1);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment