这是我指的问题：https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff43/00000000003379bb。
问题
[Apollo正在玩涉及多米诺骨牌的游戏。一个多米诺骨牌是一个形状通过边到边将一个或多个正方形连接在一起以形成一个单连接形状。游戏涉及将N个多胺没有任何孔的单个矩形。每个多胺基是标有从A到Z的唯一字符。
[Apollo完成了游戏，并创建了一个包含R行和C列。他拍了张照片并将其发送给他的朋友赛琳娜赛琳娜（Selene）喜欢墙的图片，但她更喜欢它们如果它们是稳定的墙。如果可以通过以下方式创建墙，则该墙是稳定的：一次在墙上添加一个多米诺骨牌，以便每个多米诺骨牌都是一直支持。如果每个正方形都是要么在地面上，要么在下面有另一个正方形。
[Apollo想检查他的墙是否稳定，如果稳定，请证明通过告诉她Selene添加顺序的事实，多义胺。
对这个问题的分析提出了一种使用拓扑排序的方法。我试图提出另一种解决问题的方法（尽管速度较慢），该方法可以正确解决示例测试用例，但在整个测试集上给出错误的答案（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");
}
}
}
我认为这属于code review。
我有完全相同的问题。我的代码：
#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;
}
我在样本上进行了测试-可以。我在很多情况下进行了测试。102 7FBBDDCCAAACCCE3 3DDD英国广播公司AAA级3 3AAA级AAA级AAA级3 3美国广播公司防御GHI3 3AACBAAAAA级3 5DAAAC达巴克阿巴卡3 3AAA级阿巴阿巴3 3阿巴阿巴AAA级1 1一个5 1一个乙Cd一个它回答：案例1：ABFECD案例2：ABCD案例3：A案例4：GDAHEBIFC案例5：-1案例6：BADC案例7：BA案例8：AB案例9：A案例10：-1所以一切看起来都很好。但谷歌总是声称“错误答案”。谁能找到对我的解决方案给出错误答案的测试？为什么Google声称答案错误？有人编写好的解决方案并获得0分，甚至没有办法知道原因，这真是令人讨厌。感谢帮助。最好的问候