跪求大神教一题动态规划

我发过帖子

这不是滴滴笔试的题么？用dfs暴力就能过..

你要java我就给不了你，就搜索搞搞，不是dp

//C++语法跟Java蛮像得，凑合着参考下？ #include<iostream> #include<vector> #include<queue> using namespace std; class Axis { public: int row, col; Axis(){} Axis(int r, int c): row(r), col(c){} Axis(const Axis & a): row(a.row), col(a.col){} bool operator==(const Axis & a) const { return (row == a.row) && (col == a.col); } void print() const{ cout << '[' << row << ',' << col << ']'; } Axis left() const { return Axis(row, col - 1); } Axis right()const { return Axis(row, col + 1); } Axis up() const { return Axis(row - 1, col); } Axis down()const { return Axis(row + 1, col); } }; void findPath(vector<vector<int>> &Map, vector<vector<Axis>> &allpaths, vector<Axis> & path, Axis start, Axis end, int p) { path.push_back(start); if (start == end) { allpaths.push_back(path); return; } if (p <= 0) return; Axis left = start.left(); Axis right = start.right(); Axis up = start.up(); Axis down = start.down(); Map[start.row][start.col] = 0; if (left.col >= 0 && (Map[left.row][left.col] == 1)) { findPath(Map, allpaths, path, left, end, p - 1); } if (right.col < Map[0].size() && (Map[right.row][right.col] == 1)) { findPath(Map, allpaths, path, right, end, p - 1); } if (up.row >= 0 && (Map[up.row][up.col] == 1)) { findPath(Map, allpaths, path, up, end, p - 3); } if (down.row < Map.size() && (Map[down.row][down.col] == 1)) { findPath(Map, allpaths, path, down, end, p); } Map[start.row][start.col] = 1; } bool findPath(vector<vector<int>> &Map, vector<Axis> &path, int p) { if (Map.empty()) return false; if (Map[0].empty()) return false; int m = Map[0].size(); vector<vector<Axis>> allpaths; vector<Axis> apath; findPath(Map, allpaths, apath, Axis(0, 0), Axis(0, m - 1), p); if (allpaths.empty())return false; int minSize = 100000, minIndex; for (int i = 0; i < allpaths.size(); ++i) { if (allpaths[i].size() < minSize) { minSize = allpaths[i].size(); minIndex = i; } } path = allpaths[minIndex]; return true; } int main() { int n, m, p; cin >> n >> m >> p; vector<vector<int>> Map(n, vector<int>(m)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> Map[i][j]; vector<Axis> path; bool success = findPath(Map, path, p); if (!success) {cout << "Can not escape!" << endl; return 0;} for (int i = 0; i < path.size(); i++) { path[i].print(); if (i != path.size() - 1) cout << ','; } return 0; }