Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth A strange matrix problem solution

YASH PAL, 31 July 2024
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

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

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes