当前位置：首页 > news >正文

华为OD机考-亲子游戏-BFS（JAVA 2025B卷 200分）

news 2025/7/18 11:42:05

在这里插入图片描述

package od;import java.util.*;/*** @version Ver 1.0* @date 2025/6/18* @description 亲子游戏*/
public class FamilyGames {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = Integer.parseInt(scanner.nextLine().trim());int[][] matrix = new int[N][N];int startX=0,startY=0,endX=0,endY=0;for (int i = 0; i < N; i++) {int[] array = Arrays.stream(scanner.nextLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();for (int j = 0; j < N; j++) {matrix[i][j] = array[j];if(matrix[i][j] == -3){startX = i;startY= j;}}}solve(matrix,startX,startY);}private static void solve(int[][] matrix, int startX,int startY){LinkedList<int[]> queue = new LinkedList<>();List<int[]> list = new ArrayList<>();int[][] directions = new int[][]{{0,1}, //右{1,0},//下{0,-1},//左{-1,0}};//上// 将起点加入队列queue.add(new int[]{startX,startY,0,0});while(!queue.isEmpty()){int[] ints = queue.poll();if(matrix[ints[0]][ints[1]]==-2){list.add(new int[]{ints[2],ints[3]});continue;}for(int i =0;i<4;i++){int x = ints[0]+directions[i][0];int y = ints[1]+directions[i][1];if(x>=0 && x<matrix.length && y>=0 && y<matrix[0].length){if(matrix[x][y]==-2){// 到达终点，价值不变，步数加1queue.add(new int[]{x,y,ints[2],ints[3]+1});}else if(matrix[x][y]>=0){//未到终点，价值加上当前值，步数加1，并将当前位置置为-1，避免重复访问//TODO 可以再剪枝优化下，引入二维数组存储步数，价值，步数更小，价值更高时add to queuequeue.add(new int[]{x,y,ints[2]+matrix[x][y],ints[3]+1});matrix[x][y]=-1;}}}}// 输出结果if(list.isEmpty()){System.out.println("-1");return;}list.sort((o1,o2)->{if(o1[1]==o2[1]){return o2[0]-o1[0];//价值降序}return o1[1]-o2[1];//步数升序});System.out.println(list.get(0)[0]);}
}