Find max points in grid such that a particular point is always covered

2018-06-22 18:09:41

Question

Jeff loves playing games, Gluttonous snake( an old game in NOKIA era ) is one of his favourites. However, after playing gluttonous snake so many times, he finally got bored with the original rules.

In order to bring new challenge to this old game, Jeff introduced new rules :

The ground is a grid, with n rows and m columns(1 <= n, m <= 500).

Each cell contains a value v (-1 vi 99999), if v is -1, then this cell is blocked, ≤ ≤ and the snake can not go through, otherwise, after the snake visited this cell, you can get v point.

The snake can start from any cell along the left border of this ground and travel until it finally stops at one cell in the right border.

During this trip, the snake can only go up/down/right, and can visit each cell only once.

Special cases :

a. Even in the left border and right border, the snake can go up and down.

b. When the snake is at the top cell of one column, it can still go up, which demands the player to pay all current points , then the snake will be teleported to the bottom cell of this column and vice versa.

After creating such a new game, Jeff is confused how to get the highest score. Please help him to write a program to solve this problem.

Input The first line contains two integers n (rows) and m (columns), (1 <= n, m <= 500), separated by a single space.

Next n lines describe the grid. Each line contains m integers vi (-1 ≤ vi ≤ 99999) vi = -1 means the cell is blocked.

Output

Output the highest score you can get. If the snake can not reach the right side, output -1.

Limits

• Memory limit per test : 256 megabytes

• Time limit per test : The faster the better Compile

I have solved the question with code given below then the interviewer changes the question and asked that now the snake always has to take a particular point in its route that is path including that particular point are only valid like if point is (2,1) then it has to take 3 in its path always. and than we have to find the max sum ? i was not able to do it in the interview please please any one help it , just provide link only where this type of problem is done. I applied dfs interviewer told dfs is wrong in this question , i am not able to figure it out why it is wrong and what can be better algorithm to find the answer

Code

 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/63846.html

上一篇: 在锯齿形的2D网格上向外螺旋

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