DD3. 地下迷宫
描述
小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。输入描述
输入包括n+1行:输出描述
如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示;如果不能逃离迷宫,则输出"Can not escape!"。 测试数据保证答案唯一示例1
输入:
4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1
输出:
[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]
C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-10-31
#include <bits/stdc++.h>
using namespace std;
int dirx[] = {-1, 0, 1, 0};
int diry[] = {0, 1, 0, -1};
int value[] = {3, 1, 0, 1};
struct Node {
int x, y;
int p, pre;
Node(int x, int y, int p, int pre = -1) : x(x), y(y), p(p), pre(pre) {}
bool operator < (const Node &other) const {
return p > other.p;
}
};
int main()
{
int n, m, p;
while (cin >> n >> m >> p) {
vector<vector<int> > mp(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x;
cin >> x;
mp[i][j] = x;
}
}
deque<Node> que;
vector<vector<bool> > used(n, vector<bool>(m, false));
que.push_back(Node(0, 0, p));
int head = 0;
used[0][0] = true;
bool f = false;
int ans = 0;
while (!que.empty()) {
if (que.begin() + head == que.end())
break;
auto now = que[head++];
if (now.x == 0 && now.y == m - 1) {
f = true;
ans = head - 1;
break;
}
for (int i = 0; i < 4; i++) {
int tx = now.x + dirx[i], ty = now.y + diry[i];
int tp = now.p - value[i];
if (tx >= 0 && tx < n && ty >= 0 && ty < m && mp[tx][ty] == 1 && !used[tx][ty] && tp >= 0)
que.push_back(Node(tx, ty, tp, head - 1)), used[tx][ty] = true;
}
}
if (!f) {
cout << "Can not escape!" << endl;
} else {
stack<int> st;
while (que[ans].pre != -1)
st.push(que[ans].pre), ans = que[ans].pre;
while (!st.empty())
cout << "[" << que[st.top()].x << "," << que[st.top()].y << "],", st.pop();
cout << "[" << 0 << "," << m - 1 << "]" << endl;
}
}
return 0;
}
C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-10-09
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 15;
const int INF = 0x3f3f3f3f;
const int D[4][3] = {{1, 0, 0}, {0, -1, 1}, {0, 1, 1}, {-1, 0, 3}};
int n, m, p;
int mp[N][N];
int step[N][N];
int pre[N][N];
inline bool inside(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
void dfs(int x, int y, int s) {
for (int d = 0; d < 4; d++) {
int nx = x + D[d][0], ny = y + D[d][1], ns = s + D[d][2];
if (inside(nx, ny) && mp[nx][ny] && ns <= p && ns < step[nx][ny]) {
step[nx][ny] = ns;
pre[nx][ny] = d;
dfs(nx, ny, ns);
}
}
}
void printPath(int x, int y) {
if (x != 0 || y != 0) {
int d = pre[x][y], nx = x - D[d][0], ny = y - D[d][1];
printPath(nx, ny);
}
static bool first = true;
if (!first) { putchar(','); }
printf("[%d,%d]", x, y);
first = false;
}
int main() {
scanf("%d%d%d", &n, &m, &p);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &mp[i][j]);
}
}
if (mp[0][0] == '0' || p < m - 1) {
puts("Can not escape!");
return 0;
}
memset(step, 0x3f, sizeof(step));
dfs(0, 0, 0);
if (step[0][m - 1] == INF) {
puts("Can not escape!");
return 0;
}
printPath(0, m - 1);
putchar('\n');
}
C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-09-08
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
typedef struct Point{
int x;
int y;
}Point;
vector<Point> ans;
int maxp = INT_MIN;
void helper( vector<vector<int> > &maps,int x, int y, int n, int m, int p,vector<Point> &paths){
if(x!=0&&y!=m-1&&p<0){
return;
}
if(x==0&&y==m-1&&p>=0&&p>maxp){
Point point = {x,y};
paths.push_back(point);
ans = paths;
maxp=p;
paths.pop_back();
return;
}
if(x<n-1&&maps[x+1][y]==1){
maps[x][y]=-1;
Point point = {x,y};
paths.push_back(point);
helper(maps,x+1,y,n,m,p,paths);
paths.pop_back();
maps[x][y]=1;
}
if(x>0&&maps[x-1][y]==1){
maps[x][y]=-1;
Point point = {x,y};
paths.push_back(point);
helper(maps,x-1,y,n,m,p-3,paths);
paths.pop_back();
maps[x][y]=1;
}
if(y>0&&maps[x][y-1]==1){
maps[x][y]=-1;
Point point = {x,y};
paths.push_back(point);
helper(maps,x,y-1,n,m,p-1,paths);
paths.pop_back();
maps[x][y]=1;
}
if(y<m-1&&maps[x][y+1]==1){
maps[x][y]=-1;
Point point = {x,y};
paths.push_back(point);
helper(maps,x,y+1,n,m,p-1,paths);
paths.pop_back();
maps[x][y]=1;
}
}
int main(){
int n,m,p;
while(cin>>n>>m>>p){
vector<vector<int> > maps(n,vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>maps[i][j];
}
}
vector<Point> paths;
maxp = INT_MIN;
helper(maps,0,0,n,m,p,paths);
if(maxp==INT_MIN){
cout<<"Can not escape!"<<endl;
}else{
for(int i=0;i<ans.size();i++){
cout<<"["<<ans[i].x<<","<<ans[i].y<<"]";
if(i!=ans.size()-1){
cout<<",";
}else{
cout<<endl;
}
}
}
}
return 0;
}
C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-08-24
#include<iostream>
#include<vector>
using namespace std;
class point
{
public:
int row;
int col;
point():row(0),col(0){}
point(int i,int j):row(i),col(j){}
};
vector<point> result;
int maxP=0;
void process(vector<vector<int>>&grid,int i,int j,vector<point> &res,int P)
{
int rows = grid.size();
int cols = grid[0].size();
if(P<0 && !(i==0&&j==cols-1))
return;
//此路可行
if(i==0&&j==cols-1&&P>=0)
{
if(P>=maxP)
{
maxP = P;
result = res;
}
return;
}
//往左走
if(j-1>=0 && grid[i][j-1]==1)
{
grid[i][j-1] = 0;
res.push_back(point(i,j-1));
process(grid,i,j-1,res,P-1);
grid[i][j-1] = 1;
res.pop_back();
}
//往右走
if(j+1<cols &&grid[i][j+1]==1)
{
grid[i][j+1] = 0;
res.push_back(point(i,j+1));
process(grid,i,j+1,res,P-1);
grid[i][j+1] = 1;
res.pop_back();
}
//往上走
if(i-1>=0 &&grid[i-1][j]==1)
{
grid[i-1][j] = 0;
res.push_back(point(i-1,j));
process(grid,i-1,j,res,P-3);
grid[i-1][j] = 1;
res.pop_back();
}
//往下走
if(i+1<rows &&grid[i+1][j]==1)
{
grid[i+1][j]=0;
res.push_back(point(i+1,j));
process(grid,i+1,j,res,P);
grid[i+1][j]=1;
res.pop_back();
}
}
int main()
{
int n=0,m=0,P=0;
vector<vector<int>>grid;
while(cin>>n>>m>>P)
{
grid.resize(n);
for(int i=0;i<n;++i)
grid[i].resize(m,0);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
cin>>grid[i][j];
vector<point> res;
res.push_back(point(0,0));
process(grid,0,0,res,P);
if(!result.size())
cout<<"Can not escape!"<<endl;
else
{
int len = result.size();
for(int i=0;i<len;++i)
{
if(i<len-1)
cout<<"["<<result[i].row<<","<<result[i].col<<"]"<<",";
else
cout<<"["<<result[i].row<<","<<result[i].col<<"]"<<endl;
}
}
}
}
C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-10-19
#include<iostream>
#include <vector>
#include<deque>
#include <list>
#include<queue>
#include<stack>
#include<algorithm>
#include <iomanip>
#include <functional>
#include <iostream>
#include<cstring>
#include<sstream>
using namespace std;
#define MAX 10
struct node
{
int x, y;
};
int dir[4][2] = { { -1, 0 }, { 1, 0 }, {0,-1}, {0,1} };
int pcons[4] = { -3, 0, -1, -1 };
int map[MAX][MAX];
int n, m, p;
int maxp=-200;
vector<node> minpath;
vector<node> currpath;
void dfs(int x, int y, int p)
{
node nod{ x, y };
map[x][y] = 2;
currpath.push_back(nod);
if (p >=0&&x == 0 && y == m - 1)
{
if (p >= maxp)
{
maxp = p;
minpath = currpath;
}
currpath.pop_back();
map[x][y] = 1;
}
else if (p>0)
{
for (int i = 0; i < 4; i++)
{
int nx = x + dir[i][0];
int ny = y + dir[i][1];
int np = p + pcons[i];
if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&map[nx][ny] == 1)
{
dfs(nx, ny, np);
}
}
currpath.pop_back();
map[x][y] = 1;
}
else{
currpath.pop_back();
map[x][y] = 1;
}
}
int main()
{
while (cin >> n >> m >> p)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin>> map[i][j];
}
}
}
int pnew = p;
dfs(0, 0, pnew);
if (maxp != -200)
{
int i = 0;
for (; i < minpath.size() - 1; i++)
{
cout << "[" << minpath[i].x << "," << minpath[i].y << "],";
}
if (i == minpath.size() - 1)
{
cout << "[" << minpath[i].x << "," << minpath[i].y << "]";
}
}
else
cout << "Can not escape!" << endl;
//system("pause");
return 0;
}