首页 > 试题广场 >

地鼠逃跑计划

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

田鼠:麻买批

发表于 2019-04-18 13:25:18 回复(2)
#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)

深度优先搜索

合法(剩余步数非负)越界了方案数就自增,否则尝试上下左右四个方向继续逃跑
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)

这道题目就是一个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版,递归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)
#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)
#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)
#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)
#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)

需要额外注意的是,上下左右是四种情形,不能合并处理。刚开始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)
""""
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)
#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)
其实就是计算第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)

很简单的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解法
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)
#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)
#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)