华为OD亲子游戏

import java.util.*;

import static java.lang.Math.pow;


/*
Illustration:
Just think the simplest question,if the situation is this:
1 -3 1
1  1 1
-2 1 1
How we find the position of -2 from mommy's position the earliest,one way is that,we can regard the position of -3 as centre,
then access the four positions that adjoin it.Then regard one of the four position as centre ,and repeat the same thing till
find -2.
The next thing is, how to calculate the  candy?
What if we record the accumulating amount of accessing position in its own?
 If there are different ways,how we get calculate the maxCandy?Like this:
1  1 -3  2
1  1 -1  1
1  1  4  1
1 -1 -2 -1
When wo arrive number 4 position,how to calculate its candy,which should be max between the last position
candy plus the 4 position candy and the 4 position recording accumulating candy, but we can't get the recording
accumulating candy.Thus, we need a two dimensions  array record the present arriving accumulating maxCandy;

solution:
we just use breadth first search(notice the heirarchy) to find the earliest path and record the maxCandy;





* */
public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        int[][] space = new int[N][N];

        boolean[][] accessed = new boolean[N][N];

        for (int i = 0; i <= N - 1; i++) {//Initialize space and accessed array;

            for (int j = 0; j <= N - 1; j++) {

                space[i][j] = scanner.nextInt();

                accessed[i][j] = false;
            }
        }
        scanner.close();

        int[] mommy = new int[3];
        int[] baby = new int[3];
        boolean isBabyEmpty = true;
        boolean isMommyEmpty = true;

        for (int i = 0; i < N; i++) {//get mommy and baby position.
            for (int j = 0; j < N; j++) {
                if (space[i][j] == -3) {
                    mommy[0] = i;
                    mommy[1] = j;
                    isMommyEmpty = false;
                }
                if (space[i][j] == -2) {
                    baby[0] = i;
                    baby[1] = j;
                    isBabyEmpty = false;
                }
                if (isMommyEmpty == false && isBabyEmpty == false) {//get mommy and baby's position then stop
                    break;
                }

            }
        }

        Bfs bfs = new Bfs(space, mommy, baby);
        Deque<int[]> deque = bfs.getNodes();
        while (!deque.isEmpty()) {

            int [] the=deque.poll();
            bfs.findNext(the);

        }
        if (bfs.found==true){
            int candy=bfs.candy[bfs.target[0]][bfs.target[1]];
            System.out.println(candy);
        }else {
            System.out.println(-1);
        }


    }
}



class Bfs {
    private int[][] space;
    private boolean[][] accessed;
    public  int[][] candy;//record max amount of candy of removing to the position
    private int[] start;//start position
    public int[] target;//target position
    public boolean found = false;
    public int [] stopAt=new int [2];

    public int [][] level;//represents every accessing node level;


    private final Deque<int[]> nodes = new ArrayDeque<>();//who are valid

    public Deque<int[]> getNodes() {
        return nodes;
    }

    Bfs(int[][] space, int[] start, int[] target) {
        this.space = space;
        this.start = start;
        this.target = target;
        this.nodes.offer(start);

        this.accessed = new boolean[space.length][space.length];
        this.candy=new int[space.length][space.length];
        this.level=new int[space.length][space.length];
        for (int i=0;i< space.length;i++){
            for (int j = 0; j < space.length; j++) {
                level[i][j]=(int)pow(2,31)-1;
            }
        }
        this.level[start[0]][start[1]]=-1;

        for (int i = 0; i < accessed.length; i++) {
            for (int j = 0; j < accessed.length; j++) {
                accessed[i][j] = false;
            }
        }
    }





    public void findNext(int[] the) {


        int x=the[0];
        int y = the[1];


       int [][] offsets={{0,-1},{0,1},{1,0},{-1,0}};

        for (int[] offset : offsets) {

            int newX=the[0]+offset[0];

            int newY=the[1]+offset[1];

            if (newX==target[0]&&newY==target[1]) {
                this.found = true;
                //keep the maxCandy of every arriving  the target;
                this.candy[target[0]][target[1]]=Math.max(candy[the[0]][the[1]],candy[target[0]][target[1]]);
            }

            /*level[x][y]>level[newX][newY]:
            avoiding to add the having been added node to deque;
            * */
            if (newX<0||newX> space.length-1||newY<0||newY> space.length-1||space[newX][newY]<0||level[x][y]>level[newX][newY] ) continue;
            this.level[newX][newY]=this.level[x][y]+1;
            int maxCandy=Math.max(this.candy[x][y]+space[newX][newY],this.candy[newX][newY]);
            this.candy[newX][newY]=maxCandy;
            if (this.found==false) {//once find the target then stop;
                this.nodes.offer(new int[]{newX, newY});
            }

        }





    }
}