➤ Problem Link : 1063B. Labyrinth
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int l[]={-1,1,0,0};
int r[]={0,0,1,-1};
int main()
{
int n,m,si,sj,tj;
cin>>n>>m;
cin>>si>>sj;
si--;
sj--;
tj=sj;
ll x,y;
cin>>x>>y;
char arr[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>arr[i][j];
deque<pair<int,int> > Q;
ll dis[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
dis[i][j]=INT_MAX;
dis[si][sj]=0;
Q.push_back(make_pair(si,sj));
while(!Q.empty())
{
si=Q.front().first;
sj=Q.front().second;
Q.pop_front();
int val;
for(int i=0;i<4;i++)
{
if(i==0 || i==1 || i==3)
{
if(si+l[i]>=0 && si+l[i] < n && sj+r[i]>=0 && sj+r[i] < m && arr[si+l[i]][sj+r[i]]!='*')
{
if(dis[si+l[i]][sj+r[i]] > dis[si][sj])
{
dis[si+l[i]][sj+r[i]] = dis[si][sj];
Q.push_front(make_pair(si+l[i],sj+r[i]));
}
}
}
else
{
if(si+l[i]>=0 && si+l[i] < n && sj+r[i]>=0 && sj+r[i] < m && arr[si+l[i]][sj+r[i]]!='*')
{
if(dis[si+l[i]][sj+r[i]] > dis[si][sj]+1)
{
dis[si+l[i]][sj+r[i]] = dis[si][sj]+1;
Q.push_back(make_pair(si+l[i],sj+r[i]));
}
}
}
}
}
ll ans=0;
int lt,rt;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(arr[i][j]=='*')
continue;
rt=dis[i][j];
lt=rt-j+tj;
if(lt<=x && rt<=y)
{
ans++;
}
}
cout<<ans;
}
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.