JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Segmentation fault in Div 1 medium | Reply
Has the stack run out during recursive calls?

I can use the iterative approach, but I think the following must run for the first example atleast!

#include <string>
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
 
int grid[400][600]={0};
class grafixMask
{	public:
	int mark;
	inline bool isK(int i, int j)
	{
		if( i<0 || i>399 || j<0 || j>599) return false;
		if(grid[i][j] !=0) return false;
		return true;
	}
	int dfs( int i,int j)
	{
		grid[i][j]=mark;
		int area=1;
		if ( isK(i+1,j) ) area+=dfs(i+1,j);
		if( isK(i-1,j) ) area+=dfs(i-1,j);
		if( isK(i,j+1) ) area+= dfs(i,j+1);
		if( isK(i, j-1)) area+=dfs(i,j-1);
		if( isK(i+1,j+1)) area+=dfs(i+1,j+1);
		if( isK(i+1,j-1)) area+=  dfs(i+1,j-1);
		if( isK(i-1,j-1)) area+=dfs( i+1,j-1);
		if( isK(i-1,j+1)) area+=dfs(i-1,j+1);
		return area;
			   	
	}
 
	vector<int> sortedAreas(vector<string> rect)
	{
		for( int i=0;i<rect.size();i++)
		{
			int l,t,b,r;
			stringstream ss(rect[i]);
			ss>>t>>l>>b>>r;
			for( int k=l;k<=r;k++)
				for( int j=t;j<=b;j++)
					grid[k][j]=-1;
		}		
		cerr<<"hi";
		int mark=1;
		vector<int> areas;
		for( int i=0;i<400;i++)
			for( int j=0;j<600;j++)
			{
				int area=0;
				if( isK(i,j))
				 area=dfs(i,j);
				cerr<<"hi3";
				if(area>0)
				{
				mark++;
				cerr<<mark;
				areas.push_back(area);	
					
				}
			}
		sort(areas.begin(),areas.end());
		
		return areas;
	}
};
Re: Segmentation fault in Div 1 medium (response to post by FalconsGaze) | Reply
The seventh if-then in the dfs function may be the culprit:
      if( isK(i-1,j-1)) area+=dfs( i+1,j-1);
To make writing similar pieces of code less error-prone, consider rewriting it as (warning: untested):
   int dfs( int i,int j)
   {
      grid[i][j]=mark;
      int area=1;
 
      static const int di[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
      static const int dj[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
      for ( int dir=0; dir<8; ++dir ) {
         if ( isK( i+di[dir], j+dj[dir] ) ) 
            area += dfs( i+di[dir], j+dj[dir] );
      }
      return area;
   }
But if I recall correctly, in this problem the stack will run out on large cases and you should use breadth-first search instead.
Re: Segmentation fault in Div 1 medium (response to post by lovro) | Reply
Well, I corrected the culprit.

But still I get segmentation fault for the first example even!

Perhaps the only way is to use iterative!
Re: Segmentation fault in Div 1 medium (response to post by FalconsGaze) | Reply
You have two mark variables - one in object, and another is local to method.
Also, dfs may use very big stack. In this case it's more than 4 MB.
Stack may be limited on some platforms, I'm not sure about TopCoder environment.
In case of big state space bfs is preferrable.
Re: Segmentation fault in Div 1 medium (response to post by venco) | Reply
Yes you rightly spotted that I have accidentally placed two mark variable

After removing the local definition of mark,the new code runs examples without segmentation but the answers are not correct.. :(

I am getting higher values of area than expected.
I am considering eight neighbours rather four!

Still missing something!
RSS