网易开发笔试8.21第四题bfs
bfs,AC的,感觉类似腐烂的橘子
int[][] d = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; public int minSailCost(int[][] input) { // write code here int m = input.length, n = input[0].length; boolean[][] is = new boolean[m][n]; int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { Arrays.fill(dp[i], Integer.MAX_VALUE); } dp[0][0] = 0; is[0][0] = true; Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{0, 0}); while (!queue.isEmpty()) { int[] poll = queue.poll(); int i = poll[0], j = poll[1]; is[i][j] = true; for (int k = 0; k < 4; k++) { int x = i + d[k][0]; int y = j + d[k][1]; if (x >= 0 && x < m && y >= 0 && y < n && !is[x][y] && input[x][y] != 2) { if (input[x][y] == 0) { dp[x][y] = Math.min(dp[x][y], dp[i][j] + 2); } else { dp[x][y] = Math.min(dp[x][y], dp[i][j] + 1); } queue.offer(new int[]{x, y}); } } } return dp[m - 1][n - 1] == Integer.MAX_VALUE ? -1 : dp[m - 1][n - 1]; }