首页 > 试题广场 >

地鼠逃跑计划

[编程题]地鼠逃跑计划

热度指数：3423 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有一只地鼠不小心跑进了一个m*n的矩形田地里，假设地鼠在这块田地的初始位置为（x,y），并且每次只能向相邻的上下左右四个方向移动一步，那么在最多移动K次的情况下，有多少条路径可以逃出这片田地（一旦出去田地的边界就不能再往回走）？
下面是样例示意图：

输入描述:

输入数据包括五个参数：m,n,x,y,K
其中m和n的范围均为是[1,10]，K的范围是[0,10]。
0<=x<m,0<=y<n。

输出描述:

输出成功逃跑的路径数量。

示例1

输入

输出

算法知识视频讲解

Java

pein531

深度优先搜索

合法（剩余步数非负）越界了方案数就自增，否则尝试上下左右四个方向继续逃跑

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static int count = 0;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        int x = Integer.parseInt(br.readLine());
        int y = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
        boolean[][] grid = new boolean[m][n];
        dfs(grid, x, y, k);
        System.out.println(count);
    }
    
    private static void dfs(boolean[][] grid, int x, int y, int rest) {
        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length){
            if(rest >= 0){
                count ++;        // 合法逃出方案数自增
            }
        }else{
            if(rest > 0){
                grid[x][y] = true;
                for(int i = 0; i < 4; i++){
                    dfs(grid, x + dx[i], y + dy[i], rest - 1);
                    // 回溯
                    if(0 <= x + dx[i] && x + dx[i] < grid.length && 0 <= y + dy[i] && y + dy[i] < grid[0].length){
                        grid[x + dx[i]][y + dy[i]] = false;
                    }
                }
            }
        }
    }
}

发表于 2022-01-10 21:33:50 回复(0)

Java

继续冲

这道题目就是一个dfs，同时没有说该地鼠走过的路不能再走了。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{

     static boolean[][] vis;
     static int count=0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
            str = br.readLine();
//             处理输入
            String m=str.trim();
            int m1=Integer.parseInt(m);
            str=br.readLine();
            String n=str.trim();
            int n1=Integer.parseInt(n);
            str=br.readLine();
            String x=str.trim();
            int x1=Integer.parseInt(x);
            str=br.readLine();
            String y=str.trim();
            int y1=Integer.parseInt(y);
            str=br.readLine();
            String k=str.trim();
            int k1=Integer.parseInt(k);// 需要用到的步数

            int[][] arr=new int[m1][n1];
//             坐标为x1,y1;
            arr[x1][y1]=1;
//             vis[x1][y1]=true;
            dfs(arr,x1+1,y1,k1-1);
            dfs(arr,x1-1,y1,k1-1);
            dfs(arr,x1,y1+1,k1-1);
            dfs(arr,x1,y1-1,k1-1);
            System.out.println(count);
        }

        public static void dfs(int[][] arr,int i,int j,int step){
            if(step<0) return;
            if((i<0||i>=arr.length||j<0||arr[0].length<=j) ){
                if(step>=0){
                    count++;
                }
                return;
            }
//             if(arr[i][j]==1) return;
//             arr[i][j]=1;
            dfs(arr,i+1,j,step-1);
            dfs(arr,i-1,j,step-1);
            dfs(arr,i,j+1,step-1);
            dfs(arr,i,j-1,step-1);
//             arr[i][j]=0;
        }
    }

发表于 2021-06-25 13:24:40 回复(0)

Java

梅开六度

//java递归写法


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.lang.Integer;
public class Main{
    static int count=0;
    public static void main(String[] args) throws IOException{
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        int m=Integer.parseInt(reader.readLine());
        int n=Integer.parseInt(reader.readLine());
        int x=Integer.parseInt(reader.readLine());
        int y=Integer.parseInt(reader.readLine());
        int k=Integer.parseInt(reader.readLine());
        reader.close();
        Count(m,n,x,y,k,0);
        System.out.println(count);
    }
    private static  void Count(int m,int n,int x, int y, int k,int step){

        if((x=m||y=n)&&step<=k){
            count++;
            return ;
        }
        if(step>k) return ;
        Count(m,n,x-1,y,k,step+1);
        Count(m,n,x+1,y,k,step+1);
        Count(m,n,x,y+1,k,step+1);
        Count(m,n,x,y-1,k,step+1);
    }

}

发表于 2020-09-18 15:59:17 回复(0)

Java

LHC0512

Java解法

import java.util.Scanner;

public class Main {

    static int  m;
    static int n;
    static int K;
    public static void main(String[] args) {
        //输入数据包括五个参数：m,n,x,y,K
        Scanner scanner = new Scanner(System.in);
         m = scanner.nextInt();
         n = scanner.nextInt();
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        K = scanner.nextInt();
        System.out.println(fun(x,y,0));
    }

    static int fun(int x,int y,int step){
        if (step>K)
            return 0;
        if (x<0||y<0||x>=m||y>=n)
            return 1;
        return fun(x-1,y,step+1)+fun(x+1,y,step+1)+fun(x,y-1,step+1)+fun(x,y+1,step+1);
    }


}

编辑于 2020-02-29 17:26:43 回复(0)

提交观点

问题信息

C++工程师动态规划安卓工程师小米集团运维工程师前端工程师队列测试工程师 2018 2019 安全工程师 Java工程师

来自：小米2018春季实习生...

上传者：小小

难度：

5条回答 75收藏 8083浏览

通过挑战的用户

查看代码

miu_8

2022-10-08 18:12:14
秋招求求捞捞

2022-10-03 22:56:42
牛客12481...

2022-09-19 19:49:40
dzysuns...

2022-09-15 11:38:18
在写bug的加...

2022-09-14 15:47:40

地鼠逃跑计划

输入描述:

输出描述:

输入

输出

深度优先搜索

问题信息

热门推荐

通过挑战的用户

相关试题