• 我的思路是用DFS把所有路记录下来,在用sort后输出,但总是有WA的点
• 难道要BFS输出路径吗,BFS的遍历是有序的
• DFS的遍历是无序的,不撞南墙不回头,
• 求dalao解答

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

#define pii pair<int, int>
using namespace std;
const int N = 20;
int map[N][N];
bool flag[N][N];
int x_1, y_1, x_2, y_2;
queue<pii> q;
int n, m;
int w[4] = {-1, 0, 1, 0}, ww[4] = {0, 1, 0, -1};
vector<pii> Prev;  // 输出路径
int check = 0;


vector<vector<pii> > last;
void dfs(int c_x, int c_y) {
   if (c_x == x_2 - 1 && c_y == y_2 - 1) {
       check = 1;
       last.push_back(Prev);
       return;
   }
   for (int i = 0; i < 4; i++) {
       int x = c_x + w[i], y = c_y + ww[i];
       if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] && !flag[x][y]) {
           flag[x][y] = true;
           Prev.push_back({x, y});
           dfs(x, y);
           flag[x][y] = false;
           Prev.pop_back();
       }
   }
}

int main() {
   cin >> n >> m;
   for (int i = 0; i < n; i++)
       for (int j = 0; j < m; j++)
           cin >> map[i][j];
   cin >> x_1 >> y_1 >> x_2 >> y_2;
   Prev.push_back({x_1 - 1, y_1 - 1});
   dfs(x_1 - 1, y_1 - 1);
   if (check == 0)
       cout << -1 << endl;
   else {
       // sort(last.begin(), last.end());
       for (auto i : last) {
           for (int j = 0; j < i.size(); j++) {
               printf("(%d,%d)", i[j].first + 1, i[j].second + 1);
               if (j + 1 != i.size())
                   cout << "->";
               else
                   cout << endl;
           }
       }
   }
   return 0;
}