题解 | 迷宫问题

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <map>
#include <list>
#include <bits/stdc++.h>
using namespace std;

//迷宫数据，给迷宫四周填充一圈为1，避免边界判断，数据越界
int a[105][105];
//访问数据
int vis[105][105] = {0};
//记录路径顺序
vector<pair<int, int> > ans;
//最终答案
vector<pair<int, int> > ans_final;

int h, w;

void dfs(int x, int y) {
    // cout << "(" << x << "," << y << ")" << endl;
  //访问过标记1，入队
    vis[x][y] = 1;
    ans.push_back({x, y});
  //递归终止条件
    if (x == h && y == w) {
        // cout<<x<<' '<<y<<endl;
        if (ans_final.empty()) ans_final = ans;
        return ;
    }
 //dfs搜索
    if (a[x + 1][y] == 0 && !vis[x + 1][y]) {
        dfs(x + 1, y);
    }

    if (a[x - 1][y] == 0 && !vis[x - 1][y]) {
        dfs(x - 1, y);
    }

    if (a[x][y + 1] == 0 && !vis[x][y + 1]) {
        dfs(x, y + 1);
    }

    if (a[x][y - 1] == 0 && !vis[x][y - 1]) {
        dfs(x, y - 1);
    }
   //回溯
    vis[x][y] = 0;
    ans.pop_back();
    return ;
}

int main() {
    // a = vector<vector<int>>(105,vector<int>(105,1));
  //填充
    for (int i = 0; i < 105; i++)
        for (int j = 0; j < 105; j++)
            a[i][j] = 1;

    cin >> h >> w;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            cin >> a[i][j];

    dfs(1, 1);

    for (auto itor : ans_final) {
        cout << "(" << itor.first-1 << "," << itor.second-1 << ")" << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")