[编程题]小猿的迷宫之旅
- 热度指数：1658 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 48M，其他语言96M
- 算法知识视频讲解
有一个N*M大小的迷宫矩阵，迷宫的每一个格子有一个数值（a[i][j] <10^9）。小猿在迷宫中发现，它只能朝着上下左右四个方向的相邻格子前进，并且只能进入比当前位置数值更大的格子。但是小猿有个紧急呼救按钮，他可以通过按下按钮，强行进入到不满足数值大小要求的相邻格子，可惜这个按钮只能按K次。请问小猿从这个迷宫任选一个格子出发，在紧急呼救按钮的帮助下，最多能走多少步（开始位置计入步数，即站在起点是步数为1）。
输入描述:
第一行输入三个数N, M, K。接下来N行，每行M个数，表示迷宫中每个格子的值。
1 ≤ N ≤ 500
1 ≤ M ≤ 500
0 ≤ K ≤ 10
输出描述:
输出小猿在迷宫中能走的最大步数
示例1
输入
3 3 1 1 3 3 2 4 9 8 9 2
输出
6
说明
其中一种行走方案： (0, 0) -> (0, 1) -> (0, 0) -> (1, 0) -> (2, 0) -> (2, 1)
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int matrix[502][502]{0};
int memo[502][502][12]{0};
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool inAera(int x,int y){
return x>=0 && x<m && y>=0 && y<n;
}
int dfs(int x,int y,int k){
if(memo[x][y][k]){
return memo[x][y][k];
}
int count = 1;
for(int i=0;i<4;i++){
int new_x = x + d[i][0];
int new_y = y + d[i][1];
if(inAera(new_x,new_y)){
if(matrix[x][y]<matrix[new_x][new_y]){
count = max(count,dfs(new_x,new_y,k)+1);
}else{
if(k>0){
count = max(count,dfs(new_x,new_y,k-1)+1);
}
}
}
}
memo[x][y][k] = count;
return count;
}
int main(){
cin>>m>>n>>k;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>matrix[i][j];
}
}
int res = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
res = max(res, dfs(i,j,k));
}
}
cout<<res<<endl;
return 0;
}
发表于 2020-07-25 13:35:45
回复(0)
大致想法是广度优先遍历。
每一个位置处可以向上下左右四个方向进行行走，此时分为两种情况：需要使用紧急呼救按钮和不需要使用紧急呼救按钮的情况。这两种情况在每一次尝试前进时是确定的。所以一个位置处可以行进的最大次数就是向其他四个方向尝试前进可以行进的最大次数中最多的情况再加一。可以采用递归的方法进行实现。为了加快运行速度，将每次计算完的结果存放到一个三维数组中，可以直接获取。
第一次写，还希望大家多多指教。
import java.util.*;
public class Main{
static int N;
static int M;
static int K;
static int[][] group;
static int[][][] dp;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
M = scanner.nextInt();
K = scanner.nextInt();
group = new int[N][M];
//存放计算过的最大次数的数组。
dp = new int[N][M][K+1];
for (int i = 0;i<N;i++){
for (int j = 0;j<M;j++){
group[i][j] = scanner.nextInt();
}
}
int max = 0;
for (int i = 0;i<N;i++){
for (int j = 0;j<M;j++){
int num = getNum(i,j,K);
if(num > max){
max = num;
}
}
}
System.out.println(max);
}
public static int getNum(int x,int y,int k){
if(k<0 || y<0 || x<0){ //越界判断
return 0;
}
if(dp[x][y][k] != 0){ //已经计算过
return dp[x][y][k];
}
int g1 = 0;
int g2 = 0;
int g3 = 0;
int g4 = 0;
//分别向上下左右四个方向进行尝试，需要判断是否用到紧急呼救按钮次数
if(x-1 >= 0) {
if(group[x-1][y] <= group[x][y]) {
g1 = getNum(x-1,y,k-1);
}
else {
g1 = getNum(x-1,y,k);
}
}
if(y-1 >= 0) {
if(group[x][y-1] <= group[x][y]) {
g2 = getNum(x,y-1,k-1);
}
else {
g2 = getNum(x,y-1,k);
}
}
if(x+1 < N){
if(group[x+1][y] <= group[x][y]) {
g3 = getNum(x+1,y,k-1);
}
else {
g3 = getNum(x+1,y,k);
}
}
if(y+1 < M){
if(group[x][y+1] <= group[x][y]) {
g4 = getNum(x,y+1,k-1);
}
else {
g4 = getNum(x,y+1,k);
}
}
dp[x][y][k] = max(g1,g2,g3,g4) +1;
return dp[x][y][k];
}
public static int max(int a,int b,int c,int d){
if(a>=b && a>=c && a>=d){
return a;
}
else if(b>=a && b>=c && b>=d){
return b;
}
else if(c>=a && c>=b && c>=d){
return c;
}
else {
return d;
}
}
}
发表于 2020-07-24 00:50:28
回复(4)
抄袭的楼下大哥
import java.util.*;
public class Main{
static int N,M,K;
static int[][] group;
static int[][][] dp;
public static void main(String[] args){
//第一行输入N K M
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
K = sc.nextInt();
group = new int[N][M];
//存放计算过的最大次数
dp = new int[N][M][K+1];
//输入N*M N行，每行M个数，表示迷宫中每个格子的值。
for(int i = 0;i < N ; i++){
for(int j = 0; j < M;j++){
group[i][j] = sc.nextInt();
}
}
//开始计算 上下左右找一个最大值
int max = 0;
for(int i = 0; i < N;i++){
for(int j = 0; j < M; j++){
int res = getNum(i,j,K);
if(res > max){
max = res;
}
}
}
System.out.println(max);
}
//getNum()函数
static int getNum(int i,int j,int k){
//判断边界
if(k < 0 || i < 0|| j < 0) return 0;
//已经计算过
if(dp[i][j][k] != 0) return dp[i][j][k];
int g1 = 0,g2 = 0,g3 = 0,g4 = 0;
//分别从上下左右四个方向进行尝试，需要判断是否用到 【按钮】
//上
if(i-1 >= 0){
//需要用到钥匙
if(group[i-1][j] <= group[i][j]){
g1 = getNum(i-1,j,k-1);
}else{
g1 = getNum(i-1,j,k);
}
}
//下
if(i+1 < N){
//需要用到钥匙
if(group[i+1][j] <= group[i][j]){
g2 = getNum(i+1,j,k-1);
}else{
g2 = getNum(i+1,j,k);
}
}
//左
if(j-1 >= 0){
//需要用到钥匙
if(group[i][j-1] <= group[i][j]){
g3 = getNum(i,j-1,k-1);
}else{
g3 = getNum(i,j-1,k);
}
}
//右
if(j+1 < M){
//需要用到钥匙
if(group[i][j+1] <= group[i][j]){
g4 = getNum(i,j+1,k-1);
}else{
g4 = getNum(i,j+1,k);
}
}
dp[i][j][k] = maxValue(g1,g2,g3,g4) + 1;
return dp[i][j][k];
}
//求四个数中的最大值
public static int maxValue(int a,int b,int c,int d){
if(a >= b && a >= c && a >= d){
return a;
} else if(b >= a && b >= c && b >= d){
return b;
} else if(c >= a && c >= b && c >= d) {
return c;
}else {
return d;
}
}
}
编辑于 2020-08-01 15:42:54
回复(0)
Java 深搜
import java.util.Scanner;
public class Main{
static int row,column;
static int[] dx={0,1,-1,0};
static int[] dy={1,0,0,-1};
static int[][][] mem;
public static void main(String[] args)
{
int count=1;
Scanner sc=new Scanner(System.in);
row=sc.nextInt();
column=sc.nextInt();
int k=sc.nextInt();
mem=new int[row][column][k+1];
int[][] a=new int[row][column];
for(int i = 0;i < row;i++)
for(int j = 0;j < column;j++)
a[i][j]=sc.nextInt();
for(int i=0;i<row;i++)
for(int j=0;j<column;j++)
count=Math.max(count,dfs(a,i,j,k));
System.out.print(count);
}
static int dfs(int[][] a,int i,int j,int k)
{
if(mem[i][j][k]>0) return mem[i][j][k];
int count=1;
for(int p=0;p<=3;p++)
{
int x=i+dx[p],y=j+dy[p];
if(check1(x,y))
{
if(a[x][y]>a[i][j]) {
count=Math.max(count,dfs(a,x,y,k)+1);}
else{
if(k>0)
{
count=Math.max(count,dfs(a,x,y,k-1)+1);
}
}
}
}
mem[i][j][k] = count;
return count;
}
static boolean check1(int i,int j)
{
if(i<0||i>=row||j<0||j>=column) return false;
return true;
}
}
发表于 2021-03-26 21:08:17
回复(0)
记忆化搜索
import java.util.*;
public class Main{
public static int[][] direct = {{0,1}, {0,-1}, {1,0},{-1,0}};
public static int[][][] memo;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int k = in.nextInt();
int[][] arr = new int[n][m];
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++) arr[i][j] = in.nextInt();
}
int res = 0;
memo = new int[n+1][m+1][k+1];
for(int i = 0; i < n; i++){
for(int j = 0; j<m; j++) res = Math.max(helper(arr, k, i, j),res);
}
System.out.println(res);
}
public static int helper(int[][] arr, int k, int x, int y){
if(k < 0) return 0;
if(valid(arr, x, y) && k == 0) return 1;
if(memo[x][y][k] != 0) return memo[x][y][k];
int res = 1;
for(int i = 0; i<4; i++){
int n_x = x + direct[i][0];
int n_y = y + direct[i][1];
if(n_x >= 0 && n_x = 0 && n_y < arr[0].length){
if(arr[n_x][n_y] <= arr[x][y]) res = Math.max(helper(arr, k-1 , n_x, n_y)+1, res);
else res = Math.max(helper(arr, k, n_x, n_y)+1, res);
}
}
memo[x][y][k] = res;
return res;
}
public static boolean valid(int[][] arr, int x, int y){
boolean up = false, down = false, left = false, right = false;
if(x-1 = arr[x-1][y]) up = true;
if(x+1 >= arr.length || arr[x][y] >= arr[x+1][y]) down = true;
if(y-1 = arr[x][y-1]) left = true;
if(y+1 >= arr[0].length || arr[x][y] >= arr[x][y+1]) right = true;
return left && right && down && up;
}
}
编辑于 2021-03-27 16:10:21
回复(0)
只能过40%，有没有大佬看下
n, m, k = map(int, input().split())
g = []
for _ in range(n):
g.append(list(map(int, input().split())))
dp = {}
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def dfs(i, j, k):
if (i, j, k) in dp:
return dp[(i, j, k)]
cur = g[i][j]
res = 1
for idx in range(4):
x = i + dx[idx]
y = j + dy[idx]
if 0 <= x < n and 0 <= y < m:
if g[x][y] > cur:
res = max(res, dfs(x, y, k) + 1)
else:
if k > 0:
res = max(res, dfs(x, y, k - 1) + 1)
dp[(i, j, k)] = res
return res
res = 0
for i in range(n):
for j in range(m):
res = max(res, dfs(i, j, k))
print(res)
发表于 2020-08-20 22:59:54
回复(0)
#include<bits/stdc++.h>
using namespace std;
int n,m;
int mat[502][502]{0};
int dp[502][502][12]{0};
int dfs(int i, int j, int k) {
// print(i, j, k)
if (dp[i][j][k])
return dp[i][j][k];
int a=1, b=1, c=1, d = 1;
int base = mat[i][j];
if (i-1>=0)
if (mat[i - 1][j] > base)
a += dfs(i - 1, j, k);
else
if (k >= 1)
a += dfs(i - 1, j, k - 1);
if (i+1<n)
if (mat[i + 1][j] > base)
b += dfs(i + 1, j, k);
else
if (k >= 1)
b += dfs(i + 1, j, k - 1);
if (j-1>=0)
if (mat[i][j - 1] > base)
c += dfs(i, j - 1, k);
else
if (k >= 1)
c += dfs(i, j - 1, k - 1);
if (j+1<m)
if (mat[i][j + 1] > base)
d += dfs(i, j + 1, k);
else
if (k >= 1)
d += dfs(i, j + 1, k - 1);
dp[i][j][k] = max(max(a, b), max(c, d));
return dp[i][j][k];
}
int main(){
int K;
cin>>n>>m>>K;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mat[i][j];
}
}
int res = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
dfs(i,j,K);
res = max(res, dp[i][j][K]);
}
}
cout<<res<<endl;
return 0;
}
dfs里要先往高处判断，卡了我好久。。。
编辑于 2020-08-01 15:59:02
回复(0)
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
#include <queue>
using namespace std;
int n,m,k;
int g[501][501];
int dp[501][501][11];
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
int dfs(int x, int y, int k){
if(k<0) return 0;
if(dp[x][y][k] != -1){
return dp[x][y][k];
}
dp[x][y][k] = 1;
for(int i=0;i<4;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(nx<0||nx>=n||ny<0||ny>=m){
continue;
}
if(g[nx][ny]>g[x][y]){
dp[x][y][k] = max(dfs(nx,ny,k)+1, dp[x][y][k]);
}
else if(k>0){
dp[x][y][k] = max(dfs(nx,ny,k-1)+1, dp[x][y][k]);
}
}
return dp[x][y][k];
}
int main(){
while(cin>>n>>m>>k){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>g[i][j];
//init
for(int h=0;h<=k;h++)
dp[i][j][h] = -1;
}
}
int ans = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
ans = max(ans, dfs(i,j,k));
}
}
cout<<ans<<endl;
}
}
发表于 2020-07-24 14:46:30
回复(0)
问题信息
通过挑战的用户
-
2022-08-06 22:42:18
-
2022-08-06 12:52:27
-
2022-08-05 11:52:36 -
2022-07-20 10:26:03
-
2021-09-20 17:08:57
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
