How to seach a 2d array for another smaller 2d array

Discussion in 'C++' started by Kevin, Mar 8, 2006.

  1. Kevin

    Kevin Guest

    Hey, I'm learning c++ and a program that I am suppose to make is
    suppost to read in two .txt files (map.txt, and template.txt). I am
    then suppost to put each character into a 2d array (one for each .txt
    file). Then try and find if the combination in the template 2d array
    is somewhere within the map 2d array. Then print out the what row and
    column that it was found at.

    I have gotten the two files into seperate 2d arrays:

    char ** map = new char*[numLines];

    for (int i = 0; i < numLines; i++)
    map = new char [length+1];

    in.clear();
    in.seekg(0);

    for (int i = 0; (i < numLines) && (!in.eof()); i++)
    {
    in.getline(buffer, 100);
    strcpy(map, buffer);
    }

    and

    char ** temp = new char*[numLines2];

    for (int i = 0; i < numLines2; i++)
    temp = new char [length2+1];

    inTemp.clear();
    inTemp.seekg(0);

    for (int i = 0; (i < numLines2) && (!inTemp.eof()); i++)
    {
    inTemp.getline(buffer, 100);
    strcpy(temp, buffer);
    }

    But now I am suppost to see if the temp array is inside the map array,
    and I'm abit lost. I got the program to work for the default files:

    map:
    j2DikxdiLLI3j
    aAxzZxxixxkw9
    okxjzxxxnchnq
    jmxmbkklmnsff

    temp:
    xx
    xx

    to output the correct information:"Located at row 1, column 5"

    //Searching for the temp in the map file

    bool found = 0;
    int loccol = 0;
    int locrow = 0;

    for (int i = 0; (i < numLines - 1) && !found; i++) // i runs through
    rows
    {
    for (int j = 0; (j < length - 1) && !found; j++) // j runs through
    cols
    {
    if(map[j] == temp[0][0] && map[i+1][j] == temp[1][0] &&
    map[j+1] == temp[0][1] && map[i+1][j+1] == temp[1][1])
    {
    found = 1;
    loccol = j; // j (columns) are the x coordinate
    locrow = i; // i (rows) are the y coordinate
    }
    }
    }

    if (found)
    cout << "Located at row " << locrow << ", column " << loccol << endl;
    else
    cout << "Not found" << endl;


    But now I need to get it to search if the arrays chage size, and I
    can't figure out how to do it.

    Any help would be appreciated.

    Thanks
     
    Kevin, Mar 8, 2006
    #1
    1. Advertising

  2. Kevin wrote:
    > [..]
    > for (int i = 0; (i < numLines - 1) && !found; i++) // i runs through
    > rows
    > {
    > for (int j = 0; (j < length - 1) && !found; j++) // j runs through
    > cols
    > {
    > if(map[j] == temp[0][0] && map[i+1][j] == temp[1][0] &&
    > map[j+1] == temp[0][1] && map[i+1][j+1] == temp[1][1])
    > {
    > found = 1;
    > loccol = j; // j (columns) are the x coordinate
    > locrow = i; // i (rows) are the y coordinate
    > }
    > }
    > }
    >
    > if (found)
    > cout << "Located at row " << locrow << ", column " << loccol << endl;
    > else
    > cout << "Not found" << endl;
    >
    >
    > But now I need to get it to search if the arrays chage size, and I
    > can't figure out how to do it.


    The 'if' statement inside the loop needs to be converted into two more
    nested loops -- going through the elements of the smaller "template".

    for (int i = ...
    for (int j = ...
    // optimization - only start looping if the top left corner
    // of the 'template' is not the same as the current
    if (map[j] == temp[0][0]) {
    for (int n = ... // all rows of the template
    for (int m = ... // all columns of the template
    if (not ... // not equal
    goto next_main_element;
    } // end-for(m)
    } // end-for(n)
    found = 1;
    } // end-if
    next_main_element:
    } // end-for (j)
    } // end-for (i)

    Also, there is no need to iterate through all elements of the main matrix,
    only through the top left part leaving the stripe as wide as the template
    width/height minus 1 on the right and on the bottom, because the template
    would not fit there for comparison.

    V
    --
    Please remove capital As from my address when replying by mail
     
    Victor Bazarov, Mar 8, 2006
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Lincoln
    Replies:
    3
    Views:
    453
    Chris Lincoln
    Jul 19, 2006
  2. jambiani
    Replies:
    4
    Views:
    392
    Andy Dingley
    Sep 4, 2006
  3. sherry
    Replies:
    0
    Views:
    423
    sherry
    Apr 15, 2009
  4. Hans Müller

    Seach for encrypted socket wrapper

    Hans Müller, Jun 2, 2009, in forum: Python
    Replies:
    3
    Views:
    347
    Lawrence D'Oliveiro
    Jun 3, 2009
  5. richie05 bal

    seach for pattern based on string

    richie05 bal, Aug 24, 2010, in forum: Python
    Replies:
    2
    Views:
    252
    richie05 bal
    Aug 26, 2010
Loading...

Share This Page