题解

题目描述

小华设计了一款简单的水果忍者游戏，游戏中存在一个 m*n 的网格，网格的每个单元格可能包含以下内容：

• 0：表示该单元格为空，不可滑动。
• -5：表示该单元格包含炸弹，滑动到炸弹上会失去 5 分。
• 正整数：表示该单元格包含水果，滑动到水果上会获得该水果的分数。

玩家可以从网格中的任意一个非空单元格出发，选择四个方向（上下左右）滑动到相邻的单元格，但不可滑动到空单元格（值为 0）。每个单元格只能滑动一次，滑动过的单元格会变为空单元格。

要求玩家找到最高得分路径，即从某个非空单元格出发，经过若干滑动，得到的最大得分。

题解思路

这道题本质上是一个图的深度优先搜索（DFS）问题。每个非空单元格可以看作一个节点，四个方向的相邻单元格就是节点之间的边。我们需要找到一条路径，使得路径上所有单元格的得分最大，并且路径中不能经过相同的单元格。

解题步骤：

1. DFS遍历：

   • 对于每个非空的单元格，使用深度优先搜索（DFS）探索所有可能的路径。
   • 在DFS过程中，累计当前路径的得分，同时保持一个 visited 数组来标记哪些单元格已经被访问过，避免重复访问。

2. 递归终止条件：

   • 当无法继续滑动（即所有相邻的单元格都已访问或者为 0）时，结束当前路径的探索。

3. 方向选择：

   • 我们可以通过四个方向（上下左右）来遍历相邻的单元格。

4. 计算最大得分：

   • 每次DFS结束时，更新最大得分。

5. 优化点：

   • 使用一个全局变量记录最大得分。
   • 每次从一个非空单元格开始DFS，避免从空单元格或者炸弹单元格开始。

时间复杂度：

• 每个单元格最多访问一次，因此时间复杂度为 O(m * n)，其中 m 和 n 分别是网格的行数和列数。

空间复杂度：

• 由于DFS使用了递归调用栈，空间复杂度为 O(m * n)，需要存储 visited 数组和递归栈。

代码实现

Python

def max_score(m, n, grid):
    # 定义四个方向：上下左右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def dfs(x, y, score, visited):
        # 当前路径的最大得分
        max_score = score
        visited[x][y] = True  # 标记当前单元格为已访问

        # 搜索四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] != 0:
                next_score = grid[nx][ny]
                # 递归到下一个单元格
                max_score = max(max_score, dfs(nx, ny, score + next_score, visited))

        visited[x][y] = False  # 恢复当前单元格的访问状态
        return max_score

    # 初始化最大得分
    result = float('-inf')

    # 对每个非空的单元格进行DFS遍历
    for i in range(m):
        for j in range(n):
            if grid[i][j] != 0:  # 如果是水果或炸弹
                visited = [[False] * n for _ in range(m)]  # 重置访问标记
                score = grid[i][j]  # 初始分数为当前单元格的分数
                result = max(result, dfs(i, j, score, visited))

    return result

# 读取输入
m, n = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(m)]

# 输出结果
print(max_score(m, n, grid))

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int m, n;
vector<vector<int>> grid;
vector<vector<bool>> visited;
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int dfs(int x, int y, int score) {
    visited[x][y] = true;
    int maxScore = score;

    // 搜索四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] != 0) {
            int nextScore = grid[nx][ny];
            maxScore = max(maxScore, dfs(nx, ny, score + nextScore));
        }
    }

    visited[x][y] = false;  // 恢复访问状态
    return maxScore;
}

int main() {
    cin >> m >> n;
    grid.resize(m, vector<int>(n));
    visited.resize(m, vector<bool>(n, false));

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }

    int result = -1e9;
    // 对每个非空的单元格进行DFS遍历
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 0) {  // 如果是水果或炸弹
                result = max(result, dfs(i, j, grid[i][j]));
            }
        }
    }

    cout << result << endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    static int m, n;
    static int[][] grid;
    static boolean[][] visited;
    static int[] directions = {-1, 0, 1, 0, 0, -1, 0, 1};  // 上下左右

    // 深度优先搜索
    static int dfs(int x, int y, int score) {
        visited[x][y] = true;
        int maxScore = score;

        // 搜索四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + directions[2 * i];
            int ny = y + directions[2 * i + 1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] != 0) {
                maxScore = Math.max(maxScore, dfs(nx, ny, score + grid[nx][ny]));
            }
        }

        visited[x][y] = false;  // 恢复访问状态
        return maxScore;
    }

    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();
            }
        }

        int result = Integer.MIN_VALUE;

        // 对每个非空的单元格进行DFS遍历
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    result = Math.max(result, dfs(i, j, grid[i][j]));
                }
            }
        }

        System.out.println(result);
    }
}

题目内容

小明设计了一款简单的水果忍者游戏，具体玩法如下:

(1)在m*n的网格，每个单元格中随机放着一个水果，或炸弹，或为空;为了方便表示，单元格中为整数，0表示空单元格，-5表示炸弹单元格，正整数表示水果单元格得分

(2)玩家可以滑动手指到水果或者炸弹上;滑到水果单元格会有对应加分，滑到炸弹单元格减5分，每个单元格被滑过后，将变为空单元格;不允许滑到空单元格上，滑到

(3)玩家可以从网格中任意一个非空单元格出发，每次从当前位置向上下左右四个方向滑;

请计算此局游戏最高得分

输入描述

第一行输入$m,n$两个正整数，表示整个网格行、列数，以空格分隔($m,n<=25$)

接下来依次输入$m$行，每行$n$个整数(取值范围:$0$，$-5$，正整数)，以空格分隔

输出描述

输出此局游戏最高得分

样例1

输入

3 3
0 6 0
5 8 7
0 9 0

输出

24 

说明

得分最高的滑动路径:$9->8->7$

样例2

输入

5 3
1 -5 7
2 0 6
3 4 5
-5 3 -5
9 0 20

输出

45

说明

得分最高的滑动路径:$20 ->-5 -> 3 -> 4 -> 5-> 6->7->-5 -> 1->2->3->-5-> 9$