回溯递归问题 [英] Backtracking Recursion Problem
问题描述
大家好！我正在尝试编写一个程序，它将在12x12中搜索名为blob的
事物。网格中的blob由星号组成。一个blob
包含至少一个星号。如果一个星号在一个blob中，那么与它相邻的星号
就在同一个blob中。如果一个blob有超过两个
星号，那么blob中的每个星号都与blob中至少一个
其他星号相邻。例如，这个12x12网格有6个blob。我有点时间试图弄清楚如何通过递归来解决这个问题。
我在网上看了一些例子，但我发现所有关闭的都是迷宫
问题。我使用的语言是C ++，编译器是Dev C ++
4.9.9.2。任何帮助都会非常感激，因为我似乎迷失在
这个整个递归的东西。
char grid [12] [12];
000000000000
0 * 0000000000
00000 * 000000
00 ** 0 * 00000 *
00000000000 *
00000000000 *
0000000 ** 00 *
0000000 ** 000
000000000000
000000000 ***
000000000 * 0 *
000000000 ***
这里是我的整个项目的源代码，如果你想看看
吧。
// main.cpp
#include< iostream>
#include" GridIO.h"
#include" Grid.h"
使用命名空间std;
int main（）
{
int cord [24];
int length;
GridIO obj;
obj.getFile（）;
obj.readAndStore （）;
Grid Gridobj（obj）;
Gridobj.display（）;
系统（暂停）;
返回0;
}
--------- ---------------------------
//GridIO.cpp
#include< iostream>
#include< cassert>
#include" GridIO.h"
using namespace std;
GridIO :: GridIO（）
{
for（int i = 0;我< = SIZE; i ++）
{
cords [i] = 0;
/// cout<< 我等于= << i<< endl;
// cout<< 绳索[] << i<< "] =" <<绳索[i]<< endl;
}
//默认值是数组的大小。
actualSize = SIZE;
} //结束GRIDIO构造函数
bool GridIO :: getFile（）
{
const int INPUTSIZE = 10;
bool retval = false;
char输入[INPUTSIZE];
cout<< 请输入您要打开的文件。 - " ;;
cin>输入;
cout<< 你输入了： <<输入<< endl;
infile.open（输入）;
断言（infile）; //确保文件能够打开。
retval = true; //因为断言将set retval传递给true。
返回retval;
}
void GridIO： ：readAndStore（）
{
//我们有线索所以从这里开始
int first = 0;
int second = 0;
int index = 0;
char dummy;
infile> first> dummy>第二个;
while（infile！=''\'''）
{
cords [index] = first;
index ++;
cords [index] = second;
index ++;
infile> first> dummy> second ;
}
infile.close（）;
//确保我们实际上能够阅读。
if（index 0）
actualSize = index;
index = 0;
while（index< SIZE）
{
cout<<绳索[索引]<< endl;
index ++;
}
}
void GridIO :: getCords（int cord []，int& LENGTH）
{
for（int i = 0; i< SIZE; i ++）
cord [i] = cords [i];
LENGTH = actualSize;
}
--- -------------------------------------------------- -
// GridIO.h
#ifndef GRIDIOH
#define GRIDIOH
#include< iostream>
#include< fstream>
使用命名空间std;
const int SIZE = 100;
class GridIO {
public：
//目的：构造类并设置默认值值。
//前提条件：无
//后置条件：cords []数组现在设置为全0;
// Retruns：NONE
GridIO（）;
//目的：打开用户请求的文件。
//前提条件：文件必须存在且必须按照
形成
//每行3个。
//后置条件：文件线现在存在于int cords []数组中。
//返回：True - 如果文件存在。
//错误 - 如果文件DNE。
bool getFile（）;
//目的：它是阅读文件并将电线存入
线[尺寸]。
//前提条件：必须有一个带有电线的文件。
//后置条件：文件已被读入数组并且已准备好
//要发送到网格类。
//返回：无
void readAndStore（）;
//目的：是从
$中检索线和数组的大小b $ b class
//并将它们交给客户。
//前提条件：需要有一个SIZE的绳子[]数组
big。
//后置条件：文件已被复制到客户端内存中。
//返回：无
void getCords（int cord []，int& LENGTH）;
私人：
fstream infile;
int cords [SIZE];
//将根据读入的
文件
//文件保存数组的实际大小。
int actualSize;
};
#endif
------------------ -------------------------------
// Grid.h
#ifndef GRIDH
#define GRIDH
#include" GridIO.h"
const int ROW = 12;
const int COL = 12;
class Grid {
public：
//目的：默认类构造函数。将网格设置为
all *'。
//前提条件：无
//后置条件：12x12网格现在包含所有开始。
//返回：无
网格（）;
//目的：重载网格构造函数。将网格设置为
//线索指定。
//前提条件：必须有一个填充了绳索的字符数组。
//数组的大小不能超过*******
//后置条件：网格已根据线索设置。 />
//返回：无
网格（GridIO& GridIOobj）;
//目的：显示网格。
//前提条件：无
//后置条件：网格已显示在屏幕上。
//返回：无
无效display（）;
//目的：将网格设置为默认设置0;
//前提条件：无
/ /后置条件：网格现在充满零。
//返回：无
void setGridtoZero（）;
private：
char grid [ROW] [COL];
};
#endif
----------------------------------------------- -------------------------
// Grid.cpp
#include< iostream>
#include" Grid.h"
using namespace std;
Grid :: Grid（）
{
setGridtoZero（）;
}
Grid :: Grid（GridIO& GridIOobj）
{
const int SIZE = 100;
int row，col = 0;
int rowstart，columstart = 0;
int cords [SIZE];
int Length = 0;
int x = 0;
//将网格初始化为零。
setGridtoZero（）;
GridIOobj.getCords（cords，Length ）;
cout<< 长度是 - <<长度<< endl;
cout<< 绳索 << *绳索<< endl;
//启动阅读。
行=绳索[x];
x ++;
col = cords [x];
x ++;
rowstart =（row - 1）;
columstart =（ col - 1）;
//启动读取结束。
while（x <=长度）
{
row = cords [x];
x ++;
col = cords [x];
x ++;
//计算
if（rowstart -1&& columstart -1）
{
cout<< rowstart - << rowstart<< endl;
cout<< colstart - " << columstart<< endl;
grid [rowstart] [columstart] =''*'';
rowstart =（row - 1）;
columstart = （col - 1）;
} //结束如果
其他
cout<< 错误 - 超出界限！ <<结束;
}
}
void Grid :: display（）
{
for（int i = 0; i< 12; i ++）
{
cout<< ENDL; //一行完成后的行尾。
for（int j = 0; j< 12; j ++）
{
cout<< grid [i] [j];
}
}
}
void Grid :: setGridtoZero（）
{
for（int i = 0; i< 12; i ++）
{
cout<< endl;
for（int j = 0; j< 12; j ++）
{
cout<< "网格[" << i<< "] [" << j<< "]：" ;;
grid [i] [j] =''0'';
}
}
cout<<结束;
}
--------------------------- -
无论如何，到目前为止，程序将读取用户告诉我们的.dat文件的坐标。
。这些坐标告诉Grid类blob
位于称为grid [12] [12]的12 x 12图形上。之后它会显示图表的样子。当然，我需要的程序的下一部分是递归解决方案，它将识别图中有多少blob
。正如我上面所说，任何帮助都将不胜感激。
2月15日上午8:57，NOO Recursion < f ... @ fake.comwrote：
大家好！我正在尝试编写一个程序，它将在12x12中搜索名为blob的
事物。网格中的blob由星号组成。一个blob
包含至少一个星号。如果一个星号在一个blob中，那么与它相邻的星号
就在同一个blob中。如果一个blob有超过两个
星号，那么blob中的每个星号都与blob中至少一个
其他星号相邻。例如，这个12x12网格有6个blob。我有点时间试图弄清楚如何通过递归来解决这个问题。
我在网上看了一些例子，但我发现所有关闭的都是迷宫
问题。我使用的语言是C ++，编译器是Dev C ++
4.9.9.2。任何帮助都会非常感激，因为我似乎迷失在
这个整个递归的东西。
char grid [12] [12];
000000000000
0 * 0000000000
00000 * 000000
00 ** 0 * 00000 *
00000000000 *
00000000000 *
0000000 ** 00 *
0000000 ** 000
000000000000
000000000 ***
000000000 * 0 *
000000000 ***
[snip]
---------------------------- -
无论如何，到目前为止，程序将读取用户告诉我们的.dat文件的坐标。
。这些坐标告诉Grid类blob
位于称为grid [12] [12]的12 x 12图形上。之后它会显示图表的样子。当然，我需要的程序的下一部分是递归解决方案，它将识别图中有多少blob
。正如我上面所说，任何帮助将不胜感激。
查找用于填充洪水的图形算法。他们将展示
如何计算你所追求的那些连续区域。
他们不是递归的好事。你应该使用一个单独的堆栈来存储中间结果而不是程序
堆栈，因为堆远远大于程序堆栈。
对于一个12x12的网格，它可能没什么关系，但这是一个坏习惯，让
进入。这里有一个详细描述的链接：
http://www.kirit.com/Recursive%20rights%20and%20wrongs
K
2月14日下午7:57，NOO Recursion < f ... @ fake.comwrote：
大家好！我正在尝试编写一个程序，它将在12x12中搜索名为blob的
事物。网格中的blob由星号组成。一个blob
包含至少一个星号。如果一个星号在一个blob中，那么与它相邻的星号
就在同一个blob中。如果一个blob有超过两个
星号，那么blob中的每个星号都与blob中至少一个
其他星号相邻。例如，这个12x12网格有6个blob。我有点时间试图弄清楚如何通过递归来解决这个问题。
我在网上看了一些例子，但我发现所有关闭的都是迷宫
问题。我使用的语言是C ++，编译器是Dev C ++
4.9.9.2。任何帮助都会非常感激，因为我似乎迷失在
这个整个递归的东西。
char grid [12] [12];
000000000000
0 * 0000000000
00000 * 000000
00 ** 0 * 00000 *
00000000000 *
00000000000 *
0000000 ** 00 *
0000000 ** 000
000000000000
000000000 ***
000000000 * 0 *
000000000 ***
这里是我的整个项目的源代码，如果你想看看
吧。
// main.cpp
#include< iostream>
#include" GridIO.h"
#include" Grid.h"
使用命名空间std;
int main（）
{
int cord [24];
int length;
GridIO obj;
obj.getFile（）;
obj.readAndStore （）;
Grid Gridobj（obj）;
Gridobj.display（ ）;
系统（PAUSE）;
返回0;
}
------------------------------------
//GridIO.cpp
#include< iostream>
#include< cassert>
#include" ; GridIO.h"
使用命名空间std;
GridIO :: GridIO（）
{
for（int i = 0;我< = SIZE; i ++）
{
cords [i] = 0;
/// cout<< 我等于= << i<< endl;
// cout<< 绳索[] << i<< "] =" <<绳索[i]<< endl;
}
//默认值是数组的大小。
actualSize = SIZE;
} // GRIDIO构造函数结束
bool GridIO :: getFile（）
{
const int INPUTSIZE = 10;
bool retval = false;
char输入[INPUTSIZE];
cout<< 请输入您要打开的文件。 - " ;;
cin>输入;
cout<< 你输入了： <<输入<< endl;
infile.open（输入）;
断言（infile）; //确保文件能够打开。
retval = true; //因为断言将set retval传递给true。
返回retval;
}
void GridIO :: readAndStore（）
{
//我们有线索所以从这里开始
int first = 0;
int second = 0;
int index = 0;
char dummy;
infile> first> ;假>秒;
while（infile！=''\'''）
{
cords [index] = first ;
index ++;
cords [index] = second;
index ++;
infile> first>虚拟>秒;
}
infile.close（）;
//确保我们实际上能够阅读一些东西。
if（索引0）
actualSize = index;
index = 0;
while（index< SIZE）
{
cout <<绳索[索引]<< endl;
index ++;
}
}
void GridIO :: getCords（int cord []，int& LENGTH）
{
for（int i = 0; i< SIZE; i ++）
cord [i] = cords [i];
LENGTH = actualSize;
}
------------------------------------------------- -----
// GridIO.h
#ifndef GRIDIOH
#define GRIDIOH
#include< iostream>
#include< fstream>
使用命名空间std;
const int SIZE = 100;
class GridIO {
public：
//目的：构建类和设置默认值。
//前提条件：无
//后置条件：cords []数组现在设置为全0;
/ / Retruns：NONE
GridIO（）;
//目的：打开用户请求的文件。
//前提条件：文件必须存在且必须按照
格式化为
//每行2,3。
//后置条件：文件线现在存在于int cords []数组中。
//返回：True - 如果文件存在。
//错误 - 如果文件DNE。
bool getFile（）;
//目的：这是读取文件并存储电源线
cords [SIZE]。
//前提条件：必须有一个带有电线的文件。
//后置条件：文件已被读入数组并且
准备好发送给网格类
//
//返回：无
void readAndStore（）;
//目的：是从
类中检索线和数组的大小
/ /并将它们交给客户。
//前提条件：需要有一个大小的绳索[]数组
大。
//后置条件：文件已被复制到客户端内存中。
//返回：无
void getCords（int cord []，int& LENGTH）;
私人：
fstream infile;
int cords [SIZE];
//将根据读入的
文件
//文件保存数组的实际大小。
int actualSize; };
#endif
---------------------- ---------------------------
// Grid.h
#ifndef GRIDH
#define GRIDH
#include" GridIO.h"
const int ROW = 12;
const int COL = 12;
class Grid {
public：
//目的：默认类构造函数。将网格设置为
all *'。
//前提条件：无
//后置条件：12x12网格现在包含所有开始。
//返回：无
网格（）;
//目的：重载网格构造函数。将网格设置为
//线索指定。
//前提条件：必须有一个填充了绳索的字符数组。
//数组的大小不能超过*******
//后置条件：网格已根据线索设置。 />
//返回：无
网格（GridIO& GridIOobj）;
//目的：显示网格。
//前提条件：无
//后置条件：网格已显示在屏幕上。
//返回：无
无效display（）;
//目的：将网格设置为默认设置0;
//前提条件：无
/ /后置条件：网格现在充满零。
//返回：无
void setGridtoZero（）;
private：
char grid [ROW] [COL];
};
#endif
------------------------------------------- ---------- -------------------
// Grid.cpp
#include < iostream>
#include" Grid.h"
using namespace std;
网格： ：网格（）
{
setGridtoZero（）;
}
格::网格（GridIO&安培; GridIOobj）
{
const int SIZE = 100;
int row，col = 0;
int rowstart，columstart = 0;
int cords [SIZE];
int Length = 0;
int x = 0;
//将网格初始化为零。
setGridtoZero（）;
GridIOobj.getCords（cords，Length ）;
cout<< 长度是 - <<长度<< endl;
cout<< 绳索 << *绳索<< endl;
//启动阅读。
行=绳索[x];
x ++;
col = cords [x];
x ++;
rowstart =（row - 1）;
columstart =（ col - 1）;
//启动读取结束。
while（x <=长度）
{
row = cords [x];
x ++;
col = cords [x];
x ++;
//计算
if（rowstart -1&& columstart -1）
{
cout<< rowstart - << rowstart<< endl;
cout<< colstart - " << columstart<< endl;
grid [rowstart] [columstart] =''*'';
rowstart =（row - 1）;
columstart = （col - 1）;
} //结束如果
其他
cout<< 错误 - 超出界限！ <<结束;
}
}
void Grid :: display（）
{
for（int i = 0; i< 12; i ++）
{
cout<< ENDL; //一行完成后的行尾。
for（int j = 0; j< 12; j ++）
{
cout<< grid [i] [j];
}
}
}
void Grid :: setGridtoZero（）
{
for（int i = 0; i< 12; i ++）
{
cout<< endl;
for（int j = 0; j< 12; j ++）
{
cout<< "网格[" << i<< "] [" << j<< "]：" ;;
grid [i] [j] =''0'';
}
}
cout<<结束;
}
--------------------------- -
无论如何，到目前为止，程序将读取用户告诉我们的.dat文件的坐标。
。这些坐标告诉Grid类blob
位于称为grid [12] [12]的12 x 12图形上。之后它会显示图表的样子。当然，我需要的程序的下一部分是递归解决方案，它将识别图中有多少blob
。正如我上面所说，任何帮助将不胜感激。
回溯不是你应该用来解决这个问题的算法。
它通常被用作蛮力搜索设置一个值为
满足某些标准的值。它用来解决像数独游戏这样的问题
和n-queens问题。
查看此链接了解更多信息。
http://en.wikipedia.org/wiki/Backtracking
如果你选择广泛的第一次搜索，你甚至不一定需要使用递归来解决这个
问题。但无论如何，
对某些可能有帮助的事情：
这是一个标准的图形连接问题。请参阅下面的参考资料
：
http://mathworld.wolfram.com/ConnectedGraph.html
http://en.wikipedia.org/wiki/Connectedness
http://www2.toki.or.id/book/AlgDesig...graphtraversal
每个星号都是图中的一个节点。当两个星号相邻时，
认为这是一个优势。考虑到这一点，当您读入数据时，
创建您的节点和边缘。然后通过首先使用
a广度或深度优先搜索来标记每一个。
http://en.wikipedia.org/wiki/Depth-first_search
http://en.wikipedia.org/wiki/Breadth-first_search
Pseudo代码：
http://www.kirupa.com /developer/acti...dth_search.htm
在您的搜索中，您将每个节点标记为已访问，并为每个组标记唯一的标签
。然后你弄清楚你使用了多少标签和
你有blob的数量。
HTH，
Paul Davis
NOO Recursion写道：
大家好！我正在尝试编写一个程序，它将在12x12中搜索名为blob的
事物。网格中的blob由星号组成。一个blob
包含至少一个星号。如果一个星号在一个blob中，那么与它相邻的星号
就在同一个blob中。如果一个blob有超过两个
星号，那么blob中的每个星号都与blob中至少一个
其他星号相邻。例如，这个12x12网格有6个blob。我有点时间试图弄清楚如何通过递归来解决这个问题。
我在网上看了一些例子，但我发现所有关闭的都是迷宫
问题。我使用的语言是C ++，编译器是Dev C ++
4.9.9.2。任何帮助都会非常感激，因为我似乎迷失在
这整个递归的东西。
一旦你挂起，递归很容易它的。这里有一些伪代码
find_blob（x，y，blob）
{
if（in_grid（x） ，y）&& grid [x] [y] ==''*''&&！in_blob（blob，x，y））
{
add_to_blob（blob，x，y）;
find_blob（x + 1，y，blob）;
find_blob（x - 1，y，blob）;
find_blob（x，y + 1，blob）;
find_blob（x，y - 1，blob）;
}
}
这就是它的全部内容。 x和y是你的坐标，blob是一些
种类的数据结构，你存储形成
blob的x和y坐标。 add_to_blob为blob添加一对坐标，in_blob
检查一对x和y坐标是否已经在blob中（所以你要
不要添加相同的坐标两次并进入一个无限循环）。
最后in_grid检查x和y是否在网格内部，所以你不会摔倒
网格。容易（但未经测试）。
正如你被告知这可能不是最有效的方法，但是我猜b
猜测练习的目的是学习递归。
尝试编写上面的伪代码并在遇到任何问题时回来。
john
Hi everyone! I am trying to write a program that will search a 12x12 for a
thing called a "blob". A blob in the grid is made up of asterisks. A blob
contains at least one asterisk. If an asterisk is in a blob, an asterisk
that is contiguous to it is in the same blob. If a blob has more than two
asterisks, then each asterisk in the blob is contiguous to at least one
other asterisk in the blob. For example this 12x12 grid has 6 blobs. I am
having a heck of a time trying to figure out how to do this with recursion.
I have looked online for examples but all I have found close is maze
problems. The language I am using is C++ and the compiler is Dev C++
4.9.9.2. Any help would be greatly appreciated for I seem to be lost on
this whole recursive thing.
char grid[12][12];
000000000000
0*0000000000
00000*000000
00**0*00000*
00000000000*
00000000000*
0000000**00*
0000000**000
000000000000
000000000***
000000000*0*
000000000***
here is my source code for my whole project if you would like to take a look
at it.
// main.cpp
#include <iostream>
#include "GridIO.h"
#include "Grid.h"
using namespace std;
int main()
{
int cord[24];
int length;
GridIO obj;
obj.getFile();
obj.readAndStore();
Grid Gridobj(obj);
Gridobj.display();
system("PAUSE");
return 0;
}
------------------------------------
//GridIO.cpp
#include <iostream>
#include <cassert>
#include "GridIO.h"
using namespace std;
GridIO::GridIO()
{
for (int i = 0; i <= SIZE; i++)
{
cords[i] = 0;
///cout << "I equals = " << i << endl;
//cout << "cords[ " << i << "] = " << cords[i] << endl;
}
// Default value is the size of the array.
actualSize = SIZE;
} // end of GRIDIO constructor
bool GridIO::getFile()
{
const int INPUTSIZE = 10;
bool retval = false;
char input[INPUTSIZE];
cout << "Please enter the file you would like to open. -- ";
cin >input;
cout << "You entered: " << input << endl;
infile.open(input);
assert(infile); // make sure file is able to open.
retval = true; // since the assert passed set retval to true.
return retval;
}
void GridIO::readAndStore()
{
// we have cords so start here
int first = 0;
int second = 0;
int index = 0;
char dummy;
infile >first >dummy >second;
while (infile != ''\0'')
{
cords[index] = first;
index++;
cords[index] = second;
index++;
infile >first >dummy >second;
}
infile.close();
// make sure we were actually able to read something in.
if (index 0 )
actualSize = index;
index = 0;
while (index < SIZE)
{
cout << cords[index] << endl;
index++;
}
}
void GridIO::getCords(int cord[], int& LENGTH)
{
for (int i = 0; i < SIZE; i++)
cord[i] = cords[i];
LENGTH = actualSize;
}
------------------------------------------------------
// GridIO.h
#ifndef GRIDIOH
#define GRIDIOH
#include <iostream>
#include <fstream>
using namespace std;
const int SIZE = 100;
class GridIO {
public:
// Purpose: To construct the class and set default values.
// Precondition: NONE
// Postcondition: cords[] array now set to all 0;
// Retruns: NONE
GridIO();
// Purpose: Open user requested file.
// Precondition: File must exist and must be formated according
to
// 2, 3 per line.
// Postcondition: File cords now exist in int cords[] array.
// Returns: True - if file exist.
// False - if file DNE.
bool getFile();
// Purpose: It is to read the file and store the cord in
cords[SIZE].
// Precondition: Must have a file with cords in it.
// Postcondition: File have been read into the array and is
ready to
// to be sent to the grid class.
// Returns: NONE
void readAndStore();
// Purpose: Is to retreive cords and the size of the array from
class
// and give them to the client.
// Precondition: Needs to have a cords[] array that is SIZE
big.
// Postcondition: Files have been copied into client memory.
// Returns: NONE
void getCords(int cord[], int& LENGTH);
private:
fstream infile;
int cords[SIZE];
// Will hold the actual size need for the array based on the
text
// file it has read in.
int actualSize;
};
#endif
-------------------------------------------------
// Grid.h
#ifndef GRIDH
#define GRIDH
#include "GridIO.h"
const int ROW = 12;
const int COL = 12;
class Grid {
public:
// Purpose: Default class constructor. Will set the grid to
all *''s.
// Precondition: NONE
// Postcondition: 12x12 grid now contains all starts.
// Returns: NONE
Grid();
// Purpose: Overloaded Grid constructor. Set the Grid to what
the
// Cords specify.
// Precondition: Must have a char array filled with cords. The
// Size of the array can''t exceede *******
// Postcondition: Grid has been set according to the cords.
// Returns: NONE
Grid(GridIO& GridIOobj);
// Purpose: To Display grid.
// Precondition: NONE
// Postcondition: Grid has been displayed on screen.
// Returns: NONE
void display();
// Purpose: Set grid to default setting of 0;
// Precondition: NONE
// Postcondition: Grid now is full of zeros.
// Returns: NONE
void setGridtoZero();
private:
char grid[ROW][COL];
};
#endif
------------------------------------------------------------------------
// Grid.cpp
#include <iostream>
#include "Grid.h"
using namespace std;
Grid::Grid()
{
setGridtoZero();
}
Grid::Grid(GridIO& GridIOobj)
{
const int SIZE = 100;
int row, col = 0;
int rowstart, columstart = 0;
int cords[SIZE];
int Length = 0;
int x = 0;
// initilizes the grid to zero.
setGridtoZero();
GridIOobj.getCords(cords, Length);
cout << "Length is -- " << Length << endl;
cout << "cords " << *cords << endl;
// priming read.
row = cords[x];
x++;
col = cords[x];
x++;
rowstart = (row - 1);
columstart = (col - 1);
// end of priming read.
while (x <= Length)
{
row = cords[x];
x++;
col = cords[x];
x++;
// calculations
if (rowstart -1 && columstart -1)
{
cout << "rowstart -- " << rowstart << endl;
cout << "colstart -- " << columstart << endl;
grid[rowstart][columstart] = ''*'';
rowstart = (row - 1);
columstart = (col - 1);
} // end of if
else
cout << "ERROR - OUT OF BOUNDS!" << endl;
}
}
void Grid::display()
{
for (int i = 0; i<12; i++)
{
cout << endl; // end of line for once the row is done.
for (int j = 0; j<12; j++)
{
cout << grid[i][j];
}
}
}
void Grid::setGridtoZero()
{
for (int i = 0; i<12; i++)
{
cout << endl;
for (int j = 0; j<12; j++)
{
cout << "Grid[" << i << "][" << j << "]: ";
grid[i][j] = ''0'';
}
}
cout << endl;
}
-----------------------------
Anyway, so far the program will read in coordinates from a .dat file that
the user tells us. These coordinates tell the Grid class where the blobs
are located on the 12 x 12 graph called grid[12][12]. After that it will
display what the graph looks like. Of course the next part of the program I
need is the recursive solution that will Identify how many blobs there are
in the graph. As I said up above any help will be greatly appreciated.
On Feb 15, 8:57 am, "NOO Recursion" <f...@fake.comwrote:Hi everyone! I am trying to write a program that will search a 12x12 for a
thing called a "blob". A blob in the grid is made up of asterisks. A blob
contains at least one asterisk. If an asterisk is in a blob, an asterisk
that is contiguous to it is in the same blob. If a blob has more than two
asterisks, then each asterisk in the blob is contiguous to at least one
other asterisk in the blob. For example this 12x12 grid has 6 blobs. I am
having a heck of a time trying to figure out how to do this with recursion.
I have looked online for examples but all I have found close is maze
problems. The language I am using is C++ and the compiler is Dev C++
4.9.9.2. Any help would be greatly appreciated for I seem to be lost on
this whole recursive thing.
char grid[12][12];
000000000000
0*0000000000
00000*000000
00**0*00000*
00000000000*
00000000000*
0000000**00*
0000000**000
000000000000
000000000***
000000000*0*
000000000***
[snip]
-----------------------------
Anyway, so far the program will read in coordinates from a .dat file that
the user tells us. These coordinates tell the Grid class where the blobs
are located on the 12 x 12 graph called grid[12][12]. After that it will
display what the graph looks like. Of course the next part of the program I
need is the recursive solution that will Identify how many blobs there are
in the graph. As I said up above any help will be greatly appreciated.Look up graphics algorithms for doing flood filling. They will show
how to work out contiguous areas of the sort you''re after.
They''re not good things to do recursively though. You should use a
separate stack to store intermediate results rather than the program
stack because the heap is so much larger than than the program stack.
For a 12x12 grid it probably won''t matter, but it''s a bad habit to get
into. Here''s a link describing this in detail:
http://www.kirit.com/Recursive%20rights%20and%20wrongs
K
On Feb 14, 7:57 pm, "NOO Recursion" <f...@fake.comwrote:Hi everyone! I am trying to write a program that will search a 12x12 for a
thing called a "blob". A blob in the grid is made up of asterisks. A blob
contains at least one asterisk. If an asterisk is in a blob, an asterisk
that is contiguous to it is in the same blob. If a blob has more than two
asterisks, then each asterisk in the blob is contiguous to at least one
other asterisk in the blob. For example this 12x12 grid has 6 blobs. I am
having a heck of a time trying to figure out how to do this with recursion.
I have looked online for examples but all I have found close is maze
problems. The language I am using is C++ and the compiler is Dev C++
4.9.9.2. Any help would be greatly appreciated for I seem to be lost on
this whole recursive thing.
char grid[12][12];
000000000000
0*0000000000
00000*000000
00**0*00000*
00000000000*
00000000000*
0000000**00*
0000000**000
000000000000
000000000***
000000000*0*
000000000***
here is my source code for my whole project if you would like to take a look
at it.
// main.cpp
#include <iostream>
#include "GridIO.h"
#include "Grid.h"
using namespace std;
int main()
{
int cord[24];
int length;
GridIO obj;
obj.getFile();
obj.readAndStore();
Grid Gridobj(obj);
Gridobj.display();
system("PAUSE");
return 0;
}
------------------------------------
//GridIO.cpp
#include <iostream>
#include <cassert>
#include "GridIO.h"
using namespace std;
GridIO::GridIO()
{
for (int i = 0; i <= SIZE; i++)
{
cords[i] = 0;
///cout << "I equals = " << i << endl;
//cout << "cords[ " << i << "] = " << cords[i] << endl;
}
// Default value is the size of the array.
actualSize = SIZE;
} // end of GRIDIO constructor
bool GridIO::getFile()
{
const int INPUTSIZE = 10;
bool retval = false;
char input[INPUTSIZE];
cout << "Please enter the file you would like to open. -- ";
cin >input;
cout << "You entered: " << input << endl;
infile.open(input);
assert(infile); // make sure file is able to open.
retval = true; // since the assert passed set retval to true.
return retval;
}
void GridIO::readAndStore()
{
// we have cords so start here
int first = 0;
int second = 0;
int index = 0;
char dummy;
infile >first >dummy >second;
while (infile != ''\0'')
{
cords[index] = first;
index++;
cords[index] = second;
index++;
infile >first >dummy >second;
}
infile.close();
// make sure we were actually able to read something in.
if (index 0 )
actualSize = index;
index = 0;
while (index < SIZE)
{
cout << cords[index] << endl;
index++;
}
}
void GridIO::getCords(int cord[], int& LENGTH)
{
for (int i = 0; i < SIZE; i++)
cord[i] = cords[i];
LENGTH = actualSize;
}
------------------------------------------------------
// GridIO.h
#ifndef GRIDIOH
#define GRIDIOH
#include <iostream>
#include <fstream>
using namespace std;
const int SIZE = 100;
class GridIO {
public:
// Purpose: To construct the class and set default values.
// Precondition: NONE
// Postcondition: cords[] array now set to all 0;
// Retruns: NONE
GridIO();
// Purpose: Open user requested file.
// Precondition: File must exist and must be formated according
to
// 2, 3 per line.
// Postcondition: File cords now exist in int cords[] array.
// Returns: True - if file exist.
// False - if file DNE.
bool getFile();
// Purpose: It is to read the file and store the cord in
cords[SIZE].
// Precondition: Must have a file with cords in it.
// Postcondition: File have been read into the array and is
ready to
// to be sent to the grid class.
// Returns: NONE
void readAndStore();
// Purpose: Is to retreive cords and the size of the array from
class
// and give them to the client.
// Precondition: Needs to have a cords[] array that is SIZE
big.
// Postcondition: Files have been copied into client memory.
// Returns: NONE
void getCords(int cord[], int& LENGTH);
private:
fstream infile;
int cords[SIZE];
// Will hold the actual size need for the array based on the
text
// file it has read in.
int actualSize;};
#endif
-------------------------------------------------
// Grid.h
#ifndef GRIDH
#define GRIDH
#include "GridIO.h"
const int ROW = 12;
const int COL = 12;
class Grid {
public:
// Purpose: Default class constructor. Will set the grid to
all *''s.
// Precondition: NONE
// Postcondition: 12x12 grid now contains all starts.
// Returns: NONE
Grid();
// Purpose: Overloaded Grid constructor. Set the Grid to what
the
// Cords specify.
// Precondition: Must have a char array filled with cords. The
// Size of the array can''t exceede *******
// Postcondition: Grid has been set according to the cords.
// Returns: NONE
Grid(GridIO& GridIOobj);
// Purpose: To Display grid.
// Precondition: NONE
// Postcondition: Grid has been displayed on screen.
// Returns: NONE
void display();
// Purpose: Set grid to default setting of 0;
// Precondition: NONE
// Postcondition: Grid now is full of zeros.
// Returns: NONE
void setGridtoZero();
private:
char grid[ROW][COL];
};
#endif
------------------------------------------------------------------------
// Grid.cpp
#include <iostream>
#include "Grid.h"
using namespace std;
Grid::Grid()
{
setGridtoZero();
}
Grid::Grid(GridIO& GridIOobj)
{
const int SIZE = 100;
int row, col = 0;
int rowstart, columstart = 0;
int cords[SIZE];
int Length = 0;
int x = 0;
// initilizes the grid to zero.
setGridtoZero();
GridIOobj.getCords(cords, Length);
cout << "Length is -- " << Length << endl;
cout << "cords " << *cords << endl;
// priming read.
row = cords[x];
x++;
col = cords[x];
x++;
rowstart = (row - 1);
columstart = (col - 1);
// end of priming read.
while (x <= Length)
{
row = cords[x];
x++;
col = cords[x];
x++;
// calculations
if (rowstart -1 && columstart -1)
{
cout << "rowstart -- " << rowstart << endl;
cout << "colstart -- " << columstart << endl;
grid[rowstart][columstart] = ''*'';
rowstart = (row - 1);
columstart = (col - 1);
} // end of if
else
cout << "ERROR - OUT OF BOUNDS!" << endl;
}
}
void Grid::display()
{
for (int i = 0; i<12; i++)
{
cout << endl; // end of line for once the row is done.
for (int j = 0; j<12; j++)
{
cout << grid[i][j];
}
}
}
void Grid::setGridtoZero()
{
for (int i = 0; i<12; i++)
{
cout << endl;
for (int j = 0; j<12; j++)
{
cout << "Grid[" << i << "][" << j << "]: ";
grid[i][j] = ''0'';
}
}
cout << endl;
}
-----------------------------
Anyway, so far the program will read in coordinates from a .dat file that
the user tells us. These coordinates tell the Grid class where the blobs
are located on the 12 x 12 graph called grid[12][12]. After that it will
display what the graph looks like. Of course the next part of the program I
need is the recursive solution that will Identify how many blobs there are
in the graph. As I said up above any help will be greatly appreciated.Backtracking isn''t the algorithm you should be using for this problem.
Its usually used as a brute-force search for a set a of values that
satisfy some criterion. Its used to solve things like sudoku puzzles
and the n-queens problem.
Check this link for more information.
http://en.wikipedia.org/wiki/Backtracking
And you don''t even necessarily need to use recursion to solve this
problem either if you go with the breadth first search. But anyway, on
to some things that might help:
This is a standard graph-connectivity problem. See the references
below:
http://mathworld.wolfram.com/ConnectedGraph.html
http://en.wikipedia.org/wiki/Connectedness
http://www2.toki.or.id/book/AlgDesig...graphtraversal
Each asterisk is a node in the graph. When two asterisks are adjacent,
consider that an edge. With that in mind, when you read in the data,
create your nodes and edges. Then go through and mark each one using
a breadth first or depth first search.
http://en.wikipedia.org/wiki/Depth-first_search
http://en.wikipedia.org/wiki/Breadth-first_search
Pseudo code at:
http://www.kirupa.com/developer/acti...dth_search.htm
Durring your search you mark each node as visited with a label unique
to each group. Then you figure out how many labels you used and
you''ve got the number of blobs.
HTH,
Paul Davis
NOO Recursion wrote:Hi everyone! I am trying to write a program that will search a 12x12 for a
thing called a "blob". A blob in the grid is made up of asterisks. A blob
contains at least one asterisk. If an asterisk is in a blob, an asterisk
that is contiguous to it is in the same blob. If a blob has more than two
asterisks, then each asterisk in the blob is contiguous to at least one
other asterisk in the blob. For example this 12x12 grid has 6 blobs. I am
having a heck of a time trying to figure out how to do this with recursion.
I have looked online for examples but all I have found close is maze
problems. The language I am using is C++ and the compiler is Dev C++
4.9.9.2. Any help would be greatly appreciated for I seem to be lost on
this whole recursive thing.
Recursion is easy once you get the hang of it. Here''s some psuedo-code
find_blob(x, y, blob)
{
if (in_grid(x, y) && grid[x][y] == ''*'' && !in_blob(blob, x, y))
{
add_to_blob(blob, x, y);
find_blob(x + 1, y, blob);
find_blob(x - 1, y, blob);
find_blob(x, y + 1, blob);
find_blob(x, y - 1, blob);
}
}
That''s all there is to it. x and y are your cordinates, blob is some
sort of data structure where you store the x and y coordinates that form
a blob. add_to_blob adds a pair of coordinate to the blob, in_blob
checks if a pair of x and y coordinates are already in a blob (so you
don''t add the same coordinates twice and get into an inifinite loop).
Finally in_grid checks if x and y are inside the grid, so you don''t fall
over the edge of the grid. Easy (but untested).
As you''ve been told this may not be the most efficient method, but I
guess the purpose of the exercise is to learn recursion.
Try coding up the pseudo-code above and come back if you have any problems.
john
这篇关于回溯递归问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
