首页 > 试题广场 >

地鼠逃跑计划

[编程题]地鼠逃跑计划

热度指数：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

输入

输出

算法知识视频讲解

随缘笔试

#include <bits/stdc++.h>
using namespace std;

int m, n, x, y, k, ans;
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};

bool outside(int x, int y) {
    return x < 0 || m <= x || y < 0 || n <= y;    
}

void dfs(int x, int y, int k) {
    if (k <= 0) return;
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (outside(nx, ny)) ++ans;
        else dfs(nx, ny, k - 1);
    }    
}

int main() {
    scanf("%d %d %d %d %d", &m, &n, &x, &y, &k);
    dfs(x, y, k);
    cout << ans << endl;
    return 0;
}

编辑于 2019-08-17 22:46:11 回复(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)

-chips

java版，递归4行

import java.util.Scanner;
public class Main {
    public int countPath(int m, int n, int x, int y, int k) {
        if (!(x>=0 && x<m && y>=0 && y<n)) // 逃出
            return 1;
        else if (k == 0) // 在范围内，但步数已经为0，返回0
            return 0;
        return countPath(m,n,x+1,y,k-1) + countPath(m,n,x-1,y,k-1) +
            countPath(m,n,x,y+1,k-1) + countPath(m,n,x,y-1,k-1);
    }
     
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Main main = new Main();
        while(in.hasNextInt()) {
            int m = in.nextInt();
            int n = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            int k = in.nextInt();
            System.out.println(main.countPath(m,n,x,y,k));
        }
    }
}

发表于 2019-11-25 11:09:22 回复(0)

dragonlogin

#include<bits/stdc++.h>
using namespace std;

int f(int m, int n, int x, int y, int k) {
	if (k==0 && x>=0&&x<m && y>=0&&y<n) {
		return 0;
	}
	// yuejie
	if (x<0 || x>=m || y<0 || y>=n) {
		return 1;
	}
	// k > 0
	int ans = 0;
	ans += f(m, n, x-1, y, k-1);
	ans += f(m, n, x+1, y, k-1);
	ans += f(m, n, x, y-1, k-1);
	ans += f(m, n, x, y+1, k-1);
	return ans;
}
int main() {
	int m,n,x,y,k;
	cin>>m>>n>>x>>y>>k;
	cout << f(m,n,x,y,k) << endl;
	return 0;
}

发表于 2019-10-19 15:46:59 回复(0)

C/C++

hello古斯卡

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <list>
#include <math.h>
#include <set>
#include <cstdio>
#include <queue>
#include <sstream>
#include <stack>

//#define DBL_MAX 1.7976931348623158e+308

using namespace std;
typedef long long ll;
#define BIG 1000000000
//习惯性带上上面

int f(int m, int n, int x, int y, int k) {
    if (x < 0 || y < 0 || x >= n || y >= m) {
        return 1;
    }
    if (k <= 0) {
        return 0;
    }
    return f(m, n, x + 1, y, k - 1) + f(m, n, x - 1, y, k - 1) + f(m, n, x, y + 1, k - 1) + f(m, n, x, y - 1, k - 1);
}


int main() {
    int m, n, x, y, k;
    cin >> m >> n >> y >> x >> k;
    cout << f(m, n, x, y, k) << endl;
    return 0;
}

发表于 2019-10-04 22:52:48 回复(0)

自由的小白

java版的，主要也是递归，要注意的是结束条件。

1，假如现在step > k说明还没出去，返回0

2，假如现在的点已经在田外，则返回1，说明可行并推出

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        int x = scan.nextInt();
        int y = scan.nextInt();
        int k = scan.nextInt();
        boolean[][] flags = new boolean[m][n];

        int res;
        res = helper(m, n, x, y, k, 0);
        System.out.println(res);

        scan.close();
    }

    private static int helper(int m, int n, int x, int y, int k, int step) {
        int count = 0;

        // 如果超出了步数，那么直接返回0
        if (k < step)
            return 0;

        // 已经在外边，那么直接返回
        if (x < 0 || x >= m || y < 0 || y >= n){
            return 1;
        }

        int up = helper(m, n, x - 1, y, k, step + 1);
        int down = helper(m, n, x + 1, y, k, step + 1);
        int left = helper(m, n, x, y - 1, k, step + 1);
        int right = helper(m, n, x, y + 1, k, step + 1);

        // 所有的数量为上下左右之和
        count += (up + right + left + down);
        return count;
    }
}

发表于 2019-09-20 08:46:15 回复(0)

C/C++

凌峰秋雪

#include<iostream>

using namespace std;

