(C卷,200分)- 园区参观路径（Java & JS & Python & C）

题目描述

园区某部门举办了Family Day，邀请员工及其家属参加；

将公司园区视为一个矩形，起始园区设置在左上角，终点园区设置在右下角；

家属参观园区时，只能向右和向下园区前进，求从起始园区到终点园区会有多少条不同的参观路径。

输入描述

第一行为园区的长和宽；

后面每一行表示该园区是否可以参观，0表示可以参观，1表示不能参观

输出描述

输出为不同的路径数量

用例

题目解析

本题可以使用深度优先搜索解题。

因为深度优先搜索DFS的每一条递归分支都对应一条路径，如果某个递归分支可以走到终点位置，那么说明该递归分支对应的路径可达终点。

本题递归进入下一个位置的条件是：

• 下一个位置在上一个位置的下边或右边
• 下一个位置不越界
• 下一个位置可以参观（矩阵元素值为0）

并且，本题限定只能从当前位置，向下或者向右进入下一个位置，因此不用担心走回头路的问题，即不用建立visited表记录走过的位置。

注意：本题没有数量级信息，因此如果存在大数量级的话，基于递归实现的深搜可能会发生StackOverFlow异常，因此更推荐使用基于栈结构实现的深搜。

本题如果地图矩阵数量级过大的话，深搜解题会超时。因此，更优解法是利用动态规划，我们可以定义一个dp二维数组，dp[i][j]的含义是：从坐标(0,0)到达坐标(i, j)的路径数

而本题说只能向下或者向右运动，因此到达一个坐标点，可能来自其上方，亦可能来自其左方

因此 dp[i][j] = dp[i-1][j] + dp[i][j-1]

即：

如果到达(i-1,j)的路径有dp[i-1][j]条，那么到达(i,j)的路径也有dp[i-1][j]条

同理到达(i, j-1)的路径有dp[i][j-1]，那么到达(i,j)的路径也有dp[i][j-1]条

因此：dp[i][j] = dp[i-1][j] + dp[i][j-1]

需要注意的是，dp[0][0] 初始化时，需要注意(0,0)坐标位置是否可以参观，如果不可以参观，则道道(0,0)的路径为0条，否则为1条。

其他点套用公式时，注意索引越界问题，具体请看代码实现。

JS算法源码

动态规划

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // 长n -> 行数, 宽m -> 列数
  const [n, m] = (await readline()).split(" ").map(Number);

  // 地图矩阵
  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push((await readline()).split(" ").map(Number));
  }

  // 如果起点和终点不能参观，则没有路径
  if (matrix[0][0] == 1 || matrix[n - 1][m - 1] == 1) {
    console.log(0);
    return;
  }

  const dp = new Array(n).fill(0).map(() => new Array(m).fill(0));
  dp[0][0] = 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (matrix[i][j] == 1) continue;

      if (i > 0) {
        dp[i][j] += dp[i - 1][j];
      }

      if (j > 0) {
        dp[i][j] += dp[i][j - 1];
      }
    }
  }

  console.log(dp[n - 1][m - 1]);
})();

基于递归实现的深搜

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // 长n -> 行数, 宽m -> 列数
  const [n, m] = (await readline()).split(" ").map(Number);

  // 地图矩阵
  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push((await readline()).split(" ").map(Number));
  }

  // 向下、向右的偏移量
  const offsets = [
    [1, 0],
    [0, 1],
  ];

  // 记录题解
  let ans = 0;

  function dfs(x, y) {
    if (x == n - 1 && y == m - 1) {
      // 如果当前分支可以走到终点，则对应分支路径可行
      ans++;
      return;
    }

    // 从当前位置(x, y)向下或者向右走
    for (let [offsetX, offsetY] of offsets) {
      // 新位置(newX, newY)
      const newX = x + offsetX;
      const newY = y + offsetY;

      // 如果新位置没有越界且新位置可以参观，则进入
      if (
        newX >= 0 &&
        newX < n &&
        newY >= 0 &&
        newY < m &&
        matrix[newX][newY] == 0
      ) {
        dfs(newX, newY);
      }
    }
  }

  // 从(0,0)位置开始深搜，深搜对应的每条分支都对应一条路径
  if (matrix[0][0] == 0) {
    dfs(0, 0);
  }

  console.log(ans);
})();

 基于栈实现的深搜

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // 长n -> 行数, 宽m -> 列数
  const [n, m] = (await readline()).split(" ").map(Number);

  // 地图矩阵
  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push((await readline()).split(" ").map(Number));
  }

  // 向下、向右的偏移量
  const offsets = [
    [1, 0],
    [0, 1],
  ];

  // 记录题解
  let ans = 0;

  function dfs() {
    const stack = [];

    if (matrix[0][0] == 0) {
      stack.push(0);
    }

    while (stack.length > 0) {
      const pos = stack.pop();

      const y = pos % m;
      const x = (pos - y) / m;

      if (x == n - 1 && y == m - 1) {
        ans++;
        continue;
      }

      for (let [offsetX, offsetY] of offsets) {
        const newX = x + offsetX;
        const newY = y + offsetY;

        if (
          newX >= 0 &&
          newX < n &&
          newY >= 0 &&
          newY < m &&
          matrix[newX][newY] == 0
        ) {
          stack.push(newX * m + newY);
        }
      }
    }
  }

  // 从(0,0)位置开始深搜，深搜对应的每条分支都对应一条路径
  dfs();

  console.log(ans);
})();

