在网格中查找最大点，以便始终覆盖特定点

2018-06-22 18:09:40

题

杰夫喜欢玩游戏，贪吃蛇（诺基亚时代的老游戏）是他的最爱之一。然而，在玩过饕s蛇多次后，他终于厌倦了原来的规则。

为了给这款老游戏带来新的挑战，杰夫推出了新的规则：

地面是一个网格，有n行m列（1 <= n，m <= 500）。

每个单元格包含一个值v（-1 vi 99999），如果v是-1，那么这个单元格被阻塞，≤≤并且蛇不能通过，否则当蛇访问这个单元格后，你可以得到v点。

蛇可以从沿着该地面的左边界的任何单元开始并行进，直到它最终停止在右边界的一个单元处。

在这次旅行中，蛇只能上/下/右，并且只能访问每个单元格一次。

特别案例：

一个。即使在左边界和右边界，蛇也可以上下移动。

湾当蛇位于一列的顶部单元格时，它仍然可以上升，这要求玩家支付所有当前点数，然后蛇将被传送到该列的底部单元格，反之亦然。

创建这样一款新游戏后，杰夫很困惑如何获得最高分。请帮他写一个程序来解决这个问题。

输入第一行包含两个整数n（行）和m（列），（1 <= n，m <= 500），由一个空格分隔。

接下来n行描述网格。每行包含m个整数vi（-1≤vi≤99999）vi = -1表示单元格被阻塞。

产量

输出您可以获得的最高分数。如果蛇不能到达右侧，则输出-1。

范围

•每次测试的内存限制：256兆字节

•每次测试的时间限制：编译速度越快越好

我已经用下面给出的代码解决了问题，然后面试官改变了问题，并要求现在蛇总是需要在其路径中采取特定的点，包括该特定点只有当点是（2,1）那么它必须总是在其路径上取3。 比我们必须找到最大的总和？ 我无法在面试中做到这一点，请任何人帮助它，只是在这类问题完成后才提供链接。 我应用dfs面试官告诉dfs在这个问题上是错误的，我无法弄清楚它为什么是错误的以及有什么可以更好的算法来找到答案

码

 import java.util.Scanner;

public class worksApplication {
    private static int rows;
    private static int col;
    private static int[][] a;

    private static boolean[][] check;
    private static int max1;
    private static int max;

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

        a = new int[rows][col + 1];
        check = new boolean[rows][col];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < col + 1; j++) {
                if (j == col) {
                    a[i][j] = -1;
                } else
                    a[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < rows; i++) {
            if (a[i][0] != -1) {
                check[i][0] = true;
                solve(i, 0, a[i][0]);
                check[i][0] = false;

                max1 = Math.max(max, max1);
            }
        }
        System.out.println(max1);
    }

    private static void solve(int i, int j, int sum) {
        // TODO Auto-generated method stub

        if (i - 1 == -1 && check[rows - 1][j] == false && a[rows - 1][j] != -1) {
            check[rows - 1][j] = true;
            solve(rows - 1, j, a[rows - 1][j]);
            check[rows - 1][j] = false;
        }
        if (i - 1 >= 0 && check[i - 1][j] == false && a[i - 1][j] != -1) {
            check[i - 1][j] = true;
            solve(i - 1, j, sum + a[i - 1][j]);
            check[i - 1][j] = false;
        }
        if (a[i][j + 1] != -1 && check[i][j + 1] == false) {
            check[i][j + 1] = true;
            solve(i, j + 1, sum + a[i][j + 1]);
            check[i][j + 1] = false;
        }
        if (i + 1 == rows && a[0][j] != -1 && check[0][j] == false) {
            check[0][j] = true;
            solve(0, j, a[0][j]);
            check[0][j] = false;
        }
        if (i + 1 < rows && a[i + 1][j] != -1 && check[i + 1][j] == false) {
            check[i + 1][j] = true;
            solve(i + 1, j, sum + a[i + 1][j]);
            check[i + 1][j] = false;
        }

        if (max < sum) {

            max = sum;
        }

    }

}

链接地址: http://www.djcxy.com/p/63845.html

上一篇: Find max points in grid such that a particular point is always covered

下一篇: Find the maximum sum path of a matrix from left column to right column?