0

I am beginner in coding and have basic knowledge of data structres and algorithms

I am writing a code to find the maximum connected area in matrix having atmost two different integers such that we can move from any cell to any other cell in this set by only moving between side-adjacent cells from the set. for example matrix like

1 1 2 3 1 3 1 2 5 2 5 2 1 5 6 1 3 1 2 1

answer will be 10 as

1 1 2 . . . 1 2 . . . 2 1 . . . . 1 2 1

will be the max connected area.I have written the code for this but i am getting segmentation fault in my code

 #include <bits/stdc++.h>
using namespace std;
long long int mat[2000][2000];
int dp[2000][2000];
long long int temp[2000][2000];
int findLongestFromACell(int i, int j,int n,int m)
{
    if (i<0 || i>=n || j<0 || j>=m)
        return 0;
    if (dp[i][j] != -1)
        return dp[i][j];
    if (j<m-1 && ((temp[i][j]) == temp[i][j+1]))
      return dp[i][j] = 1 + findLongestFromACell(i,j+1,n,m);

    if (j>0 && (temp[i][j]  == temp[i][j-1]))
      return dp[i][j] = 1 + findLongestFromACell(i,j-1,n,m);

    if (i>0 && (temp[i][j]  == temp[i-1][j]))
      return dp[i][j] = 1 + findLongestFromACell(i-1,j,n,m);

    if (i<n-1 && (temp[i][j]  == temp[i+1][j]))
      return dp[i][j] = 1 + findLongestFromACell(i+1,j,n,m);
    return dp[i][j] = 1;
}

int finLongestOverAll(int n,int m,long long int p,long long int q)
{
    for(int l=0;l<n;l++)
        for(int k=0;k<m;k++)
            {
                temp[l][k] = mat[l][k];
                dp[l][k] = -1;
                if (mat[l][k]==q)
                    temp[l][k] = p;
            }
    int result = 1;
    for (int i=0; i<n; i++)
    {
      for (int j=0; j<m; j++)
      {
          if (dp[i][j] == -1)
             findLongestFromACell(i, j,n,m);
          result = max(result, dp[i][j]);
      }
     }     
     return result;
}
int main() 
{
    int n,m;
    vector <int> a;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            cin>>mat[i][j];
            if (find(a.begin(),a.end(),mat[i][j]) == a.end())
                a.push_back(mat[i][j]);
        }
        int l =1;
    for(int i =0;i<a.size();i++)
        for(int j=i+1;j<a.size();j++)
        {
            int m = finLongestOverAll(n,m,a[i],a[j]);
            if (m>l)
                l=m;
        }
    cout<<l;
    return 0;
}

is this due to size overflow of 2d arrays or some thing else. I looked it over over again but i cant find the mistake

Thanks in advance

Mohit Singh
  • 1
  • 2
  • If you want to learn programming and C++ properly, I suggest you [get a few good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) to read, learn about computer architecture (to know for example what can cause a segmentation faults), and [learn how to debug your programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). And that you [should never include ``](http://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). – Some programmer dude Jun 09 '18 at 17:01
  • 1
    Your matrices are about 32MB each. The issue I foresee is that with big `n,m` you can overflow the stack used for recursive `finLongestXXX` calls. – Ripi2 Jun 09 '18 at 17:06
  • it is giving `segmentation fault` for `n=3 m=3` also – Mohit Singh Jun 09 '18 at 17:10
  • What says your debugger? When the segfaut occurs? – Daniel Langr Jun 09 '18 at 17:11
  • Use a debugger. Or at least a lot of "cout" everywhere to see where and when it fails. – Ripi2 Jun 09 '18 at 17:11
  • By the way, never do this: `#include `. Include C++ headers, such as `algorithm`, `iostream`, `vector`, etc. – Daniel Langr Jun 09 '18 at 17:15
  • 1
    I've tried to debug your program in an online debugger and it seems that even for 2x2 matrix the recursion goes forever. – Daniel Langr Jun 09 '18 at 17:22
  • @MohitSingh -- Why are you starting out with these huge matrices anyway? If the issue exists with a 2x2 or 3x3 matrix, then you should be fixing the problem there before trying out huge amounts of data. Second, if you used `std::vector` or `std::array` instead of those hard-coded arrays such as `dp`, you would more than likely get further ahead in figuring out what is wrong, since `std::array` and `std::vector` have a bounds-checking function called `at()`. Dumb arrays have no such facility built into them. Bottom line, first check if you are going out of bounds. – PaulMcKenzie Jun 09 '18 at 17:47
  • @MohitSingh Also when you're posting code, please do not post `cin` statements and input `for` loops, where it requires us to type in data. Just *hard-code* the sample data that is giving the issue directly into the program. This way, all we have to do is take your code, compile it, run it, and see the results, all without having to type in the data each and every time. You say it doesn't work with 3x3, then all you have to do is initialize `mat` in the `main` function with those 9 pieces of data. This not only helps us, it helps you also when debugging. – PaulMcKenzie Jun 09 '18 at 17:56

1 Answers1

1

There may be cases where your recursive function keeps recursing infinitely. For example, let's say temp (I,J) = temp (I,J+1). Your recursive function hops between these two states infinitely, leading to a segmentation fault due to stack overflow.

knandy
  • 11
  • 1