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?
In your bfs, you break when
boolean canbecomes true, you try to do the same thing with your dfs implementation, however, you usecan=can | dfs(ii, jj, climb)and|clause does not short-circuit meaning that it will examine all the conditions, instead of just breaking if one of the condition is true , which is exactly what happens here because your dfs function is called much more times than intended leading to MLE.I replace it with if — and still MLE.
Try replacing the final line from
can|=dfs(ii,jj,climb)tocan=can||dfs(ii,jj,climb)and let me know what happens.still MLE. (CF has limited me to 10 minutes for each comment or smth. lol).
It might just be because it is Java+RecursiveSpace, idk, lol. Best of luck!
even with java stack terribleness, there's no way you're using an entire gigabyte if your recursion is $$$NM \leq 10^6$$$ in depth. you probably have some stack overflow or something causing you to recurse infinitely.
Good question, I appreciate you explaining your problem and having put the effort into making a few different questions and trying to debug rather than just saying 'my code broken how to fix'. I think all of the logic of your code does what it should after some print statement debugging.
The next thing I did was generate a random 400*400 test case and run it in intellij. It crashed from a stackoverflow error at a depth of about 5k stack frames. This is pretty small, but from googling a bit maybe it's normal? (https://stackoverflow.com/questions/4734108/what-is-the-maximum-depth-of-the-java-call-stack)
Perhaps the stack memory size is much smaller than the heap size, and that's your problem. But I feel like I've gotten AC on some DFS programs that went quite deep; maybe someone with more experience can say something on this. I could just be wrong and it's always bad, or maybe it's something with tail recusion making it not problematic sometimes.
With a BFS, you won't have any problems, since your data is all stored on a heap.
So, it seems the moral of the story is to avoid arbitrarily deep recursive calls when the compiler won't be able to optimize them out with tail recursion (java apparently never does this). Though if someone else with more experience would validate my claim, I'd feel better about it, since I feel like I've had similar codes pass in the past.
This is probably a case of stack overflow. You can overcome this on most modern online judges by using the thread constructor which sets the stack size.
This is very interesting. But now instead of MLE, I got Time Limit Exceeded.