Question

Atlassian | OA | INTERN | Coding Questions and Solutions | 2023 | Set-11

Answer 1

Images of ques 

 

Answer 2

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> arr(n, vector<int>(m));
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    for (auto &e : arr)
        for (auto &ee : e)
            cin >> ee;
    queue<pair<pair<int, int>, int>> q;
    vector<vector<bool>> vis(n, vector<bool>(m));
    vis[0][0] = true;
    dist[0][0] = 0;
    q.push({{0, 0}, 0});
    while (!q.empty())
    {
        auto p = q.front();
        q.pop();
        // {i, j + k}
        for (int i = 1; i <= k; i++)
        {
            int x = p.first.first, y = p.first.second + i;
            if (y >= m or arr[x][y] == 1)
                break;
            if (vis[x][y])
                continue;
            q.push({{x, y}, p.second + 1});
            vis[x][y] = true;
            dist[x][y] = p.second + 1;
        }
        // {i, j - k}
        for (int i = 1; i <= k; i++)
        {
            int x = p.first.first, y = p.first.second - i;
            if (y < 0 or arr[x][y] == 1)
                break;
            if (vis[x][y])
                continue;
            q.push({{x, y}, p.second + 1});
            vis[x][y] = true;            
            dist[x][y] = p.second + 1;
        }
        // {i + k, j}
        for (int i = 1; i <= k; i++)
        {
            int x = p.first.first + i, y = p.first.second;
            if (x >= n or arr[x][y] == 1)
                break;
            if (vis[x][y])
                continue;
            q.push({{x, y}, p.second + 1});
            vis[x][y] = true;   
            dist[x][y] = p.second + 1;
        }
        // {i - k, j}
        for (int i = 1; i <= k; i++)
        {
            int x = p.first.first - i, y = p.first.second;
            if (x < 0 or arr[x][y] == 1)
                break;
            if (vis[x][y])
                continue;
            q.push({{x, y}, p.second + 1});
            vis[x][y] = true;   
            dist[x][y] = p.second + 1;
        }
    }
    cout << (dist[n - 1][m - 1] == INT_MAX ? -1 : dist[n - 1][m - 1]) << endl;
}