-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

私はあなたのアプローチを少し修正します。これは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]ifをインクリメントしますINP[r][c] == 'P'a

最後に、最終的な解決策はTAB[ki+2][kj]（ki, kjコードから）です。

于 2013-03-02T13:22:06.160 に答える
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])

したがって、現在の位置からのすべてのパスを確認する必要があります。コードが示唆しているのは、1つのパスでのみ実行することです（else if's1つのパスのみを移動するシミュレーション）。

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 に答える