int func(int x, int y,int K,int m,int n)
{
	int up = 0, down = 0, left = 0, right = 0, sum = 0;
	if (K == 0)
		return 0;
	if (x==0)//向上
		up = 1;
	else
		up = func(x - 1, y, K - 1, m, n);
	if (x == m - 1)//向下
		down = 1;
	else
		down = func(x + 1, y, K - 1, m, n);
	if (y == 0)//向左
		left = 1;
	else
		left = func(x, y - 1, K - 1, m, n);
	if (y == n - 1)//向右
		right = 1;
	else
		right = func(x, y + 1, K - 1, m, n);
	sum = up + down + left + right;
	return sum;
}
int main()
{
	int m = 0, n = 0, x = 0, y = 0, K = 0;
	cin >> m;
	cin >> n;
	cin >> x;
	cin >> y;
	cin >> K;

	cout << func(x, y, K, m, n);
}

发表于 2019-09-10 16:49:45 回复(1)

C/C++

昔遥暮云

#include <iostream>
using namespace std;
int m,n,x,y,k,ans;
void solve(int h,int i,int j){
    if(h>k)     //超过步数
        return;
    else if(i>=m||i<0||j>=n||j<0)   //走出田地范围
        ans++;
    else{   
        solve(h+1,i-1,j);   //上
        solve(h+1,i+1,j);   //下
        solve(h+1,i,j-1);   //左
        solve(h+1,i,j+1);   //右
    }
}
int main(){  
    cin>>m>>n>>x>>y>>k;
    solve(0,x,y);
    cout<<ans;
    return 0;
}

发表于 2019-09-04 17:08:51 回复(1)

C/C++

北雷北雷

需要额外注意的是，上下左右是四种情形，不能合并处理。刚开始if合起来判断了，总是少一点

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int m, n, k;
void times(int x, int y, int left_times, int &count) {
    if (left_times > 0) {
        if (x == 0 )    count++;
        if (x == m - 1) count++;
        if (y == 0 )    count++;
        if (y == n - 1) count++;

        if (x > 0)  times(x - 1, y, left_times - 1, count);
        if (x < m - 1)times(x + 1, y, left_times - 1, count);
        if (y < n - 1)  times(x, y + 1, left_times - 1, count);
        if (y > 0)      times(x, y - 1, left_times - 1, count);

    }
}
int main() {
    cin >> m >> n;
    int x, y, count = 0;
    cin >> x >> y >> k;
    times(x, y, k, count);
    cout << count;
    system("pause");
    return 0;
}

编辑于 2019-07-24 09:24:22 回复(0)

Python

ElonB

""""
BFS或DFS
"""
import sys
from collections import deque


def BFS(m, n, x, y, K):
    deq = deque([(x, y, 0)])
    ans = 0
    while deq:
        i, j, k = deq.popleft()
        if k >= K: break
        if i + 1 >= m:
            ans += 1
        else:
            deq.append((i + 1, j, k + 1))
        if i - 1 < 0:
            ans += 1
        else:
            deq.append((i - 1, j, k + 1))
        if j + 1 >= n:
            ans += 1
        else:
            deq.append((i, j + 1, k + 1))
        if j - 1 < 0:
            ans += 1
        else:
            deq.append((i, j - 1, k + 1))
    return ans


if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    m, n, x, y, K = int(input()), int(input()), int(input()), int(input()), int(input()),
    ans = BFS(m, n, x, y, K)
    print(ans)

发表于 2019-07-14 10:20:03 回复(0)

XII0001

#include<iostream>
#include<vector>
using namespace std;
int getAns(int m, int n, int x, int y, int K){
vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(K+1,0)));
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
for(int k=1; k<=K; k++){
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
dp[i][j][k] = 0;
for(int t=0; t<4; t++){
int tx = i+dx[t], ty = j+dy[t];
if(tx<0 || tx>=m || ty<0 || ty>=n) dp[i][j][k]++; //这里暗含了可以少走几步
else dp[i][j][k] += dp[tx][ty][k-1];
}
}
}
}
return dp[x][y][K];
}
int main(){
int m, n, x, y, K;
while(cin>>m>>n>>x>>y>>K){
cout<<getAns(m,n,x,y,K)<<endl;
}
return 0;
}

发表于 2019-07-06 10:50:52 回复(1)

Bostonpigeons

其实就是计算第n步所有边界上的点的和。
矩阵进行k次转移，然后统计和即可。
转移方程直接用周围四个点转移。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<bits/stdc++.h>
using namespace std;
int z[15][15];
int a[15][15];
int main()
{
   // freopen("in","r",stdin);
    int m,n,x,y,k;
    cin>>n>>m>>x>>y>>k;
    x++;
    y++;
    z[x][y]=1;
   // k--;
    int sum=0;
    while(k--){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                a[i][j]=(z[i-1][j]+z[i+1][j]+z[i][j+1]+z[i][j-1]);

                if(i==1){
                    sum+=z[i][j];
                }
                if(i==n){
                    sum+=z[i][j];
                }
                if(j==1){
                    sum+=z[i][j];
                }
                if(j==m){
                    sum+=z[i][j];
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                z[i][j]=a[i][j];
             //   cout<<z[i][j]<<' ';
            }
         //   cout<<endl;
        }

    }
    cout<<sum<<endl;
    return 0;
}

