Recently I was solving the problem from kattis and typed DFS solution and got Memory Limit Exceeded, then I typed exactly the same thing in C++ and got AC. After not figuring out the fix, I went with BFS and it passed (in Java).
This is my DFS:
DFS Code
static boolean dfs(int i, int j, int climb) {
if (i == n - 1 && j == m - 1)
return true;
vis[i][j] = true;
boolean can = false;
for (int di = -1; di <= +1; di++) {
for (int dj = -1; dj <= +1; dj++) {
if (abs(di) == abs(dj))
continue;
int ii = i + di, jj = j + dj;
if (ii < 0 || ii >= n || jj < 0 || jj >= m || vis[ii][jj] || g[ii][jj] - g[i][j] > climb)
continue;
can |= dfs(ii, jj, climb);
}
}
return can;
}
This is my BFS code:
BFS code
boolean can = false;
Queue<IntegerPair> q = new LinkedList<>();
q.add(new IntegerPair(0, 0));
vis[0][0] = true;
while (!q.isEmpty()) {
int i = q.peek().first, j = q.poll().second;
if (i == n - 1 && j == m - 1) {
can = true;
break;
}
for (int di = -1; di <= +1; di++) {
for (int dj = -1; dj <= +1; dj++) {
if (abs(di) == abs(dj))
continue;
int ii = i + di, jj = j + dj;
if (ii < 0 || ii >= n || jj < 0 || jj >= m || vis[ii][jj] || g[ii][jj] - g[i][j] > mid)
continue;
vis[ii][jj] = true;
q.add(new IntegerPair(ii, jj));
}
}
}
Full Codes:
Full code - with DFS (MLE)
import java.io.*;
import java.util.*;
import java.util.function.*;
import static java.lang.Math.*;
public class Main {
static final Scanner in = new Scanner(System.in);
static final PrintWriter out = new PrintWriter(System.out);
static int[][] g;
static boolean[][] vis;
static int n, m;
public static void main(String[] args) throws IOException {
n = in.nextInt();
m = in.nextInt();
g = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
g[i][j] = in.nextInt();
}
}
int lo = -1, hi = (int) 1e9 + 5;
while (hi - lo > 1) {
int mid = lo + hi >> 1;
vis = new boolean[n][m];
if (dfs(0, 0, mid))
hi = mid;
else
lo = mid;
}
out.println(hi);
out.close();
}
static boolean dfs(int i, int j, int climb) {
if (i == n - 1 && j == m - 1)
return true;
vis[i][j] = true;
boolean can = false;
for (int di = -1; di <= +1; di++) {
for (int dj = -1; dj <= +1; dj++) {
if (abs(di) == abs(dj))
continue;
int ii = i + di, jj = j + dj;
if (ii < 0 || ii >= n || jj < 0 || jj >= m || vis[ii][jj] || g[ii][jj] - g[i][j] > climb)
continue;
can |= dfs(ii, jj, climb);
}
}
return can;
}
}
Full code - with BFS (AC)
import java.io.*;
import java.util.*;
import static java.lang.Math.*;
public class Main {
static final Scanner in = new Scanner(System.in);
static final PrintWriter out = new PrintWriter(System.out);
static int[][] g;
static boolean[][] vis;
static int n, m;
public static void main(String[] args) throws IOException {
n = in.nextInt();
m = in.nextInt();
g = new int[n][m];
vis = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
g[i][j] = in.nextInt();
}
}
int lo = -1, hi = (int) 1e9 + 5;
while (hi - lo > 1) {
int mid = lo + hi >> 1;
for (var i : vis)
Arrays.fill(i, false);
boolean can = false;
Queue<IntegerPair> q = new LinkedList<>();
q.add(new IntegerPair(0, 0));
vis[0][0] = true;
while (!q.isEmpty()) {
int i = q.peek().first, j = q.poll().second;
if (i == n - 1 && j == m - 1) {
can = true;
break;
}
for (int di = -1; di <= +1; di++) {
for (int dj = -1; dj <= +1; dj++) {
if (abs(di) == abs(dj))
continue;
int ii = i + di, jj = j + dj;
if (ii < 0 || ii >= n || jj < 0 || jj >= m || vis[ii][jj] || g[ii][jj] - g[i][j] > mid)
continue;
vis[ii][jj] = true;
q.add(new IntegerPair(ii, jj));
}
}
}
if (can)
hi = mid;
else
lo = mid;
}
out.println(hi);
out.close();
}
static class IntegerPair implements Comparable<IntegerPair> {
int first, second;
public IntegerPair(int first, int second) {
this.first = first;
this.second = second;
}
public IntegerPair(IntegerPair p) {
this(p.first, p.second);
}
IntegerPair swapped() {
return new IntegerPair(second, first);
}
@Override
public int compareTo(IntegerPair o) {
return first != o.first ? first - o.first : second - o.second;
}
@Override
public String toString() {
return String.format("[%d, %d]", first, second);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
IntegerPair that = (IntegerPair) o;
return first == that.first && second == that.second;
}
@Override
public int hashCode() {
return Objects.hash(first, second);
}
}
}
What can cause this kind of thing?
