题面简述

该题是一个经典的路径搜索问题，我们需要在一个二维的矩阵中从起始位置（数字0）出发，经过所有食物的位置（数字2），最终到达家的位置（数字1）。每个食物只能经过一次，并且路径中不能碰到障碍（数字3）。我们的任务是计算出从起点出发，经过所有食物并到达家的路径总数。

解题思路

1. 回溯/深度优先搜索（DFS）

我们可以使用深度优先搜索（DFS）来探索所有可能的路径。DFS 会从起点开始，沿着四个方向（上下左右）逐步进行搜索，在每次访问一个新的位置时更新路径。如果到达家且收集了所有食物，那么这条路径是可行的。

2. 递归回溯

在每一步，我们都将当前位置标记为已访问，并递归地搜索所有的邻接点。在搜索过程中：

• 如果当前格子是食物，我们增加已收集的食物数量。
• 如果已经收集了所有食物并且到达了家，则此路径计数加1。
• 进行回溯时，我们恢复当前格子的状态。

3. 状态管理

我们需要一个 visited 数组来记录每个格子是否已被访问。每次递归搜索时，我们都需要判断是否能进入某个位置，确保不会重复经过同一格子。

4. 剪枝

如果当前路径已经不能再收集到足够的食物，或者已经访问过的路径再次出现，则应提前结束搜索，避免不必要的计算。

代码实现

c++

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

int gridMap[10][10]; // 存储地图
bool visited[10][10]; // 标记已访问位置
int m, n;             // 地图大小：m 行, n 列
int startX, startY;   // 起点坐标(数字0)
int homeX, homeY;     // 家的坐标(数字1)
int totalFoods = 0;   // 食物数量(数字2)
long long pathCount = 0; // 记录有效路径的数量

// 四个方向：下、上、右、左
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 判断坐标 (x, y) 是否在地图内且可以走
bool isValid(int x, int y) {
    return x >= 0 && x < m && y >= 0 && y < n && gridMap[x][y] != 3 && !visited[x][y];
}

// 深度优先搜索
void dfs(int x, int y, int foodCollected) {
    // 如果到达家，并且已收集所有食物，则找到一条路径
    if (x == homeX && y == homeY) {
        if (foodCollected == totalFoods) {
            pathCount++;
        }
        return;
    }

    // 临时保存当前格子的值
    int oldVal = gridMap[x][y];

    // 如果是食物，收集并标记为普通空地(避免重复)
    if (oldVal == 2) {
        foodCollected++;
        gridMap[x][y] = 0; // 食物位置变成空地
    }

    // 标记当前位置为已访问
    visited[x][y] = true;

    // 递归探索四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (isValid(nx, ny)) {
            dfs(nx, ny, foodCollected);
        }
    }

    // 回溯：恢复当前格子的状态
    visited[x][y] = false;
    if (oldVal == 2) {
        gridMap[x][y] = 2; // 恢复食物格子
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    
    // 输入地图数据
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> gridMap[i][j];
        }
    }

    // 初始化数据
    memset(visited, false, sizeof(visited));

    // 找到起点、家的位置，并统计食物的总数
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (gridMap[i][j] == 0) {
                startX = i;
                startY = j;
            } else if (gridMap[i][j] == 1) {
                homeX = i;
                homeY = j;
            } else if (gridMap[i][j] == 2) {
                totalFoods++;
            }
        }
    }

    // 从起点开始进行 DFS
    dfs(startX, startY, 0);

    // 输出最终的有效路径数量
    cout << pathCount << "\n";

    return 0;
}

java

import java.util.*;

public class Main {

    static int m, n;
    static int[][] grid;
    static boolean[][] visited;
    static int startX, startY;
    static int homeX, homeY;
    static int totalFoods = 0;
    static long pathCount = 0;

    // 四个方向：下、上、右、左
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static boolean isValid(int x, int y) {
        // 范围内、不是障碍(3)、且未访问
        return x >= 0 && x < m && y >= 0 && y < n
               && grid[x][y] != 3
               && !visited[x][y];
    }

