Почему этот код динамического программирования неверен?

Question

Я делаю this проблема для домашнего задания. Я решил проблему, используя стандартный алгоритм динамического программирования вверх. Мой код показывает ожидаемые результаты в моих тестовых случаях, но на сайте говорится, что он дает неверный ответ. Я не могу понять, где этот код отсутствует. Пожалуйста, помогите мне.

import java.io.*; 
import java.util.*; 
class Main300{ 

public static void main (String[] args) throws java.lang.Exception{ 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    int nn = Integer.parseInt(br.readLine()); 
    for(int j = 0 ; j < nn; j++){ 
     int n = Integer.parseInt(br.readLine()); 
     char[][] a = new char[n][n]; 
     int ki = -1; 
     int kj = -1; 
     for(int i = 0 ; i < n ; i++){ 
      String s = br.readLine(); 
      for(int k = 0 ; k < n; k++){ 
       a[i][k] = s.charAt(k); 
       if(a[i][k] == 'K'){ 
        ki = i; 
        kj = k; 
       } 
      } 
     } 
     System.out.println(ans(a, ki, kj)); 
    } 
} 

private static int ans(char[][] a, int ki, int kj){ 
    int[][] x = new int[a.length][a.length]; 
    for(int j = a.length-1; j >= 0; j--){ 
     for(int i = 0 ; i < a.length; i++){ 
      if(a[i][j] == 'P'){ 
       x[i][j]++; 
      } 
      if(i-2 >= 0 && j+1 <= a.length-1 && a[i-2][j+1] == 'P'){ 
       x[i][j] += x[i-2][j+1]; 
      }else if(i-1 >= 0 && j+2 <= a.length-1 && a[i-1][j+2] == 'P'){ 
       x[i][j] += x[i-1][j+2]; 
      }else if(i+2 <= a.length-1 && j+1 <= a.length-1 && a[i+2][j+1] == 'P'){ 
       x[i][j] += x[i+2][j+1]; 
      }else if(i+1 <= a.length-1 && j+2 <= a.length-1 && a[i+1][j+2] == 'P'){ 
       x[i][j] += x[i+1][j+2]; 
      } 
     } 
    } 
    return x[ki][kj]; 
} 
} 

Answer 1

Ниже приведены причины неправильного ответа:

а) В состав DP будет

a[r][c] = max(a[r-2][c+1], a[r-1][c+2], a[r+1][c+2], a[r+2][c+1])

так что вы должны проверить каждый путь от текущей позиции. Что означает ваш код, так это то, что вы идете и делаете это только по одному пути (else if's имитирует путешествие только по одному пути).

b) Также, как указал Винаяк, `a [i-2] [j + 1] == 'P' позволит вам перейти только в те места, где есть пешка, что не обязательно верно , Вы можете придумать очень тривиальные примеры, чтобы проверить это.

Вот код:

import java.io.*; 
import java.util.*; 

class e1_test{ 

    public static void main (String[] args) throws java.lang.Exception{ 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     int nn = Integer.parseInt(br.readLine()); 
     for(int j = 0 ; j < nn; j++){ 
      int n = Integer.parseInt(br.readLine());char[][] a = new char[n][n]; 
      int ki = -1; 
      int kj = -1; 
      for(int i = 0 ; i < n ; i++){ 
       String s = br.readLine(); 
       for(int k = 0 ; k < n; k++){ 
        a[i][k] = s.charAt(k); 
        if(a[i][k] == 'K'){ 
         ki = i; 
         kj = k; 
        } 
       } 
      } 
      System.out.println(ans(a, ki, kj)); 
     } 
    } 

    private static int ans(char[][] a, int ki, int kj) { 
     int[][] x = new int[a.length][a.length]; 
     for(int j = a.length-1; j >= 0; j--) { 
      for(int i = 0 ; i < a.length; i++) { 
       if(a[i][j] == 'P') { 
        x[i][j]++; 
       } 
       int temp=0; 
       //note the changes from else if's to only if's 
       //removal of [i-2][j+1] == 'P' condition. 
       if(i-2 >= 0 && j+1 <= a.length-1) { 
        if(temp < x[i-2][j+1]) 
         temp = x[i-2][j+1]; 
       } 
       if(i-1 >= 0 && j+2 <= a.length-1) { 
        if(temp < x[i-1][j+2]) 
         temp = x[i-1][j+2]; 
       } 
       if(i+2 <= a.length-1 && j+1 <= a.length-1) { 
        if(temp < x[i+2][j+1]) 
         temp = x[i+2][j+1]; 
       } 
       if(i+1 <= a.length-1 && j+2 <= a.length-1) { 
        if(temp < x[i+1][j+2]) 
         temp = x[i+1][j+2]; 
       } 
       x[i][j] += temp; 
      } 
     } 
     return x[ki][kj]; 
    } 
} 

Answer 2

Я немного изменю ваш подход. Вы обнаружите, что это очень полезно для решений DP. Это поможет вам написать более простое решение, и вы решите свой WA самостоятельно :)

Вместо того, чтобы проверять границы, сделайте таблицу TAB (x в вашем коде) немного больше, в зависимости от вашего отношения.

Значение TAB[r][c] равно максимальное число пешек может захватывать, начиная с (r, c)

В The White Knight проблемы, увидеть, как Конь может пойти 2 строки выше и ниже, и 2 колонки справа. Поэтому сделайте свой TAB[N+4][N+2] вместо TAB[N][N]. Заполните это дополнительное пространство базовым значением, 0 в этом случае.

Отношение довольно проста (что вы закодированы с использованием 4 if-else)

TAB[r][c] = max(TAB[r-2][c+1], TAB[r-1][c+2], TAB[r+1][c+2], TAB[r+2][c+1]) 

И приращения курса TAB[r][c] если INP[r][c] == 'P' (a в вашем случае)

Наконец окончательный решение - TAB[ki+2][kj] (ki, kj из вашего кода).