bullseye bullseye - 3 months ago 18
Java Question

Getting a wrong answer on ABCPATH on SPOJ for very long time

//Here is the code:
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.io.*;


public class ABCPATH {

public static int computeLongest(char[][] connect, int i, int j, int[][] dp) {
if (dp[i][j] != 0) {
return dp[i][j];
}
int max = 1;
char c = connect[i][j];
c++;
int dy[] = {0, 0, -1, 1, 1, -1, 1, -1};
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
for (int k = 0; k < dx.length; k++) {
int inew = i + dy[k];
int jnew = j + dx[k];
if (inew >= 0 && inew < connect.length && jnew >= 0 && jnew < connect[0].length) {
if (connect[inew][jnew] == c) {

return dp[i][j] = Math.max(max, 1 + computeLongest(connect, inew, jnew, dp));
}
}
}
return max;

}

public static void main(String[] args) throws IOException {
//Scanner s = new Scanner(System.in);
Scanner sc = new Scanner(System.in);
int k = 1;
int p = 1;
while (k != -1) {
String in[] = sc.nextLine().split(" ");
if (Integer.parseInt(in[0]) != 0 && Integer.parseInt(in[1]) != 0) {

int r = Integer.parseInt(in[0]);
int c = Integer.parseInt(in[1]);
char[][] connect = new char[r][c];
for (int i = 0; i < r; i++) {
String in2 = sc.nextLine();
for (int j = 0; j < in2.length(); j++) {
connect[i][j] = in2.charAt(j);


}
}
int max = 0;
int dp[][] = new int[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (connect[i][j] == 'A') {
max = Math.max(max, computeLongest(connect, i, j, dp));
}
}
}

System.out.println("Case " + p + ": " + max);
p++;

}
else {
k = -1;
}
}


}
}


The link to the problem is :http://www.spoj.com/problems/ABCPATH/, Even on test 1 it give a wrong answer. But the algo I have used is correct as I have verified from some people
with successful submissions.

Answer

Sample input from SPOJ gives me the correct answer:

Case 1: 4

Can you provide the input that produces incorrect results?

OK, to help you a bit. Consider these tho cases:

3 3
ABC
BFG
CDE
0 0


3 3
ABC
BFD
CGE
0 0

They should both return the same results but they don't.