JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Matches SRM 211 Segmentation fault in Div 1 medium
 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 #include #include #include 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 sortedAreas(vector rect) { for( int i=0;i>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 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<
 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 variableAfter 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!
 Forums Algorithm Matches SRM 211 Segmentation fault in Div 1 medium Previous Thread  |  Next Thread