首页 > 试题广场 >

地鼠逃跑计划

[编程题]地鼠逃跑计划

热度指数：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 <stdio.h>
#include <stdlib.h>

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

int main(const int argc, const char* argv[]) {
  int m, n, y, x, k;
  fscanf(stdin, "%d %d %d %d %d", &m, &n, &y, &x, &k);
  fprintf(stdout, "%d\n", depth_first_search_algorithm(m, n, x, y, k));
  return 0;
}

发表于 2021-07-16 07:41:53 回复(0)