HackerEarth A strange matrix problem solution

In this HackerEarth A strange matrix problem solution You are given a matrix A containing N rows and M columns and an integer C.

Initially, all cells are assigned some value less or equal to C. A[i][j] is the value of the ith row and jth column.

Each second all cell’s value is increased by 1 but it can increase maximum up to C after that value of A[i][j] is unchanged.

On the 0th second, you are at (1,1) cell and want to go to (N,M) cell.

At any point in time, you can jump to any adjacent cell. If you are at (i,j), then you can go to any of the adjacent cells, (i-1,j), (i+1,j), (i,j+1), and (i,j-1). You can move to the adjacent cells only on one condition :

You can move to any adjacent cell if and only if the value of the cell, where you are standing, is equal to the value of the adjacent cell and you can not go outside of the matrix

Your task is to determine the minimum time to reach (N,M) from the cell.

HackerEarth A strange matrix problem solution.

#include<bits/stdc++.h>

using namespace std;
using   ll = long long;
using   ld = long double;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define pb                  push_back
#define mp                  make_pair
#define F                   first
#define S                   second
#define pll                 pair<int , int>
#define int                 long long int
#define endl                "n"


#define ALL(v)              v.begin(),v.end()
#define ALLR(v)             v.rbegin(),v.rend()
#define pii                 3.14159265358979323
#define inf                     LLONG_MAX
#define ones(x)             __builtin_popcount(x)
#define fill(a,b)           memset(a,b,sizeof(a))
#define mod                         1000000007
#define hell            998244353

ll mod_pow(ll a,ll b,ll m)
{
    ll res = 1;
    while(b)
    {
        if(b&1)
        {
                res=(res*a) % m;
        }
        a=(a*a) % m;
        b>>=1;
    }
    return res;
}

ll mod_inverse(int a , int m)
{
        return mod_pow(a , m - 2 , m);
}

vector<vector<int>> b;

int n , m , h;

void dfs(int i , int j , vector<vector<int>> & vis , vector<vector<int>> & a) {
        vis[i][j] = 1;
        
        if(i - 1 >= 0 && a[i - 1][j] == a[i][j] && !vis[i - 1][j]) {
                dfs(i - 1, j , vis , a);
        }
        if(j - 1 >= 0 && a[i][j - 1] == a[i][j] && !vis[i][j - 1]) {
                dfs(i , j - 1 , vis , a);
        }
        if(j + 1 < m && a[i][j + 1] == a[i][j] && !vis[i][j + 1]) {
                dfs(i , j + 1 , vis , a);
        }
        if(i + 1 < n && a[i + 1][j] == a[i][j] && !vis[i + 1][j]) {
                dfs(i + 1, j , vis , a);
        }
}

void solve()
{
        cin >> n >> m >> h;
        
        int l = 0;
        int r = 1e9;
        int ans;
        
        b.resize(n);
        
        for(int i = 0; i < n; ++i) {
                b[i].resize(m);
                for(int j = 0; j < m; ++j) {
                        cin >> b[i][j];
                }
        }
        
        while(l <= r) {
                int mid = (l + r) / 2;
                
                vector<vector<int>> vis(n , vector<int>(m , 0));
                
                vector<vector<int>> a = b;
                
                for(int i = 0; i < n; ++i) {
                        for(int j = 0; j < m; ++j) {
                                a[i][j] = min(h , a[i][j] + mid);
                        }
                }
                
                dfs(0 , 0 , vis , a);
                
                if(vis[n - 1][m - 1] == 1) {
                        ans = mid;
                        r = mid - 1;
                }
                else {
                        l = mid + 1;
                }
        }
        
        cout << ans << endl;
}

signed main() {
        fast;
   
        int t = 1;
        
        //cin >> t;

        while(t--) {
                solve();
        }
        
        return 0;
}

Second solution

import sys

sys.setrecursionlimit(300000)
n, m, c = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
lo = -1
hi = c


def check(t):
    seen = [[False] * m for _ in range(n)]

    def dfs(x, y, val):
        if x < 0 or x >= n or y < 0 or y >= m or seen[x][y] or min(c, a[x][y] + t) != val:
            return False
        seen[x][y] = True
        if x == n - 1 and y == m - 1:
            return True
        return dfs(x - 1, y, val) or dfs(x + 1, y, val) or dfs(x, y - 1, val) or dfs(x, y + 1, val)

    return dfs(0, 0, min(c, a[0][0] + t))


while hi - lo > 1:
    mid = (lo + hi) // 2
    if check(mid):
        hi = mid
    else:
        lo = mid
print(hi)

coding problems solutions