Codeforces will be possibly unavailable in the period between Sep. 19, 19:00 (UTC) and Sep. 19, 21:00 (UTC) because of maintenance. ×

sahilarora.535's blog

By sahilarora.535, history, 5 years ago, In English

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}.

 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's very disheartening when people downvote without reasons!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should not be posting source code. Instead, post the link to your code!