java在很长一段时间内在SPOJ上的ABCPATH上得到了错误的答案
//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;
}
}
}
}
这个问题的链接是:http://www.spoj.com/problems/ABCPATH/,即使在测试1中,它也给出了错误的答案。但是我使用的算法是正确的,我已经从一些人那里验证过了 提交成功
# 1 楼答案
嗯,基本逻辑没有问题
也许对
<>我的C++代码片段可能有帮助:dp[i][j]
的公式稍作修改可能会有所帮助。 不要在for循环中计算dp[i][j]
,试着找出路径的最大长度,即所有8种可能性的最大长度,然后将其与dp[i][j]
相等# 2 楼答案
SPOJ的样本输入给了我正确的答案:
案例1:4
你能提供产生错误结果的输入吗
好的,帮你一点忙。考虑这些情况:
它们都应该返回相同的结果,但它们不会