Java算法源码

动态规划

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt(); // 长 -> 行数
    int m = sc.nextInt(); // 宽 -> 列数

    int[][] matrix = new int[n][m]; // 地图矩阵
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = sc.nextInt();
      }
    }

    // 如果起点和终点不能参观，则没有路径
    if (matrix[0][0] == 1 || matrix[n - 1][m - 1] == 1) {
      System.out.println(0);
      return;
    }

    long[][] dp = new long[n][m];
    dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (matrix[i][j] == 1) continue;

        if (i > 0) {
          dp[i][j] += dp[i - 1][j];
        }

        if (j > 0) {
          dp[i][j] += dp[i][j - 1];
        }
      }
    }

    System.out.println(dp[n - 1][m - 1]);
  }
}

基于递归实现的深搜

import java.util.Scanner;

public class Main {
  static int n;
  static int m;
  static int[][] matrix;
  static int[][] offsets = {{1, 0}, {0, 1}};

  static int ans = 0;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt(); // 长 -> 行数
    m = sc.nextInt(); // 宽 -> 列数

    matrix = new int[n][m]; // 地图矩阵
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = sc.nextInt();
      }
    }

    // 从(0,0)位置开始深搜，深搜对应的每条分支都对应一条路径
    if (matrix[0][0] == 0) {
      dfs(0, 0);
    }

    System.out.println(ans);
  }

  public static void dfs(int x, int y) {
    if (x == n - 1 && y == m - 1) {
      // 如果当前分支可以走到终点，则对应分支路径可行
      ans++;
      return;
    }

    // 从当前位置(x, y)向下或者向右走
    for (int[] offset : offsets) {
      // 新位置(newX, newY)
      int newX = x + offset[0];
      int newY = y + offset[1];

      // 如果新位置越界了，或者新位置不能参观，则无法进入
      if (newX < 0 || newX >= n || newY < 0 || newY >= m || matrix[newX][newY] == 1) continue;

      // 否则进入新位置，继续深搜
      dfs(newX, newY);
    }
  }
}

基于栈实现的深搜

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  static int n;
  static int m;
  static int[][] matrix;
  static int[][] offsets = {{1, 0}, {0, 1}};

  static int ans = 0;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt(); // 长 -> 行数
    m = sc.nextInt(); // 宽 -> 列数

    matrix = new int[n][m]; // 地图矩阵
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = sc.nextInt();
      }
    }

    dfs();

    System.out.println(ans);
  }

  public static void dfs() {
    LinkedList<Integer> stack = new LinkedList<>();

    if (matrix[0][0] == 0) {
      stack.addLast(0);
    }

    while (stack.size() > 0) {
      int pos = stack.removeLast();

      int x = pos / m;
      int y = pos % m;

      if (x == n - 1 && y == m - 1) {
        ans++;
        continue;
      }

      for (int[] offset : offsets) {
        int newX = x + offset[0];
        int newY = y + offset[1];

        if (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX][newY] == 0) {
          stack.addLast(newX * m + newY);
        }
      }
    }
  }
}

Python算法源码

动态规划

# 输入获取
n, m = map(int, input().split())  # // 长n -> 行数, 宽m -> 列数
matrix = [list(map(int, input().split())) for _ in range(n)]  # 地图矩阵


# 算法入口
def getResult():
    # 如果起点和终点不能参观，则没有路径
    if matrix[0][0] == 1 or matrix[n - 1][m - 1] == 1:
        return 0

    dp = [[0 for _ in range(m)] for _ in range(n)]
    dp[0][0] = 1

    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1:
                continue

            if i > 0:
                dp[i][j] += dp[i - 1][j]

            if j > 0:
                dp[i][j] += dp[i][j - 1]

    return dp[n - 1][m - 1]


# 算法调用
print(getResult())

基于递归实现的深搜

# 输入获取
n, m = map(int, input().split())  # // 长n -> 行数, 宽m -> 列数
matrix = [list(map(int, input().split())) for _ in range(n)]  # 地图矩阵

# 向下、向右的偏移量
offsets = ((1, 0), (0, 1))

# 记录题解
ans = 0


# 深搜
def dfs(x, y):
    global ans

    if x == n - 1 and y == m - 1:
        # 如果当前分支可以走到终点，则对应分支路径可行
        ans += 1
        return

    # 从当前位置(x, y)向下或者向右走
    for offsetX, offsetY in offsets:
        # 新位置(newX, newY)
        newX = x + offsetX
        newY = y + offsetY

        # 如果新位置没有越界且新位置可以参观，则进入
        if n > newX >= 0 and m > newY >= 0 and matrix[newX][newY] == 0:
            dfs(newX, newY)


