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