首页 > 试题广场 >

地下迷宫

[编程题]地下迷宫

热度指数：19008 时间限制：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]

算法知识视频讲解

爱锤键盘的高达奥利给

发表于 2023-01-27 13:51:32

思路本题与（DD3 地下迷宫）相似，在地下迷宫的基础上增加了体力值的限制。当一个矩阵被确定时，青蛙移动的水平位移已经被确定为矩阵的长度，即青蛙水平移动消耗的体力已经被确定了。所以我们只需要考虑上下方向的移动：上下移动的位移越小，则消耗的体力值越少，所以青蛙的体力消耗主要取决展开全文

nicnaknic

发表于 2022-10-26 12:31:54

C语言写的！嘻嘻#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>#include<stdlib.h>#include<string.h>#include<stdbool.h>#in 展开全文

江街

发表于 2023-08-25 21:54:57

#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> #include<string.h> #include<errno.h> # 展开全文

咸鱼八宝粥

发表于 2023-01-16 12:47:24

#include<stdlib.h>#include<string.h>#include<assert.h>typedef struct Postion{ int row; int col;}PT;/////// 展开全文

贪吃的迪恩顶呱呱

发表于 2024-05-15 10:38:25

经典的dfs回溯写法 #include <climits> #include <iostream> #include <vector> using namespace std; int maxP = INT_MIN; // 最大剩余体力值 vector<p 展开全文

时间丶旅行

发表于 2023-03-22 16:50:40

import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new S 展开全文

牛客320912054号

发表于 2023-11-08 19:13:31

#include <stdio.h> #include<stdlib.h> #include<string.h> #include <time.h> #include<math.h> #include<ctype.h> #inc 展开全文

gggone

发表于 2020-08-21 16:33:59

先看岛屿的最大面积这道题目，再来做迷宫题 first_row = list(map(int, input().strip().split())) rows = first_row[0] cols = first_row[1] p = first_row[2] maze = [list(map(int 展开全文

lazyyyy

发表于 2022-07-20 20:09:46

package main import ( "bufio" "fmt" "os" "strconv" "strings" ) var end [2]int var start [3]int var Maxline&nb 展开全文

牛客883296623号

发表于 2020-08-21 02:50:46

import java.util.*; public class Main { static boolean flag = false; static int n, m, p; static String path = ""; static int maxRemai 展开全文

问题信息

C++工程师 golang工程师 2017 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师滴滴查找 Java工程师

上传者：小小

难度：

116条回答 277收藏 21309浏览

通过挑战的用户

查看代码

怕黑的大熊猫在创作

2023-02-23 18:00:59
少糖去冰的00...

2023-02-15 16:37:39
Aysd

2023-02-12 09:53:34
ketil

2023-02-11 19:10:01
sniper10k

2023-02-09 10:21:07

地下迷宫

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题