    // DFS 回溯
    public static void dfs(int x, int y, int foodCollected) {
        // 如果到达家，且食物全部收集
        if (x == homeX && y == homeY) {
            if (foodCollected == totalFoods) {
                pathCount++;
            }
            return;
        }

        int oldVal = grid[x][y];
        // 如果此处是食物，收集后临时置为 0
        if (oldVal == 2) {
            foodCollected++;
            grid[x][y] = 0;
        }

        visited[x][y] = true;

        // 探索四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (isValid(nx, ny)) {
                dfs(nx, ny, foodCollected);
            }
        }

        // 回溯
        visited[x][y] = false;
        if (oldVal == 2) {
            grid[x][y] = 2;
        }
    }

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

        m = sc.nextInt();
        n = sc.nextInt();
        grid = new int[m][n];
        visited = new boolean[m][n];

        // 读入地图
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        // 找到起点、家，并统计食物总数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    startX = i;
                    startY = j;
                } else if (grid[i][j] == 1) {
                    homeX = i;
                    homeY = j;
                } else if (grid[i][j] == 2) {
                    totalFoods++;
                }
            }
        }

        // 从起点开始 DFS
        dfs(startX, startY, 0);

        // 输出路径总数
        System.out.println(pathCount);
    }
}

python

import sys
sys.setrecursionlimit(10**7)

def dfs(x, y, collected):
    """
    x, y: 当前坐标
    collected: 当前已收集的食物数量
    """
    global path_count, total_foods

    # 如果到达家（1），且已收集所有食物，则找到一条可行路径
    if x == home_x and y == home_y:
        if collected == total_foods:
            path_count += 1
        return

    # 记录当前格子的原始值
    old_val = grid[x][y]

    # 如果是食物(2)，收集食物并将其临时改成普通空地(0)
    if old_val == 2:
        collected += 1
        grid[x][y] = 0

    # 标记为已访问，避免在同一路径中重复进入
    visited[x][y] = True

    # 尝试向四个方向移动（上、下、左、右）
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < m and 0 <= ny < n:        # 边界检查
            if not visited[nx][ny] and grid[nx][ny] != 3:
                # 若未访问且不是障碍(3)，则继续 DFS
                dfs(nx, ny, collected)

    # 回溯：恢复现场
    visited[x][y] = False
    if old_val == 2:
        grid[x][y] = 2  # 恢复食物状态

def solve():
    global m, n, grid, visited
    global start_x, start_y, home_x, home_y
    global path_count, total_foods

    # 读取行列大小
    m, n = map(int, sys.stdin.readline().split())

    # 读取地图
    grid = []
    for _ in range(m):
        # 每行 n 个数字，用空格分隔
        row = list(map(int, sys.stdin.readline().split()))
        grid.append(row)

    # 初始化数据
    visited = [[False]*n for _ in range(m)]
    path_count = 0
    total_foods = 0
    start_x = start_y = 0
    home_x = home_y = 0

    # 找到起点(0)、家(1)以及食物总数(2)
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0:
                start_x, start_y = i, j
            elif grid[i][j] == 1:
                home_x, home_y = i, j
            elif grid[i][j] == 2:
                total_foods += 1

    # 从起点开始 DFS
    dfs(start_x, start_y, 0)

    # 输出可行路径的数量
    print(path_count)

# 若是直接运行此脚本，可在此调用 solve()
if __name__ == "__main__":
    solve()

题目内容

一只小蚂蚊出门觅食，请在二维的矩形地图上帮助小蚂蚁找到能够拿到所有的食物并且回家的路。

地图上有几种类型的方格，

起始位置，小蚂蚁当前位置，用数字0表示，只有一个起始位置

家的位置，小蚂蚁家的位置，用数字1表示，只有一个家的位置

食物位置，小蚂蚁可以通过的位置，从该位置通过即获取该位置食物，用数字 $2$ 表示

障碍位置，小蚂蚁无法通过的位置，用数字 $3$ 表示约束:

1.小蚂蚁要把所有的食物全部拿到，如果不能拿到所有的食物，则没有回家的路

2.同一条回家的路每个食物的位置只能经过一次

3.只能上下左右 $4$ 个方向行走

输入描述

第一行为两个数字 $m,n$ 空格分隔。

是二维地图的大小，$m$ 行，$n$ 列接下来是 $m$ 行，每行为 $n$ 个数字，以空格分隔

行列大小小于等于 $10$

输出描述

输出有几条可以回家的路

样例1

输入

3 4
0 2 2 2
2 2 2 2
2 2 1 3

输出

2

说明

以矩阵左上角为坐标(0.0),x轴向下，y轴向右，回家路如下

0,0->0,1->0,2->0,3->1,3->1,2->1,1->1,0->2,0->2,1>2,2

0,0->1,0->2,0->2,1->1,1->0,1->0,2->0,3->1,3>1,2->2,2

共2条

样例2

输入

2 2
0 2
3 1

输出

1

说明

以矩阵左上角为坐标(0.0),x轴向下，y轴向右，回家路如下0,0->0,1->1,1