首页 > 试题广场 >

地鼠逃跑计划

[编程题]地鼠逃跑计划
  • 热度指数：3412 时间限制：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

输入

2
3
0
1
2

输出

6
算法知识视频讲解
添加回答
Java
pein531头像 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头像 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条回答 7366浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号