# 算法调用
if matrix[0][0] == 0:
    dfs(0, 0)  # 从(0,0)位置开始深搜，深搜对应的每条分支都对应一条路径
print(ans)

基于栈实现的深搜

# 输入获取
n, m = map(int, input().split())  # // 长n -> 行数, 宽m -> 列数
matrix = [list(map(int, input().split())) for _ in range(n)]  # 地图矩阵

# 向下、向右的偏移量
offsets = ((1, 0), (0, 1))

# 记录题解
ans = 0


# 深搜
def dfs():
    global ans

    stack = []

    if matrix[0][0] == 0:
        stack.append(0)

    while len(stack) > 0:
        pos = stack.pop()

        x = pos // m
        y = pos % m

        if x == n - 1 and y == m - 1:
            ans += 1
            continue

        for offsetX, offsetY in offsets:
            newX = x + offsetX
            newY = y + offsetY

            if n > newX >= 0 and m > newY >= 0 and matrix[newX][newY] == 0:
                stack.append(newX * m + newY)


# 算法调用
dfs()
print(ans)

C算法源码

动态规划

#include <stdio.h>

int main() {
    // 长n -> 行数, 宽m -> 列数
    int n, m;
    scanf("%d %d", &n, &m);

    // 地图矩阵，这里把二维压缩为了一维
    int matrix[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 由于matrix是一维数组，所以这里(i, j)二维坐标也要转成一维坐标
            scanf("%d", &matrix[i][j]);
        }
    }

    if (matrix[0][0] == 1 || matrix[n - 1][m - 1] == 1) {
        puts("0");
        return 0;
    }

    long dp[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j] = 0;
        }
    }

    dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1) continue;

            if (i > 0) {
                dp[i][j] += dp[i - 1][j];
            }

            if (j > 0) {
                dp[i][j] += dp[i][j - 1];
            }
        }
    }

    printf("%ldn", dp[n - 1][m - 1]);

    return 0;
}

基于递归实现的深搜

#include <stdio.h>
#include <stdlib.h>

// 长n -> 行数, 宽m -> 列数
int n, m;

// 地图矩阵，这里把二维压缩为了一维
int *matrix;

// 向下、向右的偏移量
int offsets[2][2] = {{1, 0},
                     {0, 1}};

// 记录题解
int ans = 0;

void dfs(int x, int y) {
    if (x == n - 1 && y == m - 1) {
        // 如果当前分支可以走到终点，则对应分支路径可行
        ans += 1;
        return;
    }

    // 从当前位置(x, y)向下或者向右走
    for (int i = 0; i < 2; i++) {
        // 新位置(newX, newY)
        int newX = x + offsets[i][0];
        int newY = y + offsets[i][1];

        // 如果新位置没有越界且新位置可以参观，则进入
        if (newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX * m + newY] == 0) {
            dfs(newX, newY);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);

    matrix = (int *) calloc(n * m, sizeof(int));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 由于matrix是一维数组，所以这里(i, j)二维坐标也要转成一维坐标
            scanf("%d", &matrix[i * m + j]);
        }
    }

    // 从(0,0)位置开始深搜，深搜对应的每条分支都对应一条路径
    if(matrix[0] == 0) {
        dfs(0, 0);
    }

    printf("%dn", ans);

    return 0;
}

基于栈实现的深搜

#include <stdio.h>
#include <stdlib.h>

// 自定义栈结构（数组）的容量，不够再加
#define MAX_SIZE 10000

// 长n -> 行数, 宽m -> 列数
int n, m;

// 地图矩阵，这里把二维压缩为了一维
int *matrix;

// 向下、向右的偏移量
int offsets[2][2] = {{1, 0},
                     {0, 1}};

// 记录题解
int ans = 0;

void dfs() {
    int stack[MAX_SIZE];
    int stack_size = 0;

    if(matrix[0] == 0) {
        stack[stack_size++] = 0;
    }

    while(stack_size > 0) {
        int pos = stack[--stack_size];

        int x = pos / m;
        int y = pos % m;

        if(x == n - 1 && y == m - 1) {
            ans++;
            continue;
        }

        for(int i=0; i<2; i++) {
            int newX = x + offsets[i][0];
            int newY = y + offsets[i][1];

            if(newX >= 0 && newX < n && newY >= 0 && newY < m && matrix[newX * m + newY] == 0) {
                stack[stack_size++] = newX * m + newY;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);

    matrix = (int *) calloc(n * m, sizeof(int));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 由于matrix是一维数组，所以这里(i, j)二维坐标也要转成一维坐标
            scanf("%d", &matrix[i * m + j]);
        }
    }

    dfs();

    printf("%dn", ans);

    return 0;
}