Программа подключенного компонента выдает неверный вывод

Question

Программа подключенного компонента выдает неверный вывод

Я работаю над программой, которая принимает массив символов 5×5 и находит самый длинный список одинаковых символов, связанных значениями, смежными вверх, вниз, влево или вправо (т.е. без диагоналей). Однако выход отключен на 1, давая 6 вместо правильных 7, с вводом:

a b c c b
a c b c c
c a a b a
b b a a c
a a a b a

Кто-нибудь может помочь мне найти ошибку в моем коде? (МОЙ КОД НИЖЕ)

ПОДРОБНОСТИ: отсутствующий символ находится в индексе [3] [3] (индекс начинается с 0). Когда я проверил мой look() функция, она работала правильно, когда я передал ее 3 для строки и 2 для столбца, и он добавил [3] [3] к конечному вектору, который должен быть возвращен, но я думаю, что что-то не получилось с рекурсией.

Я уже работал над отладкой, но безуспешно, вы можете увидеть отладочные отпечатки в моем коде.

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <utility>

using namespace std;
char grid[5][5];
bool seen[5][5];
int cnt = 1;
int maxn = 0;

vector<pair<int, int>> look(int row, int col)
{
//
vector<pair<int, int >> node_list;
if (row != 0)
if (grid[row - 1][col] == grid[row][col])
if (!seen[row - 1][col])
node_list.push_back(make_pair(row - 1, col));
if (row != 4)
if (grid[row + 1][col] == grid[row][col])
if (!seen[row+1][col])
node_list.push_back(make_pair(row + 1, col));
if (col != 0)
if (grid[row][col - 1] == grid[row][col])
if (!seen[row][col-1])
node_list.push_back(make_pair(row, col - 1));
if (col != 4)
if (grid[row][col + 1] == grid[row][col])
if (!seen[row][col+1])
node_list.push_back(make_pair(row, col + 1));
if (binary_search(node_list.begin(), node_list.end(), make_pair(2, 2)))
cout << "HAPPENED^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^" << "\n";
return node_list;
}

void search(int row, int col)
{
for (pair<int, int> a : look(row, col))
{
if (!seen[a.first][a.second])
{
seen[a.first][a.second] = true;
cnt++;
cout << "COUNTED and now SEARCHING " << a.first << " " << a.second << "\n";
cout << "search about to be called on " << a.first << " " << a.second << "\n";
search(a.first, a.second);
}
}
if (cnt > maxn)
maxn = cnt;
cout << "CNT: " << cnt << "\n";
cnt = 1;
return;
}

int main()
{
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
cin >> grid[i][j];
seen[i][j] = false;
}
}

for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
if (!seen[i][j])
{
cout << "INITIALLY SEARCHING: " << i << " " << j << "\n";
seen[i][j] = true;
cout << "search about to be called on " << i << " " << j << "\n";
search(i, j);
}
else
cout << "NO INITIAL SEARCH, SEEN: " << i << " " << j << "\n";
}
}
cout << maxn << "\n";
return 0;
}

1

c++c++11 connected-components graph recursion

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Проблема в том, что вы используете search рекурсивно, но и безусловно сбрасывать cnt в конце этого.

Эту проблему можно продемонстрировать на простой «доске», состоящей всего из 3 символов:

a a a

Предположим, что мы начинаем search с середины a, Это вызывает look и получает указание осмотреть два других места: a слева и a направо. search затем вызывает себя, скажем, с левой a, cnt является 2 в этой точке и слева и в середине a иметь их seen установлен в true, Этот второй рекурсивный search перезвонить просит look найти поблизости a, но на этот раз они все уже видели. Итак, второе search заканчивает, устанавливает maxn в 2 а также перезагружается cnt в 1. Теперь мы вернулись на первый уровень рекурсии и перейдем к a справа. Излишне говорить, что мы отбросили один раз, когда мы рассчитывали a налево.

Проблема здесь в том, что вы не четко отделили «рекурсивный поиск соседних полей» от «начать поиск с этой точки». Последние две строки вашего текущего search принадлежат второму, но не первому. Я бы предложил это:

void searchRecursive(int row, int col)
{
for (pair<int, int> a : look(row, col))
{
if (!seen[a.first][a.second])
{
seen[a.first][a.second] = true;
cnt++;
searchRecursive(a.first, a.second);
}
}
}

void startSearchFrom(int row, int col)
{
cnt = 1;
seen[i][j] = true;
searchRecursive(row, col);
if (cnt > maxn)
maxn = cnt;
cout << "CNT: " << cnt << "\n";
}

Это хорошо разделяет эти проблемы.

Дальнейшее улучшение было бы избавиться от всего мирового государства. Не сразу очевидно (хотя и верно), что ваш алгоритм работает правильно, несмотря на seen никогда не сбрасывается и проверяет, что cnt используется правильно, необходимо помнить все места, где он используется. Если каждый searchRecursive вместо того, чтобы вернуть, сколько невидимых местоположений он нашел, было бы тривиально проверить, что результат правильный.

1