java - Google Kickstart : Round C, 2020:稳定墙 - 回溯解决方案错误

Question

这是我提到的问题:https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff43/00000000003379bb .

Problem

Apollo is playing a game involving polyominos. A polyomino is a shape made by joining together one or more squares edge to edge to form a single connected shape. The game involves combining N polyominos into a single rectangular shape without any holes. Each polyomino is labeled with a unique character from A to Z.

Apollo has finished the game and created a rectangular wall containing R rows and C columns. He took a picture and sent it to his friend Selene. Selene likes pictures of walls, but she likes them even more if they are stable walls. A wall is stable if it can be created by adding polyominos one at a time to the wall so that each polyomino is always supported. A polyomino is supported if each of its squares is either on the ground, or has another square below it.

Apollo would like to check if his wall is stable and if it is, prove that fact to Selene by telling her the order in which he added the polyominos.

对这道题的分析提出了一种使用拓扑排序的方法。我试图想出另一种解决问题的方法(尽管速度较慢)，该方法正确地解决了示例测试用例，但在完整的测试集上给出了错误的答案(WA)。谁能指出逻辑中的错误，如果可能的话，建议纠正错误的方法？

该解决方案使用回溯。首先，我们列出底层的独特字符 - 因为在顶部添加形状之前必须先填充其中至少一个字符。然后，我们迭代这些，并为每个发送递归调用，使用相邻元素作为下一个选项列表。如果我们匹配给定的矩阵，我们将其打印出来，否则我们返回。

这是代码-

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

class StableWall {

    public static void main(String[] args) throws IOException {
        //Taking input in required format
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        for(int i = 0; i < t; i++) {
            String[] text = br.readLine().trim().split(" ");
            int r = Integer.parseInt(text[0]);
            int c = Integer.parseInt(text[1]);
            char[][] mat = new char[r][c];
            for(int j = 0; j < r; j++) {
                String line = br.readLine();
                char[] chars = line.toCharArray();
                for(int k = 0; k < c; k++)
                    mat[j][k] = chars[k];
            }
            System.out.printf("Case #%d: ", i+1);
            solve(mat, r, c);
            System.out.println();
        }
    }

    static void solve(char[][] mat, int r, int c) {
        //make empty 2D array to hold current state of matrix
        char[][] currState = new char[r][c];
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                currState[i][j] = '0';
            }
        }

        //used holds list of alphabets we have already used and must not repeat
        ArrayList<Character> used = new ArrayList<>();

        //options holds list of alphabets that may hold the next possible alphabet
        //on first iteration, it contains elements of the first row
        //on subsequent recursive calls, it holds adjacent elements
        ArrayList<Character> options = firstRowElements(mat, r, c);

        //start function
        boolean val = recurse(mat, r, c, currState, options, used, 0);

        //print -1 if stable wall not possible
        if(!val)
            System.out.printf("-1\n");
    }

    static boolean recurse(char[][] mat, int r, int c, char[][] currState, ArrayList<Character> options, ArrayList<Character> used, int count) {

        //if we reach intended matrix state, print elements in order and return true
        if(equals(currState, mat, r, c)) {
            int len = used.size();
            for(int i = 0; i < len; i++)
                System.out.printf("%c", used.get(i));
            return true;
        }

        //create copy of current state since it will be modified in recursive calls
        char[][] currStateCopy = new char[r][c];
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++)
                currStateCopy[i][j] = currState[i][j];
        }
        //create copy of used elements since it will be modified in recursive calls
        ArrayList<Character> usedCopy = new ArrayList<>(used);

        int len = options.size();
        //loop over all available options
        for(int i = 0; i < len; i++) {
            //fill current state with option i
            fillBoard(currStateCopy, mat, options.get(i), r, c);
            //add option i to list of used alphabets
            usedCopy.add(options.get(i));

            //if current state is not stable, reset state and used lists, and move to next iteration
            if(isFail(currStateCopy, r, c)) {
                for(int j = 0; j < r; j++) {
                    for(int k = 0; k < c; k++)
                        currStateCopy[j][k] = currState[j][k];
                }
                usedCopy = new ArrayList<>(used);
                continue;
            }

            //find options for next alphabet, by finding adjacent elements
            ArrayList<Character> new_options = findAdj(currStateCopy, mat, options.get(i), usedCopy, r, c);

            //if future call is true, stop and return true
            if(recurse(mat, r, c, currStateCopy, new_options, usedCopy, count+1))
                return true;

            //reset state and used lists
            for(int j = 0; j < r; j++) {
                for(int k = 0; k < c; k++)
                    currStateCopy[j][k] = currState[j][k];
            }
            usedCopy = new ArrayList<>(used);
        }

        return false;
    }

    //return list of unique alphabets in ground floor
    static ArrayList<Character> firstRowElements(char[][] mat, int r, int c) {
        ArrayList<Character> options = new ArrayList<>();
        for(int i = 0; i < c; i++) {
            if(!options.contains(mat[r-1][i]))
                options.add(mat[r-1][i]);
        }
        return options;
    }

    //return true if current state equals intended final matrix state
    static boolean equals(char[][] currState, char[][] mat, int r, int c) {
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                if(mat[i][j] != currState[i][j])
                    return false;
            }
         }
        return true;
    }

    //fill the current state with all occurences of particular alphabet
    static void fillBoard(char[][] currState, char[][] mat, char ch, int r, int c) {
        for(int i = r-1; i >= 0; i--) {
            for(int j = 0; j < c; j++) {
                if(mat[i][j] == ch)
                    currState[i][j] = ch;
            }
        }
    }

    //return true if current state is not stable
    static boolean isFail(char[][] currState, int r, int c) {
        for(int i = 0; i < r-1; i++) {
            for(int j = 0; j < c; j++) {
                if(currState[i][j] != '0' && currState[i+1][j] == '0')
                    return true;
            }
        }
        return false;
    }


    //find options by checking adjacent elements to the given alphabet
    static ArrayList<Character> findAdj(char[][] currState, char[][] mat, char ch, ArrayList<Character> used, int r, int c) {
        ArrayList<Character> options = new ArrayList<>();
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                if(mat[i][j] == ch) {
                    if(j < c-1 && mat[i][j+1] != '0' && !used.contains(mat[i][j+1]) && !options.contains(mat[i][j+1]))
                        options.add(mat[i][j+1]);
                    if(i < r-1 && mat[i+1][j] != '0' && !used.contains(mat[i+1][j]) && !options.contains(mat[i+1][j]))
                        options.add(mat[i+1][j]);
                    if(j >= 1 && mat[i][j-1] != '0' && !used.contains(mat[i][j-1]) && !options.contains(mat[i][j-1]))
                        options.add(mat[i][j-1]);
                    if(i >= 1 && mat[i-1][j] != '0' && !used.contains(mat[i-1][j]) && !options.contains(mat[i-1][j]))
                        options.add(mat[i-1][j]);
                }
            }
        }
        return options;
    }

    //print for debugging
    static void printMatrix(char[][] mat, int r, int c) {
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                System.out.printf("%c", mat[i][j]);
            }
            System.out.printf("\n");
        }
    }
}

