public class MovingCandies { int h, w; String[] input; boolean[][][][] vis; void dfs(int row, int col, int len, int ones) { if(!order(0, row, h - 1) || !order(0, col, w - 1)) return; ++len; if(input[row].charAt(col) == '#') ++ones; if(len > h * w || vis[row][col][len][ones]) return; vis[row][col][len][ones] = true; dfs(row + 1, col, len, ones); dfs(row, col + 1, len, ones); dfs(row - 1, col, len, ones); dfs(row, col - 1, len, ones); } public int minMoved(String[] t) { input = t; h = t.length; w = t[0].length(); vis = new boolean[h][w][h*w+1][h*w+1]; dfs(0, 0, 0, 0); int allowed = 0; // the total number of ones in the grid for(String row : t) for(int i = 0; i < row.length(); ++i) if(row.charAt(i) == '#') ++allowed; System.out.println(allowed); final int INF = 1000123; int ans = INF; for(int len = 0; len <= allowed; ++len) for(int ones = 0; ones <= h * w; ++ones) if(vis[h-1][w-1][len][ones]) ans = min(ans, len - ones); if(ans == INF) ans = -1; return ans; } }