The link to the problem is
http://www.topcoder.com/stat?c=problem_statement&pm=10750&rd=14153
i applied kruskal to find the mst but my code fails for test case 2
*class* node{*public*:
*int* start,end,weight;};
*bool* *operator* <(*const* node & first, *const* node & second){
*return* first.weight<second.weight;}*class* ActivateGame{*public*:
vector<int>parent;
vector<int>rank;
*void* make_set(*int* i){
parent.push_back(i);
rank.push_back(0);}*int* findset(*int* x){
*if*(parent[x]!=x)
parent[x]=findset(parent[x]);
*return* parent[x];}*bool* merge(*int* x,*int* y){
x=findset(x);
y=findset(y);
*if*(x!=y)
{
*if*(rank[y]>rank[x])
parent[x]=y;
*else*
{
*if*(rank[x]==rank[y])
rank[x]++;
parent[y]=x;
}
*return* *true*;
}
*else*
*return* *false*;}
*int* findMaxScore(vector <string> grid){
rank.clear();parent.clear();
map<char,int>m;
*for*(*char* x='0';x<='9';x++)
{
m[x]=x-'0';
}
*for*(*char* x='a';x<='z';x++)
{
m[x]=x-'a'+10;
}
*for*(*char* x='A';x<='Z';x++)
{
m[x]=x-'A'+36;
}
vector<node> v;
*for*(*int* x=0;x<grid.size();x++)
{
*for*(*int* y=0;y<grid[x].size();y++)
make_set(x*grid[0].size()+y);
}
*for*(*int* x=0;x<grid.size();x++)
{
*for*(*int* y=0;y<grid[0].size();y++)
{
*for*(*int* z=y+1;z<grid[0].size();z++)
{
node n1;
n1.start=x*grid[0].size()+y;
n1.end=x*grid[0].size()+z;
n1.weight=abs(m[grid[x][y]]-m[grid[x][z]]);
v.push_back(n1);
}
}
}
*for*(*int* x=0;x<grid[0].size();x++)
{
*for*(*int* y=0;y<grid.size();y++)
{
*for*(*int* z=y+1;z<grid.size();z++)
{
node n1;
n1.start=y*grid[0].size()+x;
n1.end=z*grid[0].size()+x;
n1.weight=abs(m[grid[y][x]]-m[grid[z][x]]);
v.push_back(n1);
}
}
}
sort(v.rbegin(),v.rend());
*for*(*int* x=0;x<v.size();x++)
cout<<v[x].start<<" "<<v[x].end<<" "<<v[x].weight<<"\n";
*long* *long* *int* ans=0;
*for*(*int* x=0;x<v.size();x++)
{
*if*(findset(v[x].start)!=findset(v[x].end))
{
merge(v[x].start,v[x].end);
ans+=v[x].weight;cout<<v[x].start<<" "<<v[x].end<<"
"<<v[x].weight<<" "<<findset(v[x].start)<<"
"<<findset(v[x].end)<<"\n";
}
}
*return* ans;}
};
--
Anuj Kumar
Third Year Undergraduate,
Dept. of Computer Science and Engineering
NIT Durgapur
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
