[Java] 迷宫寻路

题目请参考:PTA7-1 迷宫寻路 (20分)

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

public class Main {

    static final Scanner input = new Scanner(System.in);

    public static void main(String[] args) {
        for (;;) {
            int row = input.nextInt();
            if (row < 0) {
                break;
            }
            Maze maze = new Maze(row, input.nextInt());
            if (maze.process()) {
                Maze.Node now = maze.goal;
                StringBuilder sb = new StringBuilder();
                while (now != null) {
                    sb.insert(0, now.forPrint());
                    now = now.from;
                }
                System.out.println(sb);
            } else {
                System.out.println("NO FOUND");
            }
        }
    }

    static class Maze {
        int row;
        int col;
        Node[][] maze;
        PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparing(Node::f));
        Node goal;

        class Node {
            final int x;
            final int y;
            int g;
            final int h;
            Node from;
            boolean closed;

            Node(int x, int y) {
                this.x = x;
                this.y = y;
                h = Math.abs(x - row) + Math.abs(y - col);
            }

            int f() {
                return g + h;
            }

            void setParent(Node parent) {
                g = parent.g + 1;
                from = parent;
            }

            String forPrint() {
                return (x + 1) + "," + (y + 1) + System.lineSeparator();
            }

            void addToClose() {
                closed = true;
            }
        }

        Maze(int row, int col) {
            this.row = row;
            this.col = col;
            maze = new Node[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (input.nextInt() == 0) {
                        maze[i][j] = new Node(i, j);
                    }
                }
            }
            goal = maze[row - 1][col - 1];
        }

        boolean process() {
            if (maze[0][0] != null) {
                open.add(maze[0][0]);
            }
            while (!open.isEmpty()) {
                Node parent = open.poll();
                if (parent == goal) {
                    return true;
                }
                parent.addToClose();
                spread(parent);
            }
            return false;
        }

        void spread(Node parent) {
            int x = parent.x;
            int y = parent.y;
            trySpread(parent, x - 1, y);
            trySpread(parent, x + 1, y);
            trySpread(parent, x, y - 1);
            trySpread(parent, x, y + 1);
        }

        void trySpread(Node parent, int childX, int childY) {
            if (childX < 0 || childX == row || childY < 0 || childY == col) {
                return;
            }
            Node child = maze[childX][childY];
            if (child == null || child.closed) {
                return;
            }
            if (open.contains(child)) {
                if (parent.g + 1 < child.g) {
                    child.setParent(parent);
                }
            } else {
                child.setParent(parent);
                open.add(child);
            }
        }

    }
}

[蓝桥杯] 试题 算法训练 Anagrams问题

// http://lx.lanqiao.cn/problem.page?gpid=T223

Scanner in = new Scanner(System.in);

String a = in.nextLine().toLowerCase();
String b = in.nextLine().toLowerCase();
int[] alp = new int[26];

for (char ch : a.toCharArray())
    alp[ch - 'a']++;
for (char ch : b.toCharArray())
    alp[ch - 'a']--;

boolean ret = true;
for (int i : alp) {
    if (i != 0) {
        ret = false;
        break;
    }
}

System.out.println(ret ? "Y" : "N");

[蓝桥杯] 算法训练 审美课

// http://lx.lanqiao.cn/problem.page?gpid=T519
Scanner in = new Scanner(System.in);
int n = in.nextInt();// 学生数
int m = in.nextInt();// 图画数
int pattern = (1 << m) - 1;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(n);
for (int i = 0; i < n; i++) {
    int num = 0;
    for (int j = 0; j < m; j++) {
        num <<= 1;
        if (in.nextInt() == 1) {
            num |= 1;
        }
    }
    map.merge(num, 1, Integer::sum);
}
int ret = 0;
for (Entry<Integer, Integer> e : map.entrySet()) {
    ret += e.getValue() * map.getOrDefault(~e.getKey() & pattern, 0);
}
System.out.println(ret / 2);