-1

我正在为家庭作业做这个问题。我已经使用标准的自下而上动态编程算法解决了这个问题。我的代码显示了我的测试用例的预期结果，但网站说它给出了错误的答案。我无法理解缺少此代码的位置。请帮我。

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];
}
}
4

2 回答 2

1

以下是错误答案的原因：

a) 由于 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）正如@Vinayak 指出的那样， `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];
    }
}
于 2013-03-02T14:53:18.527 回答
1

我会稍微修改你的方法。您会发现这对于 DP 解决方案非常有用。这将帮助您编写更简单的解决方案，并且您将自己解决您的 WA :)

不是检查边界，而是根据您的关系使表格TAB（x在您的代码中）更大一点。

的值TAB[r][c]等于它可以捕获的最大棋子数(r, c)

在白骑士问题中，看看骑士如何上下 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来自您的代码）。

于 2013-03-02T13:22:06.160 回答