跪求大神教一题动态规划
不记得是滴滴还是哪里的一道笔试题。
m*n的个格子，1代表可以走，0不可以走，
一个机器人从（0,0）走到（0，n-1），机器人本身的能量为p
现在机器人向下走不消耗能量，向上走消耗3个能量，向右走消耗1个能量
问能量p能够支撑机器人到达终点？
跪求大神用java写一个答案~
谢谢了，在线等。
2016-09-25 21:44 华东师大 安卓
关注
全部评论
S12
复旦大学 C++
//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;
}
xiaoguang
阿里巴巴_本地生活饿了么_研发
你要java我就给不了你，就搜索搞搞，不是dp
Earther01
南京邮电大学 C++
这不是滴滴笔试的题么？用dfs暴力就能过..
FINACK
微策略_软件工程师
我发过帖子
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享