print path from leftup to rightdown

M*N的地图上0表示可以走，1表示不能走，求从左上角到右下角的最短路径
很显然的BFS，也很快把基本的写出来了，然而我BFS每一步存了路径，大哥说这样内存消耗太大，怎么improve，然后在提示下想到每个node存一个路径上从哪来的信息，最后反过来打印。
然而悲剧就此来了，因为存的坐标信息是（x,y)，python的tuple是immutable的，存[x,y]的list初始化成M*N又有问题。然后想着建个class用coordinates表示x,y，然后一直有bug，到结束了都没有run出来，面完多看了眼就发现初始化coordinate的class应该初始化M*N个而不是直接复制（那样都是引用，导致最后改一个都改了）。因为这种问题跪了真是不甘心

import java.util.LinkedList;

public class Solution {

public String findPath(int[][] board) {
int m = board.length;
int n = board[0].length;
LinkedList<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] { 0, 0 });
boolean find = false;
while (!queue.isEmpty()) {
int count = queue.size();
while (count-- > 0) {
int[] point = queue.poll();
int x = point[0];
int y = point[1];
if (x == m - 1 && y == n - 1) {
find = true;
break;
}
if (x > 0 && board[x - 1][y] == 0) {
board[x - 1][y] = 2;// up
queue.add(new int[] { x - 1, y });
}
if (x < m - 1 && board[x + 1][y] == 0) {
board[x + 1][y] = 3;// down
queue.add(new int[] { x + 1, y });
}
if (y > 0 && board[x][y - 1] == 0) {
board[x][y - 1] = 4;// left
queue.add(new int[] { x, y - 1 });
}
if (y < n - 1 && board[x][y + 1] == 0) {
board[x][y + 1] = 5;
queue.add(new int[] { x, y + 1 });
}
}
if (find) break;
}
if (!find) return "No Path";
String res = "";
int x = m - 1;
int y = n - 1;
while (x != 0 || y != 0) {
int dir = board[x][y];
if (dir == 2) {
res = "up ->" + res;
x++;
} else if (dir == 3) {
res = "down ->" + res;
x--;
} else if (dir == 4) {
res = "left ->" + res;
y++;
} else if (dir == 5) {
res = "right ->" + res;
y--;
}
}
return res;
}

public static void main(String args[]) {
Solution s = new Solution();
int[][] board = {{0, 1, 1, 1, 0}, {0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}};
System.out.println(s.findPath(board));
}
}