![]() |
|
![]() |
|
|
Thread Tools | Display Modes |
|
|
#1 |
|
Newbie
Join Date: Mar 2006
Posts: 7
Rep Power: 0
![]() |
searching for 2D arrays within 2D arrays
Hi,
I'm working on a program to find a 2D array of characters (temp) in a larger 2D array of characters (map), and then output the coordinates of the upper left corner of the first occurrence. Temp and map are loaded from a file, and can be any size. For the purpose of this example, map is: j2DikxdiLLI3j aAxzZxxixxkw9 okxjzxxxnchnq jmxmbkklmnsff and temp is: xx xx So my expected coordinates should be row 1, col 5, but I am getting row 0, col 5 back. Here is my searching code: bool found = 0;
int row = 0, col = 0;
for (int i = 0; ((i < (maphgt-(temphgt-1))) && !found); i++)
{
for (int j = 0; ((j < (mapwid-(tempwid-1))) && !found); j++)
{
for (int m = 0; ((m < temphgt) && !found); m++)
{
for (int n = 0; n < tempwid; n++)
{
if (temp[m][n] != map[i+m][j+n])
break;
else if ((n == (tempwid - 1)) && (m == (temphgt - 1)))
{
found = 1;
row = i;
col = j;
}
}
}
}
}
if (found)
cout << "Found it at row " << row << ", col " << col << endl;
else
cout << "Not found." << endl;Anyone have any ideas? Thanks. |
|
|
|
|
|
#2 |
|
Resident Grouch
![]() ![]() ![]() ![]() ![]() ![]() Join Date: Jun 2005
Posts: 6,453
Rep Power: 10
![]() |
I'll look at your code (haven't yet). Meanwhile, here's a presentational tip: if you put your maps in code tags, as with your code, they'll use a fixed-width font and preserve their relationships.
2DikxdiLLI3j aAxzZxxixxkw9 okxjzxxxnchnq jmxmbkklmnsff vs. 2DikxdiLLI3j aAxzZxxixxkw9 okxjzxxxnchnq jmxmbkklmnsff
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers |
|
|
|
|
|
#3 |
|
Newbie
Join Date: Mar 2006
Posts: 7
Rep Power: 0
![]() |
Thank you for the tip. Upon further investigation, my map.txt file is actually
j2DikxdiLLI3j aAxzZxxixxkw9 okxjzxxxnchnq jmxmbkklmnsff which, in my code editor, are all 13 characters long. Must have made a typo earlier, I'm sorry. Thanks, Catherine |
|
|
|
|
|
#4 |
|
Programmer
Join Date: Jun 2005
Posts: 92
Rep Power: 4
![]() |
Where do you assign values to tempwid and temphgt and mapwid and maphgt? I think what is happening is that your tempwid and temphgt are set differently than your implemention of them in the search algorithm.
|
|
|
|
|
|
#5 |
|
Newbie
Join Date: Mar 2006
Posts: 7
Rep Power: 0
![]() |
This bit of code is an example for extracting info from map.txt. It is simply repeated with different variable names for template.txt.
char mapbuff[100];
ifstream instream;
instream.open("map.txt");
instream.getline(mapbuff, 100);
int mapwid = strlen(mapbuff);
int maphgt = 1; // create the variable height and set it to 1.. since we just took in 1 line
while(!instream.eof()) // while we haven't reached the end of the file yet..
{
instream.getline(mapbuff, 100);
maphgt++; // for every line we take in, increment height by 1
}
char ** map = new char*[maphgt]; // declares HEIGHT strings
for (int i = 0; i < maphgt; i++)
map[i] = new char [mapwid+1]; // initialize the ith row of the map to have width+1 characters
instream.clear();
instream.seekg(0); // seek to the beginning of the file
for (int i = 0; (i < maphgt) && (!instream.eof()); i++)
{
instream.getline(mapbuff, 100); // get a line and store it in buffer
strcpy(map[i], mapbuff);
}
instream.clear();
instream.close(); |
|
|
|
|
|
#6 | |
|
Resident Grouch
![]() ![]() ![]() ![]() ![]() ![]() Join Date: Jun 2005
Posts: 6,453
Rep Power: 10
![]() |
Here is some sample code. You will note that the approach is not the same as yours. When I use C++, I use C++, not C compiled with a C++ compiler. The result is code produced in a shorter period of time that is generally more robust. This code has been compiled and tested, but it hasn't been tested thoroughly. Your warranty expired yesterday.
#include <iostream> // Included for I/O stream operations
#include <fstream> // Included for file stream operations
#include <vector> // Included for easy 'arrays'
#include <string> // Included for C++ string usage.
// They're easier to deal with than char arrays
using namespace std; // To use the entire standard namespace,
// thus precluding the necessity of
// using the scope resolution operator.
// Can introduce name conflicts if due
// care is not taken.
typedef vector <string> charMap;
class Point
{
public:
int x;
int y;
Point () : x (0), y (0) {}
Point (int X, int Y) : x (X), y (Y){}
};
class cMap
{
public:
size_t width;
size_t height;
charMap map;
cMap (size_t w, size_t h)
{
width = w;
height = h;
for (size_t i = 0; i < height; i++)
{
string temp = "";
for (size_t j = 0; j < width; j++) temp += " ";
map.push_back (temp);
}
}
cMap (size_t w, size_t h, charMap& m)
{
width = w;
height = h;
for (size_t i = 0; i < m.size (); i++) map.push_back (m [i]);
}
void show ()
{
for (size_t i = 0; i < height; i++) cout << map [i] << endl;
cout << endl;
}
};
bool validateMap (charMap& m);
bool mapFind (cMap& main, cMap& sub, Point& loc);
bool mapMatch (cMap& m, cMap& s, size_t y, size_t x);
// Function to send error message to stderr stream
int uhOh (string trouble)
{
cerr << trouble << endl;
cin.get ();
return 1;
}
// Main
int main (int argc, char *argv [])
{
Point location;
// Generate a test map
charMap theMap;
theMap.push_back ("asdfghjkl");
theMap.push_back ("Now is th");
theMap.push_back ("The quick");
theMap.push_back ("quality o");
theMap.push_back ("Out, damn");
if (!validateMap (theMap)) return uhOh ("Map poorly defined");
cMap mainMap = cMap (theMap [0].size (), theMap.size (), theMap);
cout << "Main map:\n" << endl;
mainMap.show ();
// Generate a submap
theMap.clear ();
theMap.push_back ("qu");
theMap.push_back ("it");
if (!validateMap (theMap)) return uhOh ("submap poorly defined");
cMap subMap = cMap (theMap [0].size (), theMap.size (), theMap);
cout << "Sub map:\n" << endl;
subMap.show ();
if (mapFind (mainMap, subMap, location))
cout << "Top: " << location.y << ", Left: " << location.x << endl;
else cout << "Sub map not found within the target map" << endl;
cout << endl;
// Generate a different submap
theMap.clear ();
theMap.push_back ("Now");
theMap.push_back ("The");
theMap.push_back ("qua");
if (!validateMap (theMap)) return uhOh ("Second submap poorly defined");
subMap.height = theMap.size ();
subMap.width = theMap [0].size ();
subMap.map = theMap;
cout << "New submap:\n" << endl;
subMap.show ();
if (mapFind (mainMap, subMap, location))
cout << "Top: " << location.y << ", Left: " << location.x << endl;
else cout << "Sub map not found within the target map" << endl;
cout << endl;
cout << "Press ENTER to exit (don't you love to say that?)";
cin.sync ();
cin.get ();
return 0;
}
bool validateMap (charMap& m)
{
size_t testSize = m [0].size ();
for (size_t i = 1; i < m.size (); i++)
if (m [i].size () != testSize) return false;
return true;
}
bool mapFind (cMap& main, cMap& sub, Point& loc)
{
loc.x = 0;
loc.y = 0;
size_t maxX = main.map [0].size () - sub.map [0].size ();
size_t maxY = main.map.size () - sub.map.size ();
int pos;
// For all possible rows...
for (size_t i = 0; i <= maxY; i++)
{
// For all possible columns
for (size_t j = 0; j <= maxX; j++)
{
// If the submap string isn't on this main map row, try the next
if ((pos = main.map [i].find (sub.map [0], 0)) == string::npos) continue;
j = pos;
loc.x = pos;
loc.y = i;
if (mapMatch (main, sub, i, j)) return true;
}
}
return false;
}
bool mapMatch (cMap& m, cMap& s, size_t y, size_t x)
{
size_t xBase = x;
for (size_t i = 0; i < s.height; i++, y++, x = xBase)
for (size_t j = 0; j < s.map [0].size (); j++, x++)
if (m.map [y][x] != s.map [i][j]) return false;
return true;
}Quote:
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers |
|
|
|
|
|
|
#7 |
|
Newbie
Join Date: Mar 2006
Posts: 7
Rep Power: 0
![]() |
Thanks DaWei,
Although your methods are a little more advanced than my education at this point, I do appreciate your help. I'm going to keep playing with my code and see if I can get it to work. |
|
|
|
|
|
#8 |
|
Expert Programmer
Join Date: Jun 2005
Posts: 894
Rep Power: 4
![]() |
HammerCat: the problem is in these lines
if (temp[m][n] != map[i+m][j+n]) break; You could either use another bool variable such as "noMatch" to control the inner two loops, or you could just set m to temphgt in the above if test before the break, so that the m loop stops. |
|
|
|
|
|
#9 |
|
Newbie
Join Date: Mar 2006
Posts: 7
Rep Power: 0
![]() |
Thank you The Dark! That worked.. I actually did a combo.. first set m to temphgt, then break, so that it closes out of both inner loops. It works though. Thank you!
|
|
|
|
|
|
#10 |
|
Programming Guru
![]() Join Date: Jun 2005
Location: elemental plane
Posts: 1,429
Rep Power: 5
![]() |
That's a nice solution DaWei, I almost thought the CharMap was a map but it was a vector<string>.
__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates |
|
|
|
![]() |
| Bookmarks |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | |
| Display Modes | |
|
|