➤ Problem Link : 598D. Igor In the Museum
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int lx[4]={-1,1,0,0};
int rx[4]={0,0,-1,1};
char arr[1001][1001];
int ans[1001][1001];
pair<int,int> parent[1001][1001];
int dfs(int i,int j,int px,int py,int n,int m)
{
// cout<<i<<" "<<j<<" "<<ans<<endl;
parent[i][j]=make_pair(px,py);
int x,y,ans=0;
for(int k=0;k<4;k++)
{
x = i + lx[k];
y = j + rx[k];
if(x >= 0 && y>=0 && x<n && y<m)
{
if(arr[x][y]=='*')
ans++;
else if (parent[x][y]==make_pair(-1,-1))
ans+=dfs(x,y,px,py,n,m);
}
}
// cout<<i<<" "<<j<<" "<<ans<<endl;
return ans;
}
int main()
{
int n,m,k,x,y;
cin>>n>>m>>k;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>arr[i][j];
parent[i][j]=make_pair(-1,-1);
}
}
while(k--)
{
cin>>x>>y;
x--,y--;
if(parent[x][y]!=make_pair(-1,-1))
{
cout<<ans[parent[x][y].first][parent[x][y].second]<<"\n";
continue;
}
ans[x][y] = dfs(x,y,x,y,n,m);
cout<<ans[x][y]<<"\n";
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.