Answer 1

我也有同样的问题。

我的代码:

#include <iostream>
#include <vector>
#include <cstring>
#include <set>
#include <algorithm>

using namespace std;

#define ANY_CHAR '0'

struct PairOrder
{
    //second musi isc po first
    //jesli wykryjemy odwrotnie to fail
    char first;
    char second;
    //bool used;

    bool operator <(const PairOrder& b) const
    {
        if (first < b.first)
            return true;
        if (first > b.first)
            return false;
        return second < b.second;
    }
};


int sizeX, sizeY;
char** map;
vector<PairOrder> orders;
vector<char> solution;
set<char> lettersUsed;


bool letterWasUsed(char letter)
{
    for (size_t j = 0; j < solution.size(); ++j)
    {
        if (solution[j] == letter)
            return true;
    }
    return false;
}

bool canPass(char symbol, int exclude)
{
    for (size_t i = 0; i < orders.size(); ++i)
    {
        if (i != exclude && orders[i].second == symbol)
        {
            char newSymbol = orders[i].first;
            //jak znajde symbol po prawej to musze sprawdzic czy po ten symbol po lewej uzyty
            if (!(newSymbol == ANY_CHAR || lettersUsed.find(newSymbol) != lettersUsed.end()))
            {
                return false;
            }
        }           
    }
    return true;
}

void solve(char symbol)
{
    for (size_t i = 0; i < orders.size(); ++i)
    {
        if (orders[i].first == symbol)
        {
            char letter = orders[i].second;
            if (canPass(letter, i))
            {
                if (letter != ANY_CHAR)
                {
                    solution.push_back(letter);
                    lettersUsed.insert(letter);
                }

                //found = true;
                solve(orders[i].second);
            }
        }
    }
}

void scanMap()
{
    set<PairOrder> orderSet;
    for (int y = 0; y < sizeY; ++y)
    {
        for (int x = 0; x < sizeX; ++x)
        {
            if (y < sizeY - 1)
            {
                char c1 = map[y + 1][x];
                char c2 = map[y    ][x];
                if (c1 != c2)
                    orderSet.insert({ c1, c2 });
            }
            else
            {
                orderSet.insert({ ANY_CHAR, map[y][x] });
            }
        }
    }
    orders.clear();
    for (auto order : orderSet)
    {
        orders.push_back(order);
    }
}

int main()
{
    int testCasesCount;
    cin >> testCasesCount;
    for (int test = 1; test <= testCasesCount; ++test)
    {
        cin >> sizeY; //rows
        cin >> sizeX; //columns

        set<char> letterSet;
        map = new char*[sizeY];
        for (int y = 0; y < sizeY; ++y)
        {
            map[y] = new char[sizeX];
            for (int x = 0; x < sizeX; ++x)
            {
                char c;
                cin >> c;
                map[y][x] = c;
                letterSet.insert(c);
            }
        }

        solution.clear();
        lettersUsed.clear();
        scanMap();
        solve(ANY_CHAR);

        cout << "Case #" << test << ": ";
        if (solution.size() == letterSet.size())
        {
            for (auto c : solution)
                cout << c;
            cout << endl;
        }
        else
        {
            cout << "-1" << endl;
        }
    }

    //system("pause");

    return 0;
}

我在样本上测试了它 - 工作正常。
我在很多情况下测试过它。

10
2 7
FBBDDCC
AAACCCE
3 3
国内长途
英国广播公司
AAA级
3 3
AAA级
AAA级
AAA级
3 3
ABC
防御
GHI
3 3
AAC
BAA
AAA级
3 5
达阿克
达巴克
AABAC
3 3
AAA级
ABA
ABA
3 3
ABA
ABA
AAA级
1 1
一个
5 1
一个
B
C
D
一个

它回答:
案例#1:ABFECD
案例#2:ABCD
案例#3:A
案例#4:GDAHEBIFC
案例#5:-1
案例#6:BADC
案例#7:文学士
案例#8:AB
案例#9:A
案例#10:-1

所以一切看起来都很好。

但谷歌总是声称“错误答案”。

任何人都可以找到对我的解决方案给出错误答案的测试吗？
为什么 Google 声称答案错误？

这真的很烦人，有人写了很好的解决方案，却得了 0 分，甚至没有办法知道为什么......

感谢您的帮助。

最好的问候