Dynamic programming N*M grid problem approach solving using BFS/DFS

Viewed 31
#include <bits/stdc++.h>
using namespace std;


void anjum()
{
    int n,m;
    cin>>n>>m;
    int grid[n][m];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>grid[i][j];
        }
    }
    int x,y;
    cin>>x>>y;
    int count=0;
    int dx[]={1,1,-1,-1};
    int dy[]={1,-1,1,-1};
    queue<pair<int,int>>q;
    q.push({x,y});
    while(!q.empty())
    {
        pair<int,int>temp=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x1=temp.first+dx[i];
            int y1=temp.second+dy[i];
            if(x1>=0 && x1<n && y1>=0 && y1<m && grid[x1][y1]==0)
            {
                count++;
                grid[x1][y1]=1;
                q.push({x1,y1});
            }
        }
    }
    cout<<count<<endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        anjum();
    }
    return 0;
}

We have an NxM grid, the grid have one element named Bob. Bob can travel diagonally blocks only. The grid has some blocked blocks on which Bob can not travel. Write a function that returns on how many possible positions Bob can move. Solve this problem using BFS and submit the executable code in any programming language. In the following image example, Bob's positioning is at 9,3, and it can visit the places where Y is marked; hence your method should return 31.

**I'm not getting the output **

It just shows the test case passed but not getting the actual output.

0 Answers
Related