Link to my submission
Link to the question
I used DFS on 2D grid to find the solution first marked all element with * visited then marked all element adjacent to * as #
Then stored each ‘.’ in vector and again retrieved it from the vector and performed the DFS on the vector first
And then just counted the no. Of non visited components
Any help would be appreciated
Is my approach totally wrong?
BTW the solution from the second links are not opening…
I m not able to view your solution.
Here is one repo - “GoogleCodeJam-2014/minesweeper_master.py at master · kamyu104/GoogleCodeJam-2014 · GitHub”
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli dx[8]={1,1,1,0,0,-1,-1,-1};
lli dy[8]={0,1,-1,-1,1,0,1,-1};
#define pb push_back
#define f first
#define s second
char a[1001][1001];
int vis[1001][1001];
int dfs(lli x,lli y,lli n)
{
vis[x][y]=1;lli k;
for(k=0;k<8;k++)
{
if(((y+dy[k]<n)&&(y+dy[k]>=0))&&((x+dx[k]<n)&&(x+dx[k]>=0)))
{
if((a[x+dx[k]][y+dy[k]]=='.')&&(vis[x+dx[k]][y+dy[k]]==0))
{
dfs(x+dx[k],y+dy[k],n);}
else if(a[x+dx[k]][y+dy[k]]=='#')
vis[x+dx[k]][y+dy[k]]=1;
}
}
return 0;
}
int main()
{
lli T;cin>>T;
for(int t=1;t<=T;t++)
{
lli n;
cin>>n;
lli i,j;
memset(vis,0,sizeof vis);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{cin>>a[i][j];
if(a[i][j]=='*')
vis[i][j]=1;}
}lli k;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]=='*')
{
for(k=0;k<8;k++)
{
if(((j+dy[k]<n)&&(j+dy[k]>=0))&&((i+dx[k]<n)&&(i+dx[k]>=0)))
{if(a[i+dx[k]][j+dy[k]]=='.')
a[i+dx[k]][j+dy[k]]='#';}
}
}
}
}
vector<pair<lli,lli> > vec;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]=='.')
vec.pb(make_pair(i,j));
}
}
lli cnt=0;
for(i=0;i<vec.size();i++)
{
int x=vec[i].f,y=vec[i].s;
if(vis[x][y]==0)
{dfs(x,y,n);
cnt++;}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{if(vis[i][j]==0)
cnt++;
}
}
cout<<"Case #"<<t<<":"<<" "<<cnt<<"\n";
}
return 0;
}```
THE CODEWould be happy to get a counter Test Case on my code
as of now I didn’t find any counter test case , I will tell u if I found .
Okkkk
you are just using too much memory (the judge’s result was “segmentation fault”)
I wouldn’t recommend using long long int if you don’t have to
@carre In one of the solutions I submitted I didn’t used long long int and also made the array of size 301*301 and it was giving wrong answer
That solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int dx[8]={1,1,1,0,0,-1,-1,-1};
int dy[8]={0,1,-1,-1,1,0,1,-1};
#define pb push_back
#define f first
#define s second
char a[301][301];
int vis[301][301];
int dfs(int x,int y,int n)
{
vis[x][y]=1;int k;
for(k=0;k<8;k++)
{
if(((y+dy[k]<n)&&(y+dy[k]>=0))&&((x+dx[k]<n)&&(x+dx[k]>=0)))
{
if((a[x+dx[k]][y+dy[k]]=='.')&&(vis[x+dx[k]][y+dy[k]]==0))
{
dfs(x+dx[k],y+dy[k],n);}
else if(a[x+dx[k]][y+dy[k]]=='#')
vis[x+dx[k]][y+dy[k]]=1;
}
}
return 0;
}
int main()
{
int T;cin>>T;
for(int t=1;t<=T;t++)
{
int n;
cin>>n;
int i,j;
memset(vis,0,sizeof vis);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{cin>>a[i][j];
if(a[i][j]=='*')
vis[i][j]=1;}
}int k;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]=='*')
{
for(k=0;k<8;k++)
{
if((j+dy[k]<n)&&(j+dy[k]>=0)&&(i+dx[k]<n)&&(i+dx[k]>=0))
{if(a[i+dx[k]][j+dy[k]]=='.')
a[i+dx[k]][j+dy[k]]='#';}
}
}
}
}
vector<pair<int,int> > vec;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]=='.')
vec.pb(make_pair(i,j));
}
}
int cnt=0;
for(i=0;i<vec.size();i++)
{
int x=vec[i].f,y=vec[i].s;
if(vis[x][y]==0)
{dfs(x,y,n);
cnt++;}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{if(vis[i][j]==0)
cnt++;
}
}
cout<<"Case #"<<t<<":"<<" "<<cnt<<"\n";
}
return 0;
}
Link of the Solution
just changed long long for int in your code and get AC
@carre It is giving wrong answer Brother.
Just to make you notice I have changed
typedef long long int lli;
to
typedef int lli;
Link
Solution
#include<bits/stdc++.h>
using namespace std;
typedef int lli;
lli dx[8]={1,1,1,0,0,-1,-1,-1};
lli dy[8]={0,1,-1,-1,1,0,1,-1};
#define pb push_back
#define f first
#define s second
char a[1001][1001];
int vis[1001][1001];
int dfs(lli x,lli y,lli n)
{
vis[x][y]=1;lli k;
for(k=0;k<8;k++)
{
if(((y+dy[k]<n)&&(y+dy[k]>=0))&&((x+dx[k]<n)&&(x+dx[k]>=0)))
{
if((a[x+dx[k]][y+dy[k]]=='.')&&(vis[x+dx[k]][y+dy[k]]==0))
{
dfs(x+dx[k],y+dy[k],n);}
else if(a[x+dx[k]][y+dy[k]]=='#')
vis[x+dx[k]][y+dy[k]]=1;
}
}
return 0;
}
int main()
{
lli T;cin>>T;
for(int t=1;t<=T;t++)
{
lli n;
cin>>n;
lli i,j;
memset(vis,0,sizeof vis);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{cin>>a[i][j];
if(a[i][j]=='*')
vis[i][j]=1;}
}lli k;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]=='*')
{
for(k=0;k<8;k++)
{
if(((j+dy[k]<n)&&(j+dy[k]>=0))&&((i+dx[k]<n)&&(i+dx[k]>=0)))
{if(a[i+dx[k]][j+dy[k]]=='.')
a[i+dx[k]][j+dy[k]]='#';}
}
}
}
}
vector<pair<lli,lli> > vec;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]=='.')
vec.pb(make_pair(i,j));
}
}
lli cnt=0;
for(i=0;i<vec.size();i++)
{
int x=vec[i].f,y=vec[i].s;
if(vis[x][y]==0)
{dfs(x,y,n);
cnt++;}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{if(vis[i][j]==0)
cnt++;
}
}
cout<<"Case #"<<t<<":"<<" "<<cnt<<"\n";
}
return 0;
}ok, now is when it gets weird because I did exactly that previously
Of course, we should suspect of some undefined behaviour but I can not find any problem in the solution, maybe in the judge? 
You submitted the same code and it got accepted?
Now I think Hackerrank is awesome , don’t know how beginners deal with it
Just to mention: I don’t use hackerrank , someone gave me question so I just tried to solve it .
Please answer the question in the first line…
@carre @ssrivastava990 Thanks for the help
yes
