Почему мое решение (Square Dance - проблема с google jam) дает "неправильный ответ"?

Question

Я сделал несколько задач с архивом из конкурса Google Jam 2020. Сначала я сделал 5 задач из квалификационного раунда, и все работает нормально. Только последняя проблема: мой алгоритм слишком медленный, поэтому я не получаю максимальных баллов. Но ладно. I go в Раунд 1A, и есть 3 проблемы. Задача 3 называется «Кадриль». Его описание можно найти здесь: https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b1355

Я сделал программу. Моя программа передала пример успешного выполнения. Я также протестировал свою программу в нескольких других ситуациях, и она работает нормально. Но когда я загружаю свое решение, я получил «Неверный ответ» в наборе тестовых примеров Google.

Например. Эти ситуации идеально подходят для моего решения:

1
5 5
1 1 1 1 1
1 1 1 1 1
1 1 2 1 1
1 1 1 1 1
1 1 1 1 1

Это дает ответ 66, потому что будет 3 раунда:

1 1 1 1 1
1 1 1 1 1
1 1 2 1 1
1 1 1 1 1
1 1 1 1 1
26

1 1 1 1 1
1 1 0 1 1
1 0 2 0 1
1 1 0 1 1
1 1 1 1 1
22 * ​​1034 *

1 1 0 1 1
1 1 0 1 1
0 0 2 0 0
1 1 0 1 1
1 1 0 1 1
18

Так что все работает нормально.

Но зачем не проходит тест Google.

Есть что-то, чего я не понимаю? Или ошибка в коде? Но он работает нормально во многих случаях, которые я тестирую ...

Мой исходный код:

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

using namespace std;

int sizeX;
int sizeY;
int** map;
bool** eliminateTable;


bool calculateWhoToEliminate()
{
    for (int y = 0; y < sizeY; ++y)
    {
        memset(eliminateTable[y], 0, sizeX);
    }

    bool toEliminate = false;

    for (int y = 0; y < sizeY; ++y)
    {
        for (int x = 0; x < sizeX; ++x)
        {
            if (map[y][x] == 0)
                continue;

            int skillOfNeightbours = 0;
            int neightboursCount = 0;

            //w lewo
            int px = x - 1;
            while (px >= 0)
            {
                if (map[y][px] != 0)
                {
                    skillOfNeightbours += map[y][px];
                    neightboursCount++;
                    break;
                }
                px--;
            }

            //w prawo
            px = x + 1;
            while (px < sizeX)
            {
                if (map[y][px] != 0)
                {
                    skillOfNeightbours += map[y][px];
                    neightboursCount++;
                    break;
                }
                px++;
            }

            //w gore
            int py = y - 1;
            while (py >= 0)
            {
                if (map[py][x] != 0)
                {
                    skillOfNeightbours += map[py][x];
                    neightboursCount++;
                    break;
                }
                py--;
            }

            //w dol
            py = y + 1;
            while (py < sizeY)
            {
                if (map[py][x] != 0)
                {
                    skillOfNeightbours += map[py][x];
                    neightboursCount++;
                    break;
                }
                py++;
            }

            if (map[y][x] * neightboursCount < skillOfNeightbours)
            {
                eliminateTable[y][x] = true;
                toEliminate = true;
            }
        }
    }

    return toEliminate;
}

void eliminate()
{
    for (int y = 0; y < sizeY; ++y)
    {
        for (int x = 0; x < sizeX; ++x)
        {
            if (eliminateTable[y][x])
            {
                map[y][x] = 0;
            }
        }
    }
}

int countScore()
{
    int score = 0;
    for (int y = 0; y < sizeY; ++y)
    {
        for (int x = 0; x < sizeX; ++x)
        {
            score += map[y][x];
        }
    }
    return score;
}

int solve()
{
    int score = 0;
    while (true)
    {
        score += countScore();
        if (calculateWhoToEliminate())
        {
            eliminate();
        }
        else
        {
            break;
        }       
    }
    return score;
}

int main()
{
    int testCasesCount;
    cin >> testCasesCount;
    for (int test = 1; test <= testCasesCount; ++test)
    {
        cin >> sizeX;
        cin >> sizeY;
        map = new int*[sizeY];
        eliminateTable = new bool*[sizeY];
        for (int y = 0; y < sizeY; ++y)
        {
            map[y] = new int[sizeX];
            eliminateTable[y] = new bool[sizeX];

            for (int x = 0; x < sizeX; ++x)
            {
                cin >> map[y][x];
            }
        }

        int r = solve();

        cout << "Case #" << test << ": " << r << endl;

        for (int y = 0; y < sizeY; ++y)
        {
            delete map[y];
            delete eliminateTable[y];
        }
        delete map;
        delete eliminateTable;
    }

    //system("pause");

    return 0;
}

Answer 1

ОК. Я нашел решение.

1. счет должен быть длинным long

2. not: cin >> sizeX; cin >> sizeY; но: cin >> sizeY; cin >> sizeX;

потому что сначала строки, затем столбцы.

Answer 2

Независимо от того, устраняет ли это проблему или нет, это определенно ошибка:

memset(eliminateTable[y], 0, sizeX);

Это должно быть:

memset(eliminateTable[y], 0, sizeX * sizeof(bool));

Третий аргумент функции memset - это количество байтов, а не количество элементов.

Возможно, тот вызов memset, который вы выполняли, только частично заполнял массив bool нулем, поэтому вы не получали правильных результатов из-за использования неинициализированных частей массива bool.