1

In this question, firstly, you have to write two functions:

new_array (char** a, int n, int m): create a two-dimension matrix of characters whose size is m*n.
del_array (char** a, int n, int m): delete a two-dimension matrix of characters whose size is m*n.

After that, you use two above functions to perform the following task: You are given a big image with size M*N and some small images with size m*n. Each image is presented by a matrix of characters with its size. Your task is finding the number of positions which each small image occurs in that big image.

Input file: image.inp.

The first line of the input file contains two positive integers M and N which are respectively the height and the width of the big image. Each line 2...M+1 consists of N characters (a...z, A...Z) which describe a row of the big image.

Subsequently, there are some small images which you must find the big image. Each small image is written in the formation of the big image. Specially, there is a line having m = 0 and n = 0, you have to end your finding process.

Output file: image.out.

For each small image in the input file, you must write a number which presents the number of positions which that small image occurs in the big image.

image.inp            image.out
4 4                   3 
Aaaa                  1 
Aaaa
Aaab
Aaaa
2 2
Aa
Aa
2 2
aa
ab
0 0

I did this:

  • file header: image.h:

    #ifndef _IMAGE_H_
#define _IMAGE_H_

using namespace std;
void    new_array (char** , int , int );
void    del_array (char** , int ,  );
bool    small_image(char**,char**,int,int,int,int)
int     count_small_image(char** , char** , int ,int ,int ,int );
#endif

  • file image.cpp:

    #include<iostream>
#include "image.h"
#include <fstream>
using namespace std;

void new_array(char** a, int n,int m)

    { ifstream inStream; inStream.open("image.inp");

       a=new char* [m] ;
   for(int i=0; i<m; i++)
   {
       a[i]=new char[n];

       for(int j=0;j<n; j++)
           inStream>>a[i][j];
   }
 }

void del_array(char** a,int m)
{

for(int i=0;i<m ;i++)
  {
    delete [] a[i];
  }
    delete [] a;
}

bool small_image(char** a,char** b, int i,int j,int p,int q)
{

        for(int u=i;u<i+p;u++ )
        {

            for(int v=j;v<j+q;v++ )
                {
                    if(a[u][v]!=b[u-i][v-j]) return false;

                }
        }

        return true;

}
int count_small_image(char** a,char** b,int m,int n,int p, int q)
{   

  int COUNT=0;
    for(int i=0;i<m;i++ )
       for(int j=0;j<n;j++ )
       {

          if(a[i][j]==b[0][0])
          {
            if((m-i+1)>=p && (n-j+1)>=q)
            {
              if(small_image(a,b,i,j,p,q)==false) break;
              else  COUNT++;
            }
       }
   } 


 return COUNT;
}

  • file main_count_small_image.cpp:

    #include <iostream>
#include "image.h"
#include <fstream>
using namespace std;

int main()
{
     ifstream inStream;
     inStream.open("image.inp");
     ofstream outStream;
     outStream.open("image.out");

     int m,n,p,q;
     char** a;
     char** b;

     inStream>>n>>m;

     new_array(a,n,m);
     inStream>>q>>p;

     new_array(b,q,p);

     int c;
     c=count_small_image(a,b,m,n,p,q);

     outStream<<c;

     del_array(a,m);
     del_array(b,p);

     return 0;
     getchar(); 
}

But, I get:

[error]: has stopped working ...

halfer
  • 19,824
  • 17
  • 99
  • 186
Jack
  • 51
  • 3
  • 2
    I think no one can blame you for your code ... the question itself forces one to write ugly code. Who is giving you such a bad question? – Daniel Jour Aug 16 '15 at 08:18
  • use a debugger. hint: changing a local variable will only have a local effect. – Karoly Horvath Aug 16 '15 at 08:31
  • Can you say more about this? Karoly Horvath – Jack Aug 16 '15 at 08:44
  • what do you mean? Daniel Jour – Jack Aug 16 '15 at 08:45
  • The `new_array` and `del_array` functions are completely useless, they aren't how one would write good C++ code. So I suspect that whoever gave you that question isn't qualified to teach good C++ programming, which is why I'd advise you to look for other resources. – Daniel Jour Aug 16 '15 at 08:55
  • thanks you daniel jour , but you can point out its useless? – Jack Aug 16 '15 at 08:58
  • One of several problem is that if you want to write a function to create a 2D array, then it must return the 2D array. So the code should look like this `char** new_array(int m, int n) { ...; return a; }`, not how you were told to write it. – john Aug 16 '15 at 09:16
  • Perhaps get to grips with the library - vectors perhaps – Ed Heal Aug 16 '15 at 09:41
  • Got to say I'm glad no one has jumped up and down screaming "Use std::vector!!!" Obviously the assignment wants arrays an pointers. That said, in the real world, use a vector. – user4581301 Aug 16 '15 at 09:42

2 Answers2

1

This is a simple bit of code best stepped through with a debugger. The OP will learn a lot more tracing the execution low than they will from being handed a canned answer.

Brute force works, but a previous question has an answer suggesting better approaches. See How to detect occurrencies of a small image in a larger image? .

The new array method is implemented incorrectly. Its inability to return the built array has been covered already so I'm skipping it. Nowhere in the specification does it say the new_array should read in the data from the file. Further, reopening the file will require the new stream to tart at the beginning and reread m and n before getting to the image data. This is not taken into account.

The lack of descriptive variable names makes this program difficult to read and is a disincentive to assisting the OP. Likewise the lack of rational indentation and braces use. The program by its appearance seems to ask the reader not to render assistance.

In count_small_image given the call

count_small_image(a,b,m,n,p,q);

The two for loops set up small_image for out-of-range array access. I believe that is that this is trying to prevent. 

if((m-i+1)>=p && (n-j+1)>=q)

Maybe it does, but it's a convoluted and clumsy way to do it. Remember: Code not written has no bugs. Instead, try something along the lines of

for(int m = 0; m < largeMaxM - smallMaxM; m++)
{
    for(int n = 0; n < largeMaxM - smallMaxN; n++)

Where smallMaxM and smallMaxN are the m and n bounds of the small image and largeMaxM and largeMaxN are the m and n bounds of the large image.

Small count is also overly complicated. Sorting it out so that it is based on iterating through the small image eliminates the cruft. descriptive variable names also makes the function much more readable.

bool small_image(char** a,char** b, int offsetM,int offsetN,int maxM,int maxN)
{
    for(int m = 0; m < maxM; m++)
    {
        for(int n = 0; n < maxN; n++)
        {
            if(a[m+offsetM][n+offsetN]!=b[m][n]) return false;
        }
    }
    return true;
}

I'm operating on tablet without a compiler, so forgive me if I'm off by one.

Community
  • 1
  • 1
user4581301
  • 33,082
  • 7
  • 33
  • 54
0

You've been told wrong (or you've misunderstood what you were told). Rewrite your code like this

char** new_array(int n, int m)
{
    char** a;
    ...
    return a;
}

int main()
{
     ...
     char** a = new_array(n, m);

etc.

You should read up how functions can return values (including pointers). And also read up on how pointers can be used to implement arrays.

john
  • 85,011
  • 4
  • 57
  • 81