Unable to find bug in DFS problem — TopCoder SRM 211 Div1 500 GrafixMask.

Revision en1, by sahilarora.535, 2016-11-11 17:04:46

I recently came across this DFS problem: Topcoder SRM211 Div1 500, however, my code runs for the first test case but does not run for any other. I am unable to figure out the problem. Help appreciated.

//Sahil Arora
#include<bits/stdc++.h>
using namespace std;
#define ll              long long
#define ii              pair<int,int>
#define ff              first
#define ss              second
#define all(a)          a.begin(), a.end()
#define pb              push_back 
#define vi              vector<int>
#define vvi             vector< vi >
#define ford(i,x,a)     for(int i = x; i <= a; ++i)
#define sz(C)           int((C).size()) 

vvi mat(400, vi(600, 1));
vvi used(400, vi(600, 0));

int dfs(int x, int y){
	if(used[x][y] || !mat[x][y]) return 0;
	stack<ii> st;
	st.push({x,y});
	int result = 0;
	while(!st.empty()){
		ii cur = st.top();
		st.pop();
		if(cur.ff < 0 || cur.ff >=400 || cur.ss < 0 || cur.ss >= 600) continue;
		if(used[cur.ff][cur.ss] || !mat[cur.ff][cur.ss]) continue;
		used[cur.ff][cur.ss] = 1;
		++result;
		st.push({cur.ff, cur.ss+1});
		st.push({cur.ff, cur.ss-1});
		st.push({cur.ff+1, cur.ss});
		st.push({cur.ff-1, cur.ss});
	}
	return result;
}

class grafixMask {
public:
	vector <int> sortedAreas(vector <string> rect) {
		ford(i,0,399) ford(j,0,599){mat[i][j] = 1, used[i][j] = 0;}; 
		vi v;
		for(auto s: rect){
			istringstream is(s);
			int x1, y1, x2, y2;
			is>>x1>>y1>>x2>>y2;
			cout<<x1<<" - "<<y1<<" - "<<x2<<" - "<<y2<<"\n";
			ford(i,x1,x2) {ford(j,y1,y2) mat[i][j] = 0, used[i][j] = 1;}
			ford(i,0,399){
				ford(j,0,599){
					int x = dfs(i,j);
					if(x) v.pb(x);
				}
			} 
		}
		sort(all(v));
		return v;
	}
};

For the input vector: {"48 192 351 207", "48 392 351 407", "120 52 135 547", "260 52 275 547"}, I get a resulting vector: {235136}, whereas expected vector: {22816,192608}.

Tags #dfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English sahilarora.535 2016-11-11 17:04:46 2075 Initial revision (published)