# 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)