发表于 2019-06-30 16:55:31 回复(2)

C/C++

别和我比菜

很简单的DFS
当前坐标、步数对应的路径总数 = 当前方格能1步出田地的路径数 + 上下左右步数+1时出田地的路径数

#include 
using namespace std;
int dfs(int i, int j, const int& row, const int& col, int step, const int& K){
    int now = 0;
    if(step==K)    //K步之后还在田地里
        return 0;
    if(i==0)
        ++now;
    if(j==0)
        ++now;
    if(i==row-1)
        ++now;
    if(j==col-1)
        ++now;
    int up,down,left,right;
    up = down = left = right = 0;
    if(i>0)
        up = dfs(i-1,j,row,col,step+1,K);
    if(i<row-1)
        down = dfs(i+1,j,row,col,step+1,K);
    if(j>0)
        left = dfs(i,j-1,row,col,step+1,K);
    if(j<col-1)
        right = dfs(i,j+1,row,col,step+1,K);
    return now+up+down+left+right;
}

int main(){
    int m,n,x,y,K;
    cin>>m>>n>>x>>y>>K;
    int result = dfs(x,y,m,n,0,K);
    cout<<result<<endl;
    return 0;
}

发表于 2019-04-27 16:25:04 回复(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)

任肖乐

田鼠：麻买批

发表于 2019-04-18 13:25:18 回复(2)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int m,n,k;

int DFS(int x, int y, int s){
    int sum=0;
    if(s==k)
        return 0;
    if(x==0)
        sum++;
    if(y==0)
        sum++;
    if(x==m-1)
        sum++;
    if(y==n-1)
        sum++;

    if(x>0)
        sum += DFS(x-1,y,s+1);
    if(x<m-1)
        sum += DFS(x+1,y,s+1);
    if(y>0)
        sum += DFS(x,y-1,s+1);
    if(y<n-1)
        sum += DFS(x,y+1,s+1);
    return sum;
}

int main(){
    int x,y;
    cin>>m>>n>>x>>y>>k;
    cout<<DFS(x,y,0)<<endl;    
    return 0;
}

发表于 2019-07-14 23:14:52 回复(0)

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var m,n,x,y,k int
    fmt.Scan(&m,&n,&x,&y,&k)
    ans:=0
    var dfs func(int,int,int)
    dfs=func(i,j int,tot int){
        if tot>k{
            return
        }
        if (i<0||i>=m||j<0||j>=n)&&tot<=k{
            ans++
            return
        }
        tot++
        dfs(i+1,j,tot)
        dfs(i-1,j,tot)
        dfs(i,j+1,tot)
        dfs(i,j-1,tot)
    }
    dfs(x,y,0)
    fmt.Print(ans)
}

发表于 2023-03-19 07:56:33 回复(0)

白羽青罗

鼠鼠我啊，真的是要累死了捏！递归加回溯。

import sys
 
# for line in sys.stdin:
#     a = line.split()
#     print(int(a[0]) + int(a[1]))
para = []
for i in range(5):
    num = int(input())
    para.append(num)
row, col = para[0], para[1]
start = (para[2], para[3])
K = para[-1]
tian = [[0]*3 for _ in range(row)]
res = []
temp = []
 
def func(start, K):
    global res, tian, temp
    m, n = start
    if ((m<0&nbs***bsp;m>=row)&nbs***bsp;(n<0&nbs***bsp;n>=col) and K>=0):
        res.append(temp.copy())
        return
    K -= 1
    if K<0:
        return
    temp.append(start)
    func((m+1, n), K)
    func((m-1, n), K)
    func((m, n-1), K)
    func((m, n+1), K)
    temp.pop()
    K += 1
 
func(start, K)
print(len(res))

发表于 2023-02-17 11:39:13 回复(0)

C++

科大无颜祖

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

void helper(int m,int n,int x,int y,int k,vector<pair<int,int>>& dirs,int& res ,int curr_step){
if(x < 0 || x >= m || y < 0 || y >= n){
res++;
return;
}
if(curr_step >= k){
return;
}

for(auto dir:dirs){
helper(m,n,x+dir.first,y+dir.second,k,dirs,res,curr_step + 1);
}
}

int main(){
int m,n,x,y,k;
cin >> m >> n >> x >> y >> k;
int res = 0;
vector<pair<int,int>> dirs{{1,0},{-1,0},{0,1},{0,-1}};
helper(m,n,x,y,k,dirs,res,0);
cout << res;
}

发表于 2022-06-22 23:59:26 回复(0)

提交观点

问题信息

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

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

上传者：小小

难度：

36条回答 74收藏 8078浏览

通过挑战的用户

查看代码

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

地鼠逃跑计划

输入描述:

输出描述:

输入

输出

深度优先搜索

问题信息

热门推荐

通过挑战的用户

相关试题