c++ - 连接的组件程序产生不正确的输出
问题描述
我正在开发一个程序,它接收一个 5x5 的字符数组并找到最长的相同字符列表,连接的意思是上、下、左或右相邻(意味着没有对角线)。然而,输出偏离 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()
函数时,它工作正常,当我将它传递给 row 3 并将 2 传递给 col 时,它会将 [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;
}
解决方案
问题是您正在递归使用,但在结束时search
也无条件地重置。cnt
这个问题可以在一个只有 3 个字符的简单“板”上演示:
a a a
假设我们从search
中间开始a
。它打电话look
并被告知要检查另外两个地方:a
左边和a
右边。search
然后调用自己,让我们说 left 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
是否正确使用需要牢记使用它的所有地方。如果 everysearchRecursive
返回它找到了多少看不见的位置,那么验证结果是否正确将是微不足道的。
推荐阅读
- ruby-on-rails - 返回 html 的响应正文中的 HTTP 错误
- wordpress - 将图像添加到 Mailchimp RSS 源
- javascript - getStaticProps Next JS 在生产环境中不起作用
- angular - Angular Jasmine:将主题附加到订阅与 subject.next
- python-3.x - TypeError: 'float' 对象在访问列表的浮动元素时不可下标
- c++ - 可能损坏的视觉工作室 2019 附加包含目录?
- amazon-elb - 我们可以使用经典负载均衡器 ARN 通过 CLI 注册实例吗
- vim - 在 Vim 中更改单词末尾的大小写
- javascript - 如何在VueJS中将表示{}内键值对中的值的数组显示为列表项?
- android - 如何在运行 AMD 处理器的 Windows 10 家庭版上安装 Android Studio?