0

This is a problem from TalentBuddy (https://www.talentbuddy.co/challenge/52a9121cc8a6c2dc91481f90525870614af0110af3834439) Casian is infiltrating an alien base to destroy the controls of the mothership that threatens planet PACO. The base is a rectangle of size N x M, where every square meter has an associated light level Li,j.

Because of his abilities, the aliens can't see him immediately unless he is in a square of light level K or if the sum of the last X squares Casian went through is at least (X * K) / 2 (integer part).

Given the values for N, M, X, K, Casian's position (XCa,YCa), the position of the controls (XCo,YCo) and the light levels for each square meter of the base Your task is to write a function that prints to the standard output (stdout) the length of the shortest path Casian can take to get to the controls, as well as the risk value for the least risky path the risk value for a path is the sum of the light levels of all the squares he passed through

Note that your function will receive the following arguments: data which is an integer array of length 8 containing the values for N, M, X, K, XCa,YCa, XCo,YCo in this specific order base which is an array of N x M integers representing the light levels for each square meter of the base. The first N integers represent the first line of the rectangle base. The next N represent the second line and so on.

Data constraints
0 < N, M < 100
Efficiency constraints
your function is expected to print the requested result and return in less than 2 seconds

Example
Input
data: 4 4 3 7 1 1 4 4
base: 1 1 4 4 0 4 4 4 7 3 2 3 14 9 8 3

Output
6 16

And here is my program, but it cannot pass the online judge because of timeout issue.

Could anyone help me on that? Thanks

static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
public static void paco(Integer[] D, Integer[] B) {

    int N = D[0], M = D[1], X = D[2], K = D[3], X0 = D[4], Y0 = D[5], X1 = D[6], Y1 = D[7];
    X0--;   Y0--;   X1--;   Y1--;
    int[][] C = new int[N][M];
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            C[i][j] = B[i*N+j];
        }
    }

    boolean[][] vis = new boolean[N][M];
    int minLen = Integer.MAX_VALUE, minRisk = Integer.MAX_VALUE;
    List<Integer> risks = new LinkedList<>();
    risks.add(C[X0][Y0]);
    vis[X0][Y0] = true;

    Queue<Item> queue = new LinkedList<>();
    queue.add(new Item(X0, Y0, 0, risks, C[X0][Y0], C[X0][Y0]));

    while(!queue.isEmpty()) {
        Item cur = queue.poll();

        vis[cur.x][cur.y] = true;
        if(cur.x == X1 && cur.y == Y1) {
            if(cur.length <= minLen) {
                minLen = cur.length;
                if(cur.sum < minRisk) {
                    minRisk = cur.sum;
                }
            } else break;
        }

        if(cur.x > X1 && cur.y > Y1)    break;

        for(int i=0; i<4; i++) {
            int nx = cur.x+dx[i], ny = cur.y+dy[i];
            if(nx>=0 && nx<N && ny>=0 && ny<M && !vis[nx][ny] && C[nx][ny]<K) {
                int newPartialSum = cur.partialSum;
                List<Integer> newRisks = new LinkedList<>(cur.risks);
                boolean full = false;
                int old = -1;
                if(newRisks.size() < X) {
                    newRisks.add(C[nx][ny]);
                    newPartialSum += C[nx][ny];
                } else {
                    full = true;
                    old = newRisks.get(0);
                    newRisks.remove(0);
                    newRisks.add(C[nx][ny]);
                    newPartialSum -= old;
                    newPartialSum += C[nx][ny];
                }
                if(newPartialSum < X*K/2) {
                    queue.add(new Item(nx, ny, cur.length+1, newRisks, C[nx][ny]+cur.sum, newPartialSum));
                }
            }
        }
    }

    System.out.println(minLen + " " + minRisk);
}

static class Item {
    int length, x, y, sum, partialSum;
    List<Integer> risks;
    public Item(int x, int y, int length, List<Integer> risks, int sum, int partialSum) {
        this.x = x;
        this.y = y;
        this.length = length;
        this.risks = risks;
        this.sum = sum;
        this.partialSum = partialSum;
    }
}
2
  • Have you tried running it locally in a Java development environment? Did it finish? Did it produce correct results? Aug 14, 2015 at 21:34
  • Hi Andy, yes. It finishes on small sample test data provided. and it also produces correct result.
    – spiralmoon
    Aug 14, 2015 at 22:02

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.