[编程题]地下迷宫
- 热度指数：18810 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。
输入描述:
输入包括n+1行:
第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100)
接下来的n行:
每行m个0或者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]
求的是体力消耗最小的路径，直接DFS穷举出所有路径然后找出剩余体力最多的路径即可，注意下边界条件是“体力值为0时还未到达出口则无法到达出口”，达到出口时体力刚好为0是合法的
#include <iostream>
#include <vector>
using namespace std;
int Maze[10][10];
#define VISITED 2
int m, n, P;
int Dir[4][2] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
int Cost[4] = { -1, -1, -3, 0 };
int H = -200;
struct MazePoint
{
MazePoint(int _x, int _y)
:x(_x), y(_y)
{
}
int x, y;
};
vector<MazePoint> PathStack;
vector<MazePoint> MinCostPath;
void PushPoint(int x, int y)
{
PathStack.push_back(MazePoint(x, y));
}
void PopPoint()
{
PathStack.pop_back();
}
void PrintPath(const vector<MazePoint>& Path)
{
for (int i = 0; i < Path.size(); ++i)
{
cout << "[" << Path[i].x << "," << Path[i].y << "]";
if (i < Path.size() - 1)
{
cout << ",";
}
}
}
void Search(int x, int y, int currP)
{
PushPoint(x, y);
Maze[x][y] = VISITED;
if (x == 0 && y == m-1 && currP >= 0)
{
if (currP > H)
{
H = currP;
MinCostPath = PathStack;
}
PopPoint();
Maze[x][y] = 1;
return;
}
if(currP > 0)
{
for (int i = 0; i < 4; ++i)
{
int nx = x + Dir[i][0];
int ny = y + Dir[i][1];
int nP = currP + Cost[i];
if (nx >= 0 && nx < n &&
ny >= 0 && ny < m &&
Maze[nx][ny] == 1)
{
Search(nx, ny, nP);
}
}
}
PopPoint();
Maze[x][y] = 1;
}
int main()
{
cin >> n >> m >> P;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin >> Maze[i][j];
}
}
Search(0, 0, P);
if (H != -200)
{
PrintPath(MinCostPath);
}
else
{
cout << "Can not escape!";
}
return 0;
}
发表于 2017-01-25 13:34:08
回复(1)
暴力搜索！
这道题感觉因为每一步体力根据方向损失固定，所以到某个点，使用步数最少一定损失体力最少，多的步都是浪费体力，所以可以从起点开始广搜，一直最先搜到终点的路径是最剩体力的，如果体力还小于0，就不能到。
n, m, p = [int(x) for x in input().split()]
mat0 = []
for _ in range(n):
mat0.append([int(x) for x in input().split()])
mat1 = [[None for j in range(m)] for i in range(n)]
mat1[0][0] = [0, 0, p] # mat1保存到达[x, y]的前一个点和到达[x, y]剩余的p
route = [[0, 0]]
steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]
flag = True #其实遍历到0，m-1点就可以停止了
while route and flag:
x0, y0 = route.pop(0)
for step in steps:
x1, y1 = x0 + step[0], y0 + step[1]
if 0 <= x1 < n and 0 <= y1 < m and mat0[x1][y1] and mat1[x1][y1] is None:
if step[0] == -1:
new_p = mat1[x0][y0][2] - 3
elif step[0] == 0:
new_p = mat1[x0][y0][2] - 1
else:
new_p = mat1[x0][y0][2]
mat1[x1][y1] = [x0, y0, new_p]
route.append([x1, y1])
if x1==0 and y1==m-1:
flag = False
break
if mat1[0][m-1][2] < 0:
print('Can not escape!')
else:
res = []
x, y = 0, m-1
while [x, y] != [0, 0]:
res.append([x, y])
x, y = mat1[x][y][0], mat1[x][y][1]
res.append([0, 0])
print(','.join(['[{},{}]'.format(x[0], x[1]) for x in res[::-1]]))
编辑于 2018-05-23 18:57:24
回复(1)
//DFS深度搜索，tmp保存路径
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int dp[10][10];
int n,m;
int mymax=0;
vector<pair<int,int> > res;
void myfind(vector<pair<int,int> >& tmp,int x,int y,int p)
{
if(p<0) return;
tmp.push_back(make_pair(x,y));
dp[x][y]=0; //标记已经走过，防止走回头路
if(x==0&&y==m-1)
{
if(p>=mymax)
{
mymax=p;
res=tmp;
}
tmp.pop_back();
return;
}
if(y+1<m&&dp[x][y+1]==1)
myfind(tmp,x,y+1, p-1);
if(x+1<n&&dp[x+1][y]==1)
myfind(tmp,x+1,y, p);
if(x-1>=0&&dp[x-1][y]==1)
myfind(tmp,x-1,y, p-3);
if(y-1>=0&&dp[x][y-1]==1)
myfind(tmp,x,y-1, p-1);
tmp.pop_back();
dp[x][y]=1; //返回上层时，别忘记恢复
}
int main()
{
int p;
while(cin>>n>>m>>p)
{
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
cin>>dp[i][j];
vector<pair<int,int> > tmp;
myfind(tmp,0,0,p);
if(res.size()==0)
cout<<"Can not escape!"<<endl;
else
{
int k;
for(k=0;k<res.size()-1;++k)
cout<<"["<<res[k].first<<","<<res[k].second<<"]"<<",";
cout<<"["<<res[k].first<<","<<res[k].second<<"]"<<endl;
}
}
}
发表于 2017-08-19 10:38:02
回复(1)
回溯算法，标准流程
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input=new Scanner(System.in);
while(input.hasNext()){
int n=input.nextInt();
int m=input.nextInt();
int P=input.nextInt();
int[][] a=new int[n][m];
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
a[i][j]=input.nextInt();
boolean[][] flag=new boolean[n][m];
ArrayList<Integer> path=new ArrayList<>();
if(isTruePath(0,0,P,a,path,flag)){
for(int i=0; i<path.size()-2; i+=2)
System.out.print("["+path.get(i)+","+path.get(i+1)+"]"+",");
System.out.println("["+path.get(path.size()-2)+","+path.get(path.size()-1)+"]");
}else{
System.out.println("Can not escape!");
}
}
}
public static boolean isTruePath(int i, int j, int P, int[][] a, ArrayList<Integer> path, boolean[][] flag){
if(i<0 || i>=a.length || j<0 || j>=a[0].length || P<0 || a[i][j]==0|| flag[i][j]==true)
return false;
flag[i][j]=true;
path.add(i);
path.add(j);
if(i==0 && j==a[0].length-1){
return true;
}
if(isTruePath(i,j-1,P-1,a,path,flag)||
isTruePath(i,j+1,P-1,a,path,flag)||
isTruePath(i-1,j,P-3,a,path,flag)||
isTruePath(i+1,j,P,a,path,flag))
return true;
path.remove(path.size()-1);
path.remove(path.size()-1);
return false;
}
}
编辑于 2018-05-29 20:36:44
回复(0)
上下我的代码，想法就是dfs了~
import java.util.Scanner;
/**
* Created by Olive on 2017/9/14.
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
// n*m迷宫,小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)
// 小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向
// 上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值
int n = in.nextInt();
int m = in.nextInt();
// 剩余体力值
int power = in.nextInt();
int[][] maze = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++)
maze[i][j] = in.nextInt();
}
System.out.println(pathOut(n , m, maze, power));
}
}
static String path = "";
public static String pathOut(int n, int m, int[][] maze, int power){
if(n <= 0)
return "Can not escape!";
boolean[][] visited = new boolean[n][m];
findPath(n, m, maze, 0, 0, "", visited, power);
return path;
}
public static void findPath(int n, int m, int[][] maze, int nowx, int nowy, String res, boolean[][] visited, int power){
if(nowx == 0 && nowy == m - 1 && maze[0][m - 1] == 1){
if(power >= 0)
path = res + "[0," + (m - 1) + "]";
else
path = "Can not escape!";
return;
}
if(nowx < n && nowy < m && nowx >= 0 && nowy >= 0 && maze[nowx][nowy] == 1 && !visited[nowx][nowy]){
visited[nowx][nowy] = true;
res += "[" + nowx + "," + nowy + "],";
// 水平向右
findPath(n, m, maze, nowx, nowy + 1, res, visited, power - 1);
// 向下
findPath(n, m, maze, nowx + 1, nowy, res, visited, power);
// 水平向左
findPath(n, m, maze, nowx, nowy - 1, res, visited, power - 1);
// 向上
findPath(n, m, maze, nowx - 1, nowy, res, visited, power - 3);
}
}
}
发表于 2017-09-14 20:03:00
回复(0)
题目不难，这里用的方法比较笨，完全递归了所有路径，如果当前体力已经不足，则提前跳出当前路径。
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
private static int m = 0, n = 0, minCost = Integer.MAX_VALUE, p = 0;
private static LinkedList<Point> linkedList = new LinkedList<>();
private static String path = "";
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
p = in.nextInt();
int[][] map = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = in.nextInt();
}
}
generate(map, 0, 0, 0);
if (minCost == Integer.MAX_VALUE) {
System.out.println("Can not escape!");
} else {
System.out.println(path.substring(0,path.length()-1));
}
}
private static void generate(int[][] map, int x, int y, int currentCost) {
if (currentCost > p) return;
map[x][y] = 2;
linkedList.offer(new Point(x, y));
if (x == 0 && y == m - 1) {
if (currentCost < minCost){
minCost = currentCost;
savePath();
}
map[x][y] = 1;
linkedList.removeLast();
return;
}
if (x < n - 1 && map[x + 1][y] == 1) {//down
generate(map, x + 1, y, currentCost);
}
if (x > 0 && map[x - 1][y] == 1) {//up
generate(map, x - 1, y, currentCost + 3);
}
if (y < m - 1 && map[x][y + 1] == 1) {//right
generate(map, x, y + 1, currentCost + 1);
}
if (y > 0 && map[x][y - 1] == 1) {//left
generate(map, x, y - 1, currentCost + 1);
}
map[x][y] = 1;
linkedList.removeLast();
}
private static void savePath() {
Iterator<Point> iterator = linkedList.iterator();
StringBuilder sb = new StringBuilder();
while (iterator.hasNext()) {
Point point = iterator.next();
sb.append("[").append(point.x).append(",").append(point.y).append("],");
}
path = sb.toString();
}
private static class Point {
int x = 0;
int y = 0;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
发表于 2017-04-04 11:23:35
回复(0)
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
struct Position
{
int row;
int col;
};
int main(){
//n行，m列
int n,m;
//体力
int health;
scanf("%d %d %d",&n,&m,&health);
//迷宫的大小
int** grid = new int*[n+2];
for(int i = 0;i<n+2;++i)
grid[i] = new int[m+2];
for(int i = 0;i<n+2;++i){
grid[i][0] = grid[i][m+1] = 0;//左边和右边添加障碍物
}
for(int i = 0;i<m+2;++i){
grid[0][i] = grid[n+1][i] = 0;//上边和下边添加障碍物
}
//接收数据
for(int j = 1;j<n+1;++j)
for(int i = 1;i<m+1;++i)
scanf("%d",&grid[j][i]);
//算法
Position offset[4];
offset[0].row = 0;offset[0].col = 1;
offset[1].row = 1;offset[1].col = 0;
offset[2].row = 0;offset[2].col = -1;
offset[3].row = -1;offset[3].col = 0;
Position here;
here.col = here.row = 1;//起点
Position finish;//终点
finish.row = 1;
finish.col = m;
grid[here.row][here.col] = 2;
int numbers = 4;//四个方向
//对可到达的位置做标记
queue<Position> q;
Position nbr;
do
{
//给相邻位置做标记
for (int i = 0;i<numbers;++i)
{
//检查相邻位置
nbr.row = here.row + offset[i].row;
nbr.col = here.col + offset[i].col;
if(grid[nbr.row][nbr.col] == 1){
//对不可标记的nbr做标记
grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;
if((nbr.row == finish.row) && (nbr.col == finish.col))
break;
//把后者插入队列
q.push(nbr);
}
}
//是否到达终点
if((nbr.row == finish.row) && (nbr.col == finish.col))
break;
//终点不可到达，可以移到nbr么
if(q.empty()){
cout<<"Can not escape!";
return 0;
}
here = q.front();
q.pop();
} while (true);
//构造路径
int pathLength = grid[finish.row][finish.col] - 2;
Position* path = new Position[pathLength];
//从终点回溯
here = finish;
for (int j = pathLength - 1;j>=0;--j)
{
path[j] = here;
//寻找最合适的祖先位置,往下扣3滴血，左右扣1滴血，往上不扣血
if(grid[here.row-1][here.col] == j+2){//往上走
health = health;
here.row = here.row - 1;
}
else
if(grid[here.row][here.col+1] == j+2){//往左走
health -= 1;
here.col = here.col+1;
}
else
if(grid[here.row][here.col-1] == j+2){//往右走
health -= 1;
here.col = here.col-1;
}
else//往下走
{
health -= 3;
here.row = here.row + 1;
}
if(health < 0){
cout<<"Can not escape!";
return 0;
}
}
//输出路径
cout<<"["<<0<<","<<0<<"]"<<",";
for (int i = 0;i<pathLength-1;++i)
{
cout<<"["<<path[i].row-1<<","<<path[i].col-1<<"]"<<",";
}
cout<<"["<<0<<","<<m-1<<"]";
return 0;
}
发表于 2017-02-08 21:58:51
回复(0)
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int n, m, k;
int board[10][10];
bool visited[10][10];
int res = INT_MAX, tempRes = 0;
vector<vector<int>> path;
vector<vector<int>> temp;
void dfs(int i, int j){
if(i == 0 && j == m - 1){
temp.push_back({i, j});
if(tempRes < res){
path = temp;
res = tempRes;
}
temp.pop_back();
return;
}
if(visited[i][j] == true || board[i][j] == 0){
return;
}
visited[i][j] = true;
temp.push_back({i, j});
for(int idx = 0; idx < 4; idx++){
int newI = i + dirs[idx][0];
int newJ = j + dirs[idx][1];
if(newI >= 0 && newI < n && newJ >= 0 && newJ < m){
if(idx == 0){
tempRes += 3;
dfs(newI, newJ);
tempRes -= 3;
}
else if(idx == 2 || idx == 3){
tempRes += 1;
dfs(newI, newJ);
tempRes -= 1;
}
else{
dfs(newI, newJ);
}
}
}
visited[i][j] = false;
temp.pop_back();
}
int main(){
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> board[i][j];
}
}
dfs(0, 0);
if(res <= k){
for(int i = 0; i < path.size() - 1; i++){
cout << "[" << path[i][0] << "," << path[i][1] << "],";
}
cout << "[" << path.back()[0] << "," << path.back()[1] << "]" << endl;
}
else{
cout << "Can not escape!" << endl;
}
return 0;
}
发表于 2021-12-02 18:15:30
回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
typedef struct Position
{
int row;
int col;
}Pos;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//栈创建
typedef Pos STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}Stack;
void StackInit(Stack* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;//初始给0，top指向栈顶元素的下一个；
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = x;
ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//栈空了，直接终止报错
ps->top--;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//栈空了，直接终止报错
return ps->a[ps->top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//迷宫主程序
Stack path;
Stack minpath;
//判断是否有通路
bool IsPass(int** Maze, int N, int M, Pos next)
{
if (next.col >= 0 && next.col < M && next.row >= 0 && next.row < N && Maze[next.row][next.col] == 1)
return true;
else
return false;
}
//深拷贝
void StackCopy(Stack* dest, Stack* source)
{
dest->a = (STDataType*)malloc(sizeof(STDataType) * source->capacity);
memcpy(dest->a, source->a, sizeof(STDataType) * source->top);
dest->capacity = source->capacity;
dest->top = source->top;
}
//判断是否有到终点的路
void GetMazePath(int** Maze, int N, int M, Pos cur, int P)
{
StackPush(&path, cur);
//判断是否到出口
if (cur.col == M - 1 && cur.row == 0 && P>= 0)//到达出口必须要有充足体力
{
if (StackEmpty(&minpath) || StackSize(&path) < StackSize(&minpath))//要么minpath为空，要么path比minpath要小
{
//深拷贝
StackDestory(&minpath);
StackCopy(&minpath, &path);
}
}
Pos next;
//将走过的地方置2，防止重走
Maze[cur.row][cur.col] = 2;
//探测上下左右四个方向
//上
next = cur;
next.row -= 1;
if (IsPass(Maze, N, M, next))
{
//如果有通路将继续递归
GetMazePath(Maze, N, M, next, P-3);
}
//下
next = cur;
next.row += 1;
if (IsPass(Maze, N, M, next))
{
GetMazePath(Maze, N, M, next, P);
}
//左
next = cur;
next.col -= 1;
if (IsPass(Maze, N, M, next))
{
GetMazePath(Maze, N, M, next,P-1);
}
//右
next = cur;
next.col += 1;
if (IsPass(Maze, N, M, next))
{
GetMazePath(Maze, N, M, next,P-1);
}
//回溯的过程中将走过的路程重新恢复
Maze[cur.row][cur.col] = 1;
//当走到思路，将走错的坐标删除
StackPop(&path);
}
//采用栈储存路径
//由于先进后出，栈顶为出口，栈底为入口，需要反过来
//所以再创建一个栈将数据倒过来再输出
void PrintPath(Stack* ps)
{
Stack rPath;
StackInit(&rPath);
while (!StackEmpty(ps))
{
StackPush(&rPath, StackTop(ps));
StackPop(ps);
}
while (StackSize(&rPath)>1)
{
Pos top = StackTop(&rPath);
printf("[%d,%d],", top.row, top.col);
StackPop(&rPath);
}
//最后一个输出后边没有“，”,所以单独拎出来输出
Pos top = StackTop(&rPath);
printf("[%d,%d]\n", top.row, top.col);
StackPop(&rPath);
StackDestory(&rPath);
}
int main()
{
int N = 0, M = 0, P = 0;
while (scanf("%d%d%d", &N, &M, &P) != EOF)
{
//创建迷宫
//先创建行坐标
//由于是二位数组，先创建一个含有N个数组指针的指针数组，指针数组储存的是指针，所以指向这个指针数组的指针为二级指针
//指针数组中每个指针都为数组指针，每个数组指针指向的数组为每一行
int** Maze = (int**)malloc(sizeof(int*) * N);
for (int i = 0; i < N; i++)
{
//Maze[i]就是int*，是一个指针，开辟的空间储存int
Maze[i] = (int*)malloc(sizeof(int) * M);
}
//输入迷宫
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
scanf("%d", &Maze[i][j]);
}
}
//初始化栈
StackInit(&path);
StackInit(&minpath);
//定起点
Pos entry = { 0,0 };
GetMazePath(Maze, N, M, entry, P);
if (!StackEmpty(&minpath))
{
PrintPath(&minpath);
}
else
{
printf("Can not escape!\n");
}
StackDestory(&minpath);
StackDestory(&path);
for (int i = 0; i < N; i++)
{
free(Maze[i]);
}
free(Maze);
Maze = NULL;
}
return 0;
}
编辑于 2021-07-12 17:46:24
回复(0)
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> gpath;
int max_life = -1;
void dfs(vector<vector<int>> &g, vector<vector<int>> &visited, int x, int y, int life, vector<pair<int, int>> &path) {
if (x < 0 || x >= g.size() || y < 0 || y >= g[0].size() || g[x][y] == 0 ||visited[x][y] || life < 0) {
return;
}
path.push_back(make_pair(x, y));
if (x == 0 && y == g[0].size() - 1) {
if (life > max_life) {
gpath = path;
max_life = life;
}
path.pop_back();
return;
}
visited[x][y] = 1;
dfs(g, visited, x + 1, y, life, path);
dfs(g, visited, x - 1, y, life - 3, path);
dfs(g, visited, x, y + 1, life - 1, path);
dfs(g, visited, x, y - 1, life - 1, path);
path.pop_back();
visited[x][y] = 0;
}
void show_path(vector<pair<int, int>> &path) {
for (int i = 0; i < path.size(); ++i) {
cout << '[' << path[i].first << ',' << path[i].second << ']';
if (i < path.size() - 1) {
cout << ',';
}
}
}
int main() {
int n, m, life;
cin >> n >> m >> life;
vector<vector<int>> grids(n, vector<int>(m));
vector<pair<int, int>> path;
vector<vector<int>> visited(n, vector<int>(m, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grids[i][j];
}
}
dfs(grids, visited, 0, 0, life, path);
if (!gpath.empty()) {
show_path(gpath);
} else {
cout << "Can not escape!" << endl;
}
return 0;
}
发表于 2021-07-07 22:20:45
回复(0)
'''引用@rober 大佬的框架改写如下'''n,m,p = [int(x) for x in input().split()] def dfs(grid,visited,path,i,j,p): path.append([i,j]) if i == 0 and j == m - 1: return visited[i][j] = True if i-1>=0 and grid[i-1][j] and visited[i-1][j]==0 and p>=0: dfs(grid,visited,path,i-1,j,p) if j-1>=0 and grid[i][j-1] and visited[i][j-1]==0 and p-1>=0: dfs(grid,visited,path,i,j-1,p-1) if j+1=0: dfs(grid,visited,path,i,j+1,p-1) if i+1=0: dfs(grid,visited,path,i+1,j,p-3) if path[-1][0]==0 and path[-1][1]==m-1: return path.pop() grid = [] for i in range(n): grid.append([int(x) for x in input().split()]) visited = [[False for i in range(m)] for i in range(n)] path = [] dfs(grid,visited,path,0,0,p) if path and path[-1][0]==0 and path[-1][1]==m-1: res = '' for i in path: res += '['+str(i[0])+','+str(i[1])+']'+',' print(res[:-1]) else: print('Can not escape!')
编辑于 2018-08-19 19:29:22
回复(0)
利用优先队列的bfs。节点设置一个step属性，记录的是走到这个位置所需的最少体力，以这个属性在优先队列中排序。其他处理和普通的宽度遍历一样，下面上代码
package 校招真题2017;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
public class 地下迷宫2 {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int m=scan.nextInt();
int p=scan.nextInt();
int[][] map=new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
map[i][j]=scan.nextInt();
}
}
boolean[][] seen=new boolean[n][m];
PriorityQueue queue=new PriorityQueue();
queue.add(new Node(0,0,0,null));
while(!queue.isEmpty()){
Node tmp=queue.poll();
int row=tmp.row;
int col=tmp.col;
if(seen[row][col]){
continue;
}else{
seen[row][col]=true;
}
if(row==0&&col==m-1){
if(tmp.step>p){
System.out.println("Can not escape!");
return;
}
Node current=tmp;
Stack stack=new Stack();
while(current!=null){
stack.add(current);
current=current.prev;
}
while(stack.size()!=1){
Node nn=stack.pop();
System.out.print("["+nn.row+","+nn.col+"],");
}
Node nn=stack.pop();
System.out.print("["+nn.row+","+nn.col+"]");
}
//down
if(row+1<n&&map[row+1][col]==1){
queue.add(new Node(row+1,col,tmp.step,tmp));
}
//up
if(row-1>=0&&map[row-1][col]==1){
queue.add(new Node(row-1,col,tmp.step+3,tmp));
}
if(col+1<m&&map[row][col+1]==1){
queue.add(new Node(row,col+1,tmp.step+1,tmp));
}
if(col-1>=0&&map[row][col-1]==1){
queue.add(new Node(row,col-1,tmp.step+1,tmp));
}
}
}
public static class Node implements Comparable{
int row;
int col;
int step;
Node prev;
public Node(int row, int col, int step,Node prev) {
this.row = row;
this.col = col;
this.step = step;
this.prev=prev;
}
public int compareTo(Node o) {
if(this.step>o.step){
return 1;
}else if(this.step<o.step){
return -1;
}else{
return 0;
}
}
}
}
编辑于 2018-08-03 15:32:50
回复(0)
//优先往右，上，下，左顺序，往上时要判断移动到的位置是否是上一步走过的位置
//不可避免的情况是，往右是个死胡同，所以如果依靠往左折回去，要恢复其重复的体力
#include <iostream>
#include <vector>
using namespace std;
struct Point{
Point(int a, int b){
x = a;
y = b;
};
int x;
int y;
};
int main()
{
//读入数据
int n,m,p;
cin >> n >> m >> p;
int ** data = new int*[n];
for(int i = 0; i < m; i++)
data[i] = new int[m];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> data[i][j];
vector<Point> pt;
pt.push_back(Point(0,0));
while(p > 0)
{
if(pt[pt.size() - 1].x == 0 && pt[pt.size() - 1].y == m-1)//如果走到出口，退出
break;
int len = pt.size();
if(pt[len-1].y + 1 < m && data[pt[len-1].x][pt[len-1].y + 1])//往右
{
pt.push_back(Point(pt[len-1].x, pt[len-1].y + 1));
p -= 1;
continue;
}
if(pt[len-1].x - 1 >= 0 && data[pt[len-1].x - 1][pt[len-1].y])//往上
{
if(!(len-2 >= 0 && pt[len-1].x - 1 == pt[len-2].x && pt[len-1].y == pt[len-2].y))//移动的位置与上上个位置不能相同
{
pt.push_back(Point(pt[len-1].x - 1, pt[len-1].y));
p -= 3;
continue;
}
}
if(pt[len-1].x + 1 < n && data[pt[len-1].x + 1][pt[len-1].y])//往下
{
pt.push_back(Point(pt[len-1].x + 1, pt[len-1].y));
continue;
}
if(pt[len-1].y - 1 >= 0 && data[pt[len-1].x][pt[len-1].y - 1])//往左
{
pt.push_back(Point(pt[len-1].x, pt[len-1].y - 1));
p -= 1;
continue;
}
}
//没体力或者没到最到出口
if(p < 0 || !(pt[pt.size() - 1].x == 0 && pt[pt.size() - 1].y == m-1))
{
cout << "Can not escape!" << endl;
return 0;
}
for(int i = 0; i < pt.size(); i++)
{
cout << "[" << pt[i].x << "," << pt[i].y << "]";
if(i != pt.size() - 1)
cout << ",";
}
return 0;
}
发表于 2018-07-28 12:17:02
回复(0)
回溯思想 + 贪心算法
import java.util.ArrayList;
import java.util.Scanner;
/*
* 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]
*/
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int p = sc.nextInt();
int [][] arr = new int[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
arr[i][j] = sc.nextInt();
//x、y设为起点
int x=0,y=0;
//用两个list，放走过的坐标
ArrayList<Integer> xlist = new ArrayList<>();
ArrayList<Integer> ylist = new ArrayList<>();
int i=0;
if(fun(x,y,n,m,p,xlist,ylist,arr)) {
while(true) {
if(i<xlist.size())
System.out.print("["+xlist.get(i)+","+ylist.get(i)+"]");
else
break;
i++;
if(i<xlist.size())
System.out.print(",");
}
}else
System.out.println("Can not escape!");
}
private static boolean fun(int x, int y, int n, int m, int p, ArrayList<Integer> xlist, ArrayList<Integer> ylist,
int[][] arr) {
if(x<0||x>=n||y<0||y>=m||arr[x][y]!=1||p<0)
return false;
//走过的坐标，赋为-1
arr[x][y] = -1;
xlist.add(x);
ylist.add(y);
if(x==0&&y==m-1)
return true;
//贪心策略
if(!fun(x-1,y,n,m,p,xlist,ylist,arr))
if(!fun(x,y+1,n,m,p-1,xlist,ylist,arr))
if(!fun(x+1,y,n,m,p-3,xlist,ylist,arr))
if(!fun(x,y-1,n,m,p-1,xlist,ylist,arr)) {
//回溯回退，对应坐标赋为0，并且从list中移除
arr[x][y] = 0;
xlist.remove(xlist.size()-1);
ylist.remove(ylist.size()-1);
return false;
}
else {
return true;
}
else {
return true;
}
else {
return true;
}
else
return true;
}
}
发表于 2018-07-25 17:49:07
回复(0)
# -*- coding: utf8 -*-
def isValid(matrix,n,m,p,x,y,visited):
isvisit=(x*m+y in visited) #是否访问
isvalid=(0<=x<n and 0<=y<m) and matrix[x][y]==1#是否通路
hasp=(p>=0)#是否有剩余能量值
return not isvisit and isvalid and hasp #是否可走
def getPath(matrix, n, m, p, x, y, visited, path):
if (x, y) == (0, m - 1):
return True
else:
nextpos=[(x,y+1,p-1),(x-1,y,p-3),(x,y-1,p-1),(x+1,y,p)]
#向右，向上，向左，向下 (贪心思想，尽可能以最小的消耗靠近终点--右上角
for nextx,nexty,nextp in nextpos:
if isValid(matrix,n,m,nextp,nextx,nexty,visited):
path.append([nextx,nexty])
visited.add(nextx * m + nexty)
if getPath(matrix, n, m, nextp,nextx,nexty, visited, path):
return True
path.pop(-1)
visited.remove(nextx * m + nexty)
return False
if __name__ == "__main__":
n, m, p = map(int, raw_input().split(' '))
matrix = []
for i in range(n):
matrix.append(map(int, raw_input().split(' ')))
visited = set()
path = [[0, 0]]
if getPath(matrix, n, m, p, 0, 0, visited, path):
print ','.join(map(str, path)).replace(' ', '')
else:
print "Can not escape!"
编辑于 2018-07-16 12:13:53
回复(1)
- 内存432k，耗时3ms
- 思路是广搜，利用两个队列记录搜索的点和路径，并且剪枝防止下一步往回走
- 可以看我的博文
#include<iostream>
#include<queue>
#include<vector>
#include<string>
using namespace std;
void ShowPath(const vector<pair<int, int>>& path){
int len=path.size();
for(int i=0; i<len-1; i++){
cout<<"["<<path[i].first<<","<<path[i].second<<"],";
}
cout<<"["<<path[len-1].first<<","<<path[len-1].second<<"]";
}
int up=3;
int down=0;
int horizon=1;
int main(){
int n,m,P;
while(cin>>n>>m>>P){
vector<vector<int>> maze(n, vector<int>(m, 0));
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin>>maze[i][j];
}
}
vector<pair<int, int>> best_path;
int minP = P+1;
queue<vector<int>> q;
queue<vector<pair<int, int>>> path_q;
// {x, y, p, from_direction}
// from_direction:up-0, left-1, right-2, down-3
q.push({0, 0, 0, 0});
path_q.push({ {0, 0} });
while(!q.empty()){
// 取出最先加到队列的坐标
vector<int> node = q.front();
vector<pair<int, int>> current_path = path_q.front();
q.pop();
path_q.pop();
// 判断当前点是否是终点，记录最佳路径
if(node[0]==0 && node[1]==m-1 && node[2]<=P){
if(node[2]<minP){
best_path = current_path;
minP = node[2];
}
continue;
}
// 判断当前是否还有体力
if(node[2]>=P) continue;
// 向下走一步
if(node[0]+1<n && node[3]!=3){
if(maze[node[0]+1][node[1]]==1){
q.push({node[0]+1, node[1], node[2]+down, 0});
current_path.push_back({node[0]+1, node[1]});
path_q.push(current_path);
current_path.pop_back();
}
}
// 向右走一步
if(node[1]+1<m && node[3]!=2){
if(maze[node[0]][node[1]+1]==1){
q.push({node[0], node[1]+1, node[2]+horizon, 1});
current_path.push_back({node[0], node[1]+1});
path_q.push(current_path);
current_path.pop_back();
}
}
// 向左走一步
if(node[1]-1>=0 && node[3]!=1){
if(maze[node[0]][node[1]-1]==1){
q.push({node[0], node[1]-1, node[2]+horizon, 2});
current_path.push_back({node[0], node[1]-1});
path_q.push(current_path);
current_path.pop_back();
}
}
// 向上走一步
if(node[0]-1>=0 && node[3]!=0){
if(maze[node[0]-1][node[1]]==1){
q.push({node[0]-1, node[1], node[2]+up, 3});
current_path.push_back({node[0]-1, node[1]});
path_q.push(current_path);
current_path.pop_back();
}
}
}
if(best_path.empty()){
cout<<"Can not escape!"<<endl;
}
else{
ShowPath(best_path);
}
}
return 0;
}
编辑于 2018-05-10 16:24:02
回复(2)
迷宫可以看成一个有向图，向上的边权值是3，向下的边权值是0，向左和向右的边权值都是1；不相邻的边，或者一端有障碍物的边，权值是无穷大。本质上就是求这个有向图从(0,0)到(0,m-1)的最短路径，可以用Dijkstra算法求解。
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int main()
{
// 输入数据
int n, m, P;
cin >> n >> m >> P;
vector<vector<int>> board(n);
for(int i = 0; i < n; i++)
{
board[i].resize(m);
for(int j = 0; j < m; j++)
cin >> board[i][j];
}
// 构建有向图
vector<vector<int>> graph(m * n); // 邻接矩阵[m*n][m*n]
for (int i = 0; i < m * n; i++)
graph[i].resize(m * n, INT32_MAX);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(i > 0 && board[i - 1][j]) // 向上的边权值为3
graph[i * m + j][(i - 1) * m + j] = 3;
if(i < n - 1 && board[i + 1][j]) // 向下的边权值为0
graph[i * m + j][(i + 1) * m + j] = 0;
if(j > 0 && board[i][j - 1]) // 向左的边权值为1
graph[i * m + j][i * m + j - 1] = 1;
if(j < m - 1 && board[i][j + 1]) // 向右的边权值为1
graph[i * m + j][i * m + j + 1] = 1;
}
// Dijkstra算法求(0,0)->(0,m-1)的最短路径
vector<int> prenode(m * n); // 前驱结点
vector<int> mindist(m * n); // 最短距离
vector<bool> found(m * n, false); // 该结点是否已找到最短路径
for (int i = 0; i < m * n; i++)
{
prenode[i] = 0;
mindist[i] = graph[0][i];
}
found[0] = true;
for (int v = 1; v < m * n; v++)
{
// 求得距离vs最近的结点vnear和最短距离min
int vnear;
int min = INT32_MAX;
for (int j = 0; j < m * n; j++)
if(!found[j] && mindist[j] < min)
{
min = mindist[j];
vnear = j;
}
if(min == INT32_MAX) // 找不到连通路径
break;
found[vnear] = true;
// 根据vnear修正vs到其他节点的前驱结点prenode和最短距离mindist
for (int k = 0; k < m * n; k++)
if(!found[k] && min != INT32_MAX && graph[vnear][k] != INT32_MAX && (min + graph[vnear][k] < mindist[k]))
{
prenode[k] = vnear;
mindist[k] = min + graph[vnear][k];
}
}
// 输出(0,0)到(0,m-1)的路径
if(mindist[m - 1] > P)
cout << "Can not escape!" << endl;
else
{
stack<pair<int, int>> path;
for (int i = m - 1; i != 0; i = prenode[i])
path.push({i / m, i % m});
cout << "[0,0]";
while(!path.empty())
{
const auto &p = path.top();
cout << ",[" << p.first << ',' << p.second << ']';
path.pop();
}
cout << endl;
}
return 0;
}
发表于 2018-04-08 17:02:41
回复(1)
#include <iostream>
#include <vector>
using namespace std;
const int visited = -1;
int G[10][10];
int d[4][3] = {{0,-1,1},{0,1,1},{-1,0,3},{1,0,0}};
int remain_P = -1;
int n,m,P;
struct Point{ int x, y; Point(int xx, int yy): x(xx), y(yy) {};
};
vector<Point> pathStack;
vector<Point> path;
void PrintPath(vector<Point> &path)
{ for(int i=0;i<path.size();i++) { cout<<"["<<path[i].x<<","<<path[i].y<<"]"; if(i<path.size()-1) cout<<","; }
}
void Search(int x, int y, int p)
{ pathStack.push_back(Point(x,y)); G[x][y] = visited; //当前点为出口 且 体力值>=0 if(x==0 && y==m-1 && P>=0){ if(p > remain_P) { remain_P = p; path = pathStack; } }else if(p>0){ //当前点不为出口 且 体力值>0 for(int i=0;i<4;i++) { int xx = x + d[i][0]; int yy = y + d[i][1]; int pp = p - d[i][2]; if(xx>=0 && xx<n && yy>=0 && yy<m && G[xx][yy]==1) Search(xx,yy,pp); } } pathStack.pop_back(); G[x][y] = 1;
}
int main()
{ cin>>n>>m>>P; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>G[i][j]; Search(0,0,P); if(remain_P != -1) { PrintPath(path); cout<<endl; }else cout<<"Can not escape!"<<endl; return 0;
}
编辑于 2018-01-27 01:04:10
回复(0)
//AC代码：
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
struct HeapNode{
int d,u;
HeapNode(int d,int u):d(d),u(u){}
bool operator<(const HeapNode &rhs) const{
return d>rhs.d;
}
};
struct Edge{
int from,to,dist;
Edge(int u,int v,int d):from(u),to(v),dist(d){}
};
int N,M;
const int INF=1000000000;
const int maxn=100;
struct Dijkstra{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool done[maxn];
int d[maxn];
int p[maxn];
Dijkstra(int n):n(n){}
void AddEdge(int from,int to,int dist){
edges.push_back(Edge(from,to,dist));
m=edges.size();
G[from].push_back(m-1);
}
void dijkstra(int s){
int i;
priority_queue<HeapNode> Q;
for(i=0;i<n;i++) d[i]=INF;
d[s]=0;
memset(done,0,sizeof(done));
Q.push(HeapNode(0,s));
while(!Q.empty()){
HeapNode x=Q.top(); Q.pop();
int u=x.u;
if(done[u]) continue;
done[u]=true;
for(i=0;i<G[u].size();i++){
Edge &e=edges[G[u][i]];
if(d[e.to]>d[u]+e.dist){
d[e.to]=d[u]+e.dist;
p[e.to]=G[u][i];
Q.push(HeapNode(d[e.to],e.to));
}
}
}
}
void path(int s,int t){
if(t!=s){
int fa=edges[p[t]].from;
path(s,fa);
printf("[%d,%d]",t/M,t%M);
if(t/M||t%M!=M-1) printf(",");
else printf("\n");
}else
printf("[%d,%d],",t/M,t%M);
}
};
int main(){
//freopen("input.txt","r",stdin);
int G[15][15],i,j,p,k,Next[4][3]={0,1,1,0,-1,1,-1,0,3,1,0,0};
for(scanf("%d%d%d",&N,&M,&p),i=0;i<N;i++)
for(j=0;j<M;j++) scanf("%d",&G[i][j]);
Dijkstra dijkstra(N*M);
for(i=0;i<N;i++)
for(j=0;j<M;j++)
for(k=0;k<4;k++){
int nx=i+Next[k][0],ny=j+Next[k][1],num1=i*M+j,num2=nx*M+ny;
if(nx<0||nx>=N||ny<0||ny>=M||!G[nx][ny]) continue;
dijkstra.AddEdge(num1,num2,Next[k][2]);
}
dijkstra.dijkstra(0);
if(dijkstra.d[M-1]>p) printf("Can not escape!\n");
else dijkstra.path(0,M-1);
}//用dijkstra就可以了
发表于 2017-10-21 10:49:25
回复(0)
# include <iostream>
# include <vector>
# include <stack>
using namespace std;
int res_cnt = 0; //结果数目
int max_p = -1; //初始化剩余体力
vector<int> result; //保存结果
vector<int> res_tmp; //保存中间结果
bool visited[10][10] = { 0 }; //0表示未访问过
int a[10][10] = { 0 };
void dfs(int i, int j, int p, int n, int m);
int main()
{
int n, m, p;
cin >> n >> m >> p;
cin.get();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
cin >> a[i][j];
cin.get();
}
dfs(0, 0, p, n, m);
if (res_cnt)
{
for (int i = 0; i < result.size() / 2 - 1; i++)
cout << '[' << result[2 * i] << ',' << result[2 * i + 1] << ']' << ',';
cout << '[' << result[result.size() - 2] << ',' << result[result.size() - 1] << ']' << endl;
}
else
cout << "Can not escape!" << endl;
cin.get();
}
void dfs(int i, int j, int p, int n, int m)
{
if (i<0 || i >= n || j<0 || j >= m || p<0 || !a[i][j] || visited[i][j]) //各类边界条件
return;
res_tmp.push_back(i);
res_tmp.push_back(j);
visited[i][j] = 1;
if (i == 0 && j == m - 1)
{
res_cnt++;
if (p > max_p) //找到剩余体力较多的方案，更新方案
{
max_p = p;
result.clear(); //清空
for (int i = 0; i < res_tmp.size(); i++)
result.push_back(res_tmp[i]);
}
}
else
{
dfs(i - 1, j, p - 3, n, m); //上
dfs(i + 1, j, p, n, m); //下
dfs(i, j - 1, p - 1, n, m); //左
dfs(i, j + 1, p - 1, n, m); //右
}
res_tmp.pop_back(); //记得返回
res_tmp.pop_back();
visited[i][j] = 0;
}
发表于 2017-08-27 23:32:05
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-23 18:00:59 -
2023-02-15 16:37:39
-
2023-02-12 09:53:34 -
2023-02-11 19:10:01
-
2023-02-09 10:21:07
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
