Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #define MAX 1002
- using namespace std;
- bool matrix[MAX][MAX];
- vector<pair<int, int>> path;
- int w, h, x1, y1, x2, y2;
- bool dfs(int x, int y) {
- if (x == x2 && y == y2) {return 1;} // if v == goal
- matrix[x][y] = 0;
- if(matrix[x + 1][y] != 0)
- if (dfs(x+1,y)) {path.push_back({x + 1, y}) ; return 1; }
- if(matrix[x - 1][y] != 0)
- if (dfs(x-1,y)) {path.push_back({x - 1, y}) ; return 1; }
- if(matrix[x][y + 1] != 0)
- if (dfs(x,y + 1)) {path.push_back({x, y + 1}) ; return 1; }
- if(matrix[x][y - 1] != 0)
- if (dfs(x,y - 1)) {path.push_back({x, y - 1}) ; return 1; }
- return 0;
- }
- int main() {
- cin >> w >> h;
- cin >> x1 >> y1;
- cin >> x2 >> y2;
- char symb;
- for(int i = 1; i <= h; ++i) {
- for(int j = 1; j <= w; ++j) {
- cin >> symb;
- if (symb == '*')
- matrix[j][i] = 0;
- else
- matrix[j][i] = 1;
- }
- }
- for(int i = 0; i <= h + 1; ++i) {
- matrix[0][i] = 0;
- //cout << matrix[0][i];
- }
- for(int i = 0; i <= h + 1; ++i) {
- matrix[w + 1][i] = 0;
- //cout << matrix[h + 1][i];
- }
- for(int i = 0; i <= w + 1; ++i) {
- matrix[i][0] = 0;
- //cout << matrix[i][0];
- }
- for(int i = 0; i <= w + 1; ++i) {
- matrix[i][h + 1] = 0;
- //cout << matrix[i][w + 1];
- }
- if(dfs(x1, y1)) {
- cout << "YES" << "\n";
- path.push_back({x1, y1});
- reverse(path.begin(), path.end());
- for (auto x : path)
- cout << x.first << " " << x.second << " ";
- }
- else cout << "NO" << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement