BFS练习: POJ1426 POJ1724 POJ2251 POJ3126 POJ3278 POJ3414

POJ1426

package poj1426;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/10/2 8:56
 * @Description BFS，每一层节点是同位数，要搜索完一层节点再搜下一层。已AC
 * @Since version-1.0
 */
public class Main {
    /**
     * 输入的正整数
     */
    static int num;
    /**
     * 余数的最大个数
     */
    static int maxNum = 210;

    /**
     * 答案
     */
    static int[] answer;
    /**
     * 答案尾下标（答案长度）
     */
    static int ansIndex;
    /**
     * 余数存在过
     */
    static boolean[] exist;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true){
            num = sc.nextInt();
            if (num==0){
                break;
            }

            answer = new int[maxNum];
            exist = new boolean[maxNum];
            ansIndex = 0;
            bfs();

            for (int i = ansIndex-1; i >=0 ; i--) {
                if (i==0){
                    System.out.println(answer[i]);
                }else {
                    System.out.print(answer[i]);
                }
            }
        }
    }

    private static void bfs() {
        Node root = new Node(null,1,1);
        LinkedList<Node> list = new LinkedList<Node>();
        list.offer(root);
        while (!list.isEmpty()){
            Node parNode = list.poll();
            int remainder = parNode.remainder;
            /*下一个余数*/
            int next =0;
            for (int i = 0; i < 2; i++) {
                next = (remainder*(10%num)+i)%num;

                if (!exist[next]){
                    exist[next] = true;
                    Node child = new Node(parNode,next,i);
                    list.offer(child);
                    if (next==0){
                        Node temp = child;
                        while (temp!=null){

                            answer[ansIndex] = temp.type;
                            ansIndex++;
                            temp = temp.parent;

                        }
                        return;
                    }
                }
            }
        }
    }
    static class Node{
        /**
         * 父节点
         */
        Node parent;
        /**
         * 余数
         */
        int remainder;
        /**
         * 节点种类：根节点=-1，左节点=0，右节点=1
         */
        int type;

        public Node(Node parent, int remainder, int type) {
            this.parent = parent;
            this.remainder = remainder;
            this.type = type;
        }
    }
}
/*

2
6
19
0
*/

POJ1724

package poj1724;

import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/10/18 17:53
 * @Description
 * @Since version-1.0
 */
public class Main {
    /**
     * 钱数
     */
    static int k;
    /**
     * 城市数
     */
    static int n;
    /**
     * 道路数
     */
    static int r;
    /**
     * 道路邻接矩阵
     */
    static int[][][] roads;
    /**
     * 最短路径
     */
    static int shortestLen = -1;

    static class Node implements Comparable<Node> {
        int city;
        int spend;
        int length;
        boolean[] visit;

        public Node(int city, int spend, int length, boolean[] visit) {
            this.city = city;
            this.spend = spend;
            this.length = length;
            this.visit = visit;
        }

        @Override
        public int compareTo(Node o) {
            /*路径长度短的节点优先，如果一样就花钱少的优先*/
            if (this.length == o.length) {
                return this.spend - o.spend;
            } else {
                return this.length - o.length;
            }
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        k = sc.nextInt();
        n = sc.nextInt();
        r = sc.nextInt();
        roads = new int[n + 5][n + 5][5];
        for (int i = 0; i < r; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            int l = sc.nextInt();
            int t = sc.nextInt();
            if (roads[s][e][0] == 1) {

                /*筛选重负边中最短的*/
                if (l == roads[s][e][1]) {
                    if (t < roads[s][e][2]) {
                        roads[s][e][1] = l;
                        roads[s][e][2] = t;
                    }
                } else if (l < roads[s][e][1]) {
                    roads[s][e][1] = l;
                    roads[s][e][2] = t;
                }


                /*筛选重负边中最便宜的*/
                if (t == roads[s][e][4]) {
                    if (l < roads[s][e][3]) {
                        roads[s][e][3] = l;
                        roads[s][e][4] = t;
                    }
                } else if (t < roads[s][e][4]) {
                    roads[s][e][3] = l;
                    roads[s][e][4] = t;
                }

            } else {
                roads[s][e][1] = l;
                roads[s][e][2] = t;
                roads[s][e][3] = l;
                roads[s][e][4] = t;
                /*标记边存在*/
                roads[s][e][0] = 1;
            }


        }

        bfs();
        System.out.println(shortestLen);
    }

    private static void bfs() {
        PriorityQueue<Node> list = new PriorityQueue<Node>();
        Node top = new Node(1, 0, 0, new boolean[n + 5]);
        top.visit[1] = true;
        list.offer(top);
        while (!list.isEmpty()) {
            Node parent = list.poll();
            if (parent.city == n) {
                shortestLen = parent.length;
                return;
            }

            for (int i = 1; i <= n; i++) {
                /*下一站未走过并且该边存在*/
                if (!parent.visit[i] && roads[parent.city][i][0] != 0) {
                    /*重复边中最短的*/
                    int l1 = parent.length + roads[parent.city][i][1];
                    int t1 = parent.spend + roads[parent.city][i][2];
                    /*重复边中最便宜的*/
                    int l2 = parent.length + roads[parent.city][i][3];
                    int t2 = parent.spend + roads[parent.city][i][4];
                    boolean[] visit = parent.visit.clone();
                    visit[i] = true;
                    if (t1 <= k) {
                        Node child1 = new Node(i, t1, l1, visit);
                        list.offer(child1);
                    }

                    if (!(t1 == t2 && l1 == l2)) {
                        if (t2 <= k) {
                            Node child2 = new Node(i, t2, l2, visit);
                            list.offer(child2);
                        }

                    }
                }
            }
        }
    }
}
/*Notice that different roads may have the same source and destination cities.
* 请注意，不同的道路可能具有相同的源城市和目的城市。没看到这条被坑惨了*/
/*
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

11

19
6
7
1 2 2 2
1 3 2 2
1 4 2 2
2 5 5 10
4 5 7 7
3 5 10 5
5 6 5 10
14

15
12
16
1 8 20 0
1 2 10 0
2 8 5 0
1 7 100 0
2 3 5 1
3 4 5 1
4 5 5 1
5 6 5 1
6 12 5 1
8 12 10 20
8 9 1 1
9 10 1 1
10 11 1 1
11 7 2 10
7 12 10 1
11 4 1 0
30
*/

POJ2251

package poj2251;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/10/3 14:45
 * @Description 多选择求最少选择次数：BFS，一次AC的典范
 * @Since version-1.0
 */
public class Main {
    static int l;
    static int r;
    static int c;
    static char[][][] map;
    static int[][][] visit;
    static int[][] dir = {{0, 0, -1}, {0, 0, 1}, {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}};
    static int[] start;
    static int[] end;
    static LinkedList<Node> list;
    static Node optimal;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            l = sc.nextInt();
            r = sc.nextInt();
            c = sc.nextInt();
            if (l == 0 && r == 0 && c == 0) {
                break;
            }
            start = new int[6];
            end = new int[6];
            map = new char[l + 5][r + 5][c + 5];
            visit = new int[l + 5][r + 5][c + 5];
            sc.nextLine();
            for (int i = 0; i < l; i++) {
                for (int j = 0; j < r; j++) {
                    String str = sc.next();
                    for (int k = 0; k < c; k++) {
                        map[i][j][k] = str.charAt(k);
                        if (map[i][j][k] == 'S') {
                            start[0] = i;
                            start[1] = j;
                            start[2] = k;
                            visit[i][j][k] = 1;
                        }
                        if (map[i][j][k] == 'E') {
                            end[0] = i;
                            end[1] = j;
                            end[2] = k;
                        }
                    }
                }
            }
            list = new LinkedList<Node>();
            optimal = new Node();
            bfs();
            if (optimal.time==0){
                System.out.println("Trapped!");
            }else {
                System.out.println("Escaped in "+optimal.time+" minute(s).");
            }
        }

    }

    private static void bfs() {
        Node root = new Node(start[0], start[1], start[2], 0);
        list.offer(root);
        while (!list.isEmpty()) {
            Node parent = list.poll();
            /*当前的l，r，c，time*/
            int cl,cr,cc;
            int ct = parent.time + 1;
            for (int i = 0; i < 6; i++) {

                /*往i方向移动一格*/
                cl = parent.l + dir[i][0];
                cr = parent.r + dir[i][1];
                cc = parent.c + dir[i][2];
                /*判断有没有出界*/
                boolean b1 = cl>=0&&cl<l&&cr>=0&&cr<r&&cc>=0&&cc<c;
                if (b1){
                    /*判断该位置有没有走过*/
                    boolean b2 = visit[cl][cr][cc]==0;
                    /*判断该位置是不是石头*/
                    boolean b3 = map[cl][cr][cc]!='#';

                    if (b2&&b3){
                        visit[cl][cr][cc]=1;
                        /*判断当前耗时是否比最短耗时小，否则剪枝*/
                        if (optimal.time == 0 || ct < optimal.time) {
                            Node child = new Node(cl,cr,cc,ct);
                            /*到达终点就更新最优值节点*/
                            if (cl == end[0] && cr == end[1] && cc == end[2]) {
                                optimal = child;
                            }else {
                                /*否则入队*/
                                list.offer(child);
                            }
                        }
                    }
                }
            }
        }
    }

    static class Node {
        int l;
        int r;
        int c;
        int time = 0;

        public Node(int l, int r, int c, int time) {
            this.l = l;
            this.r = r;
            this.c = c;
            this.time = time;
        }

        public Node() {
        }
    }
}

/*
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

*/

POJ3126

package poj3126;

import java.util.LinkedList;
import java.util.Scanner;


/**
 * @Author jinjun99
 * @Date Created in 2022/10/2 14:46
 * @Description 每次改变一位数，有多种改法，求最少次数，选BFS，先把第i次的所有可能性遍历，再看i+1步
 * @Since version-1.0
 */
public class Main {
    static int n;
    static int a;
    static int b;
    static int maxInt = 10000;
    /**
     * 标记素数 false 表示是素数
     */
    static boolean[] nonPrimeNum = new boolean[maxInt+5];
    /**
     * 标记是否走过
     */
    static boolean[] visit;
    /**
     * 标记所有素数的步数
     */
    static int[] allSteps;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        earSieve();
        for (int i = 0; i < n; i++) {
            a = sc.nextInt();
            b = sc.nextInt();

            initData();
            bfs();
            if (allSteps[b]!=100000){
                System.out.println(allSteps[b]);
            }else {
                System.out.println("impossible");
            }

        }
    }

    private static void initData() {
        visit = new boolean[maxInt+5];
        allSteps = new int[maxInt+5];
        for (int i = 0; i < maxInt+5; i++) {
            allSteps[i] = 100000;
        }
        allSteps[a] = 0;
        visit[a] = true;
    }
    /**
     * 埃氏法求素数
     */
    private static void earSieve() {

        for (int i = 2; i < maxInt+5; i++) {
            if (!nonPrimeNum[i]){
                for (int j = i*2; j < maxInt+5; j+=i) {
                    nonPrimeNum[j] = true;
                }
            }
        }
    }

    private static void bfs() {
        if (a==b) {
            return;
        }
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.offer(a);

        while (!list.isEmpty()){
            int parent = list.poll();
            int[] num = {parent/1000%10, parent/100%10,
                    parent/10%10, parent%10};
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 10; j++) {
                    if (j==num[i]||(i==3&&j==0)){
                        continue;
                    }
                    int newNum = getNewNum(num,i,j);

                    if (!nonPrimeNum[newNum]&&!visit[newNum]&&allSteps[newNum]>allSteps[parent]+1){
//                        System.out.println(newNum);
                        allSteps[newNum] = allSteps[parent]+1;
                        list.offer(newNum);
                        visit[newNum] = true;

                    }
                }
            }
        }
    }

    private static int getNewNum(int[] num,int digit,int bit) {
        if (digit==0){
            return num[0]*1000+num[1]*100+num[2]*10+bit;
        }
        if (digit==1){
            return num[0]*1000+num[1]*100+bit*10+num[3];
        }
        if (digit==2){
            return num[0]*1000+bit*100+num[2]*10+num[3];
        }
        if (digit==3){
            return bit*1000+num[1]*100+num[2]*10+num[3];
        }
        return 0;
    }

}


/*
4
1033 8179
1373 8017
1033 1033
1029 1014

             if (newNum==1733){
                            System.out.println("1733 step="+allSteps[newNum]);
                        }
                        if (newNum==3733){
                            System.out.println("3733 step="+allSteps[newNum]);
                        }
*/

POJ3278

package poj3278;

import java.util.Queue;

import java.util.concurrent.LinkedBlockingQueue;
import java.util.Scanner;
/**
 * @Author jinjun99
 * @Date Created in 2022/9/30 21:16
 * @Description 每次移动有3种选择，求最小步数，BFS，搜索完当前步的所有可能性再走下一步。已AC
 * @Since version-1.0
 */
public class Main {

    static class Node{
        /**
         * 位置
         */
        int x;
        /**
         * 时间
         */
        int t;

        public Node(int x, int t) {
            this.x = x;
            this.t = t;
        }

        public Node() {
        }
    }

    static int maxInt = 100005;
    /**
     * 判断是否走过
     */
    static int[] walk;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        walk = new int[maxInt];

//        NodeLinkedList list = new NodeLinkedList();
        Queue<Node> list = new LinkedBlockingQueue<Node>();
        list.offer(new Node(n,0));
        while (!list.isEmpty()){
            Node node = list.poll();
            int x1 = node.x;
            int x2 = x1+1;
            int x3 = x1-1;
            int x4 = x1*2;
            int t1 = node.t+1;

            if (x1==k){
                System.out.println(node.t);
                break;
            }
            if (x2<maxInt&&walk[x2]==0){
                walk[x2]=1;
                list.offer(new Node(x2,t1));
            }
            if (x3>=0&&walk[x3]==0){
                walk[x3]=1;
                list.offer(new Node(x3,t1));
            }
            if (x4<maxInt&&walk[x4]==0){
                walk[x4]=1;
                list.offer(new Node(x4,t1));
            }
        }
    }
}


/*
5 17
5 1700

  long st = System.currentTimeMillis();
 long e = System.currentTimeMillis();
        System.out.println("计算时长："+(e-st)+"ms");
*/

 /* static class NodeLinkedList{
        int capacity =1000;
        Node[] list = new Node[capacity];
        int f = 0;
        int l = 0;
        int size = 0;

        public void offer(Node n){
            if (l==capacity-5){
                expansion();
            }
            list[l] = n;
            l++;
            size++;

        }
        public Node poll(){
            Node n = list[f];
            list[f]=null;
            f++;
            size--;
            return n;
        }
        public boolean isEmpty(){
            return size == 0;
        }

        private void expansion(){
            capacity = capacity*2;
            Node[] list1 = new Node[capacity];
            for (int i = 0; i < size; i++) {
                list1[i] = list[f];
                f++;
            }
            f=0;
            l=size-1;
            list=list1;
        }

        public NodeLinkedList(int capacity) {
            this.capacity = capacity;
        }

        public NodeLinkedList() {
        }
    }*/

POJ3414

package poj3414;

import java.io.BufferedInputStream;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @Author jinjun99
 * @Date Created in 2022/10/2 22:06
 * @Description 多选择求最少选择次数，BFS 已AC
 * @Since version-1.0
 */
public class Main {
    static int maxInt = 110;
    /**
     * 标记一种状态是否入队过
     */
    static int[][] visit;
    /**
     * 水杯容量
     */
    static int a, b, c;
    /**
     * 最小步数
     */
    static Node optimalN;
    static LinkedList<Node> list;
    /**
     * 标记路径
     */
    static int[] path;
    /**
     * 打印可选单词
     */
    static String[] word = {"", "FILL(1)", "FILL(2)", "DROP(1)",
            "DROP(2)", "POUR(1,2)", "POUR(2,1)", "impossible", "", "", ""};

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));

            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();
            if (a == c || b == c) {
                System.out.println(1);
                if (a==c){
                    System.out.println(word[1]);
                }else {
                    System.out.println(word[2]);
                }
            } else {
                visit = new int[maxInt][maxInt];
                optimalN = new Node(null, 0, 0, 0, 0);
                list = new LinkedList<Node>();
                bfs();
                if (optimalN.step == 0) {
                    System.out.println(word[7]);
                } else {
                    System.out.println(optimalN.step);
                    int index = optimalN.step;
                    int len = index;
                    path = new int[len + 5];

                    while (optimalN.parent != null) {
                        path[index] = optimalN.op;
                        optimalN = optimalN.parent;
                        index--;
                    }
                    for (int i = 1; i <= len; i++) {
                        System.out.println(word[path[i]]);
                    }
                }
            }

    }

    private static void bfs() {
        Node root = new Node(null, 0, 0, 0, 0);
        visit[0][0] = 1;
//        LinkedList<Node> list = new LinkedList<Node>();
        list.offer(root);
        while (!list.isEmpty()) {
            Node parent = list.poll();
            int a1 = parent.a1;
            int b1 = parent.b1;
            int step1 = parent.step;
            int childA;
            int childB;
            for (int i = 1; i <= 6; i++) {
                childA = a1;
                childB = b1;

                /*操作一：a杯倒满*/
                if (i == 1) {
                    childA = a;
                }
                /*操作二：b杯倒满*/
                if (i == 2) {
                    childB = b;
                }
                /*操作三：a杯倒空*/
                if (i == 3) {
                    childA = 0;
                }
                /*操作四：b杯倒空*/
                if (i == 4) {
                    childB = 0;
                }
                /*操作五：a倒入b*/
                if (i == 5) {
                    /*全倒入*/
                    if (childA + childB <= b) {
                        childB += childA;
                        childA = 0;
                    } else {/*剩一点*/
                        childA -= b - childB;
                        childB = b;
                    }
                }
                /*操作六：b倒入a*/
                if (i == 6) {
                    /*全倒入*/
                    if (childA + childB <= a) {
                        childA += childB;
                        childB = 0;
                    } else {/*剩一点*/
                        childB -= a - childA;
                        childA = a;
                    }
                }
                /*如果当前两杯的状态未出现过*/
                if (visit[childA][childB] == 0) {
                    /*标记该状态*/
                    visit[childA][childB] = 1;

                    /*当前步数比最优节点小才有必要入队*/
                    if (optimalN.step == 0 || step1 + 1 < optimalN.step) {
                        /*创建子节点*/
                        Node child = new Node(parent, childA, childB, i, step1 + 1);

                        /*如果找到c水量就记录一次最优解*/
                        if (childA == c || childB == c) {
                            optimalN = child;
                        }else {
                            list.offer(child);
                        }
                    }
                }
            }
        }
    }

    static class Node {
        Node parent;
        /**
         * a杯当前水量
         */
        int a1;
        /**
         * b杯当前水量
         */
        int b1;
        /**
         * 当前操作
         */
        int op;
        /**
         * 记录步数
         */
        int step;

        public Node(Node parent, int a1, int b1, int op, int step) {
            this.parent = parent;
            this.a1 = a1;
            this.b1 = b1;
            this.op = op;
            this.step = step;
        }
    }
}
/*
3 5 4
3 5 5
4 8 9
7 6 4
AC经验：忘了初始是空杯子，355的情况直接输出0了，还有题目只给一个案例，就不要加 while (sc.hasNext())


*/

原文地址：http://www.cnblogs.com/jinjun99/p/16807527.html