题解 | #地下迷宫#

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

const int N = 20;
int n, m, p;
int board[N][N];
bool st[N][N];

int x[4] = {0, 0, 1, -1};
int y[4] = {1, -1, 0, 0};
int r[4] = {1, 1, 0, 3};
// 坐标系的建立方向有讲究 
typedef pair<int, int> PII;


struct mypoint {
    vector<PII> points;
    int cost;
};

vector<mypoint> ans;
vector<PII> list;
void dfs(int i, int j, int p, int cost, vector<PII> list) {
    if (cost > p) return ;
    if (i == 0 && j == m - 1) {
        list.push_back({i, j});
        if (ans.size()) {
            if (cost < ans[0].cost) {
                ans[0].points = list;
                ans[0].cost = cost;
                return ;
            } else
                return ;
        } else ans.push_back({list, cost});

        return ;
    }

    list.push_back({i, j});
    st[i][j] = 1;

    for (int h = 0; h < 4; h++) {
        int x1 = i + x[h];
        int y1 = j + y[h];
        if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m || board[x1][y1] == 0 ||
                st[x1][y1] == 1)
            continue;


        dfs(x1, y1, p, cost + r[h], list);

    }
    list.pop_back();
    st[i][j] = 0;
}

int main() {
    cin >> n >> m >> p;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }

    dfs(0, 0, p, 0, list);
    if (ans.size() == 0) {
        cout << "Can not escape!" << endl;
    } else {
        for (int i = 0; i < ans[0].points.size(); i++) {
            cout << "[" << ans[0].points[i].first << "," << ans[0].points[i].second << "]";
            if (i != ans[0].points.size() - 1) {
                cout << ",";
            }
        }
        cout << endl;
    }


    return 0;

}