Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cassert>
- #include <algorithm>
- #include <vector>
- #include <unordered_map>
- #include "optimization.h"
- #include <map>
- #include <unordered_set>
- #define all(a) a.begin(), a.end()
- using namespace std;
- vector<vector<int>> mark;
- vector<vector<int>> matrix;
- bool flag = false;
- int n;
- int m;
- vector<pair<int,int>> result;
- pair<int,int> finish;
- vector<pair<int,int>> w = {{1, 0}, {0,1}, {-1, 0}, {0, -1}};
- void dfs(pair<int,int> start) {
- result.push_back(start);
- if (start == finish) {
- flag = true;
- return;
- }
- mark[start.first][start.second] = 1;
- for (auto [x,y] : w){
- int f1 = x + start.first;
- int f2 = y + start.second;
- if (!flag && f1 >= 0 && f1 < m && f2 >= 0 && f2 < n && matrix[f1][f2] != -1 && mark[f1][f2] == 0){
- dfs({f1,f2});
- }
- }
- if (flag){
- return;
- }
- result.pop_back();
- }
- int main() {
- // cin >> n >> m;
- n = readInt(); m = readInt();
- int a,b;
- // cin >> a >> b;
- a = readInt(); b = readInt();
- pair<int,int> start = {b-1,a-1};
- // cin >> a >> b;
- a = readInt(); b = readInt();
- finish = {b-1,a-1};
- matrix.resize(m, vector<int>(n, -1));
- mark.resize(m, vector<int>(n, 0));
- for (int i = 0; i < m; i++){
- for (int j = 0; j < n; j++){
- char a = readChar();
- // cin >> a;
- if (a == '.'){
- matrix[i][j] = 0;
- }
- }
- }
- dfs(start);
- if (flag){
- // cout << "YES\n";
- writeWord("YES\n");
- for (auto [x,y] : result){
- // cout << y+1 << " " << x + 1 << endl;
- writeInt(y+1, ' ');
- writeInt(x + 1, '\n');
- }
- }
- else{
- // cout << "NO\n";
- writeWord("NO\n");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment