獲取上SPOJ ABCPATH一個錯誤的答案很長一段時間

-1

//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把它給一個錯誤的答案。但是我使用的算法是正確的，因爲我已經從一些人驗證了成功的提交。從SPOJ獲取上SPOJ ABCPATH一個錯誤的答案很長一段時間

來源

2013-12-19 bullseye

始終的問題給出了問題的描述。到SPOJ的網址是不夠的。 – xenteros

樣品輸入給了我正確的答案：

案例1：4

你能提供產生不正確的結果輸入？

好的，幫助你一下。考慮這些情況：

3 3 
ABC 
BFG 
CDE 
0 0 


3 3 
ABC 
BFD 
CGE 
0 0

他們都應該返回相同的結果，但他們不。

來源

2013-12-19 13:37:48 michali

spoj不提供給你測試用例 – bullseye

你在那裏的問題很小;）看看dp數組 - 你首先不需要它（或者我錯過了什麼）。此外，你正在完成遞歸到早 - 這就是爲什麼你只是正確的（第一種情況下）沒有檢查第二個路徑：]希望它有幫助;） – michali

謝謝，我明白了。 dp被用來減少時間，否則我會得到一個tle – bullseye

-2

好吧，基本邏輯沒有問題。

也許dp[i][j]公式的一些變化可能會有所幫助。而不是計算for-loop內的dp[i][j]嘗試找到所有8種可能性的最大路徑長度，即最大值，然後將其與dp[i][j]等值。從我的C代碼

片段++可能會幫助：

int dfs(int i,int j) 
{ 

    if(dp[i][j]!=0) 
    { 

    return dp[i][j]; 
    } 

    int val=1; 
for(int k=0;k<8;k++) 
{ 

    int i1=i+x[k]; 
    int j1=j+y[k]; 

    if(i1>=0&&i1<h&&j1>=0&&j1<w) 
    { 
     if((mat[i1][j1]==mat[i][j]+1)&& visit[i1][j1]==0) 
     { 

      //path++; //important don't do this in recursive functions with for loops 
      visit[i1][j1]=1; 

      //return(dp[i][j]=max(path ,dfs(i1,j1,path+1)));//this is causing problem here 
      val=max(val ,1+dfs(i1,j1)); 



     } 
    } 

} 

return(dp[i][j]=val); 

}

來源

2016-09-05 13:31:21 truecoder

獲取上SPOJ ABCPATH一個錯誤的答案很長一段時間

回答

相關問題