java - 使用广度优先填充算法填充 "power grid"；我被困住了

Question

编辑:我想我可能必须在 run() 函数中实现 BFS？

EDIT2:我已将代码更新为现在的代码。我对此不太满意，但它似乎成功地在电源导体上添加了星号。我必须输出房屋总数以及有多少房屋断电，但我不知道如何正确跟踪该数量。

EDIT3:好的，我完全相信我的网格填充是正确的。然而，我无法追踪没有通电的房屋数量。任何有关这方面的建议都会很棒。

这个想法是这样的:

给我一​​个充满符号的 h x w 矩阵。其中之一是字母“P”，代表发电厂。从该发电厂出发，任何大写字母都是导电的，可以将电力输送到 map 上。最重要的是，有 3 个符号代表电线也可以传输电力。它们是:+、- 和 |

最后，还有字母“H”代表的房屋。如果靠近任何其他导电符号，这些符号也具有导电性。这个想法是，如果电力可以到达，则用星号“*”填充网格。问题是每个发电厂 P 只能为 30 个家庭 H 供电。我发布的代码显然尚未完成，但广度优先填充算法(bff)已完成。我可以成功填充 P 旁边的任何直接符号，但我无法弄清楚如何继续使用不同的符号追踪 P。欢迎任何想法。

输入示例:

15 22
, , , , , , , , , , . . . , , , , , , , , ,
, , . , , , , , , H H H - - + , , , , , , ,
, , , , , , , , , H H H . . | . , , , . , ,
, , , , , , , , , H H H = , | . , , , . . .
, , , , , , , , , H H H = , | . , , , . . .
, , , . . . . . , H H H = , | , , , , . . .
. . . . . . . . , H H H = , | , , , , . . .
, , . , , = = = = = = = = , | , , , . . . .
, , X X X X , . . . . C C C C C C . . . . .
. . X P X X , . . . . C C C C C C . . . . .
. . X X X X - - - - - C C C C C C . . . . .
. ~ X X X X . . . . . . . . . . . . . . . .
~ ~ ~ ~ . . . . . . . . . . . . . . . . . .
~ ~ ~ ~ ~ . . . . . . . . . . . . . . . . ~
~ ~ ~ ~ ~ ~ . . . . . . . . . . . ~ ~ . ~ ~

示例输出:

0 of 18 homes are without power .
, , , , , , , , , , . . . , , , , , , , , ,
, , . , , , , , , * * * * * * , , , , , , ,
, , , , , , , , , * * * . . * . , , , . , ,
, , , , , , , , , * * * = , * . , , , . . .
, , , , , , , , , * * * = , * . , , , . . .
, , , . . . . . , * * * = , * , , , , . . .
. . . . . . . . , * * * = , * , , , , . . .
, , . , , = = = = = = = = , * , , , . . . .
, , * * * * , . . . . * * * * * * . . . . .
. . * * * * , . . . . * * * * * * . . . . .
. . * * * * * * * * * * * * * * * . . . . .
. ~ * * * * . . . . . . . . . . . . . . . .
~ ~ ~ ~ . . . . . . . . . . . . . . . . . .
~ ~ ~ ~ ~ . . . . . . . . . . . . . . . . ~
~ ~ ~ ~ ~ ~ . . . . . . . . . . . ~ ~ . ~ ~

到目前为止的代码:

public class PowerGrid {
    String[][] grid = new String[120][120];
    LinkedList<Pair> q = new LinkedList<Pair>();
    LinkedList<Pair> visited = new LinkedList<Pair>();
    Map<Pair, Integer> dist = new HashMap<Pair, Integer>();
    ArrayList<Pair> pwrPlants = new ArrayList<Pair>();
    String[] alphabet = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L",
            "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};  
    int row = -1;
    int col = -1;

    int homesToPwr = 0;
    int homesNotPwrd = 0;
    int totalHomes = 0;

    public static void main (String[] args) {
        PowerGrid pg = new PowerGrid();
        pg. run();

    }

    public void run() {
        Scanner sc = new Scanner(System.in);

        row = sc.nextInt();
        col = sc.nextInt();

        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++) {
                grid[i][j] = sc.next();
        }

        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++) {
                if (grid[i][j].equals("P")) {
                    Pair tmpPair = new Pair(i, j);
                    pwrPlants.add(tmpPair);
                }
            }

        for (Pair p : pwrPlants) {
            homesToPwr += 30;
            for (String s : alphabet) {
                if (s == "H") 
                    if (homesToPwr != 0) 
                        homesToPwr--;                       

                bff(grid, p.x, p.y, s, "*");
            }

            bff(grid, p.x, p.y, "-", "*");
            bff(grid, p.x, p.y, "+", "*");
            bff(grid, p.x, p.y, "|", "*");
        }

        System.out.println(homesToPwr + " of " + totalHomes + " are without power.");

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(grid[i][j]);
            }
            System.out.println();
        }
    }

    public void bff (String[][] grid, int x, int y, String oldSymbol, String newSymbol) {
        if (oldSymbol == newSymbol) return;


        Pair pair = new Pair(x,y);
        q.addLast(pair);
        dist.put(pair, 0);
        grid[x][y] = newSymbol;

        while (!q.isEmpty()) {
            Pair v = q.getFirst();
            q.pop();
            int d = dist.get(v) + 1;
            String[] symbols = {"+", "-", "|"};

            visit(grid, v.x + 1, v.y, new Pair(v.x+1, v.y), oldSymbol, newSymbol, d);
            visit(grid, v.x - 1, v.y, new Pair(v.x-1, v.y), oldSymbol, newSymbol, d);
            visit(grid, v.x, v.y + 1, new Pair(v.x, v.y+1), oldSymbol, newSymbol, d);
            visit(grid, v.x, v.y - 1, new Pair(v.x, v.y-1), oldSymbol, newSymbol, d);

            for (String t : alphabet){
                if (t == "H") {
                    if (homesToPwr != 0) {
                        homesToPwr--;
                    }
                }

                    visit(grid, v.x + 1, v.y, new Pair(v.x+1, v.y), t, newSymbol, d);
                    visit(grid, v.x - 1, v.y, new Pair(v.x-1, v.y), t, newSymbol, d);
                    visit(grid, v.x, v.y + 1, new Pair(v.x, v.y+1), t, newSymbol, d);
                    visit(grid, v.x, v.y - 1, new Pair(v.x, v.y-1), t, newSymbol, d);

            }
            for (String s : symbols) {
                visit(grid, v.x + 1, v.y, new Pair(v.x+1, v.y), s, newSymbol, d);
                visit(grid, v.x - 1, v.y, new Pair(v.x-1, v.y), s, newSymbol, d);
                visit(grid, v.x, v.y + 1, new Pair(v.x, v.y+1), s, newSymbol, d);
                visit(grid, v.x, v.y - 1, new Pair(v.x, v.y-1), s, newSymbol, d);
            }
        }
    }

    public void visit (String[][] A, int x, int y, Pair pair, String oldSymbol, String newSymbol, int d) {
        if ((x >= 0 && y >= 0) && (x < row && y < col) && A[x][y].equals(oldSymbol)) {
            if (oldSymbol == "H")
                totalHomes++;
            A[x][y] = newSymbol;
            dist.put(pair, d);
            q.addLast(pair);

        }
    }

    public class Pair {
        int x, y;
        public Pair (int x, int y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            String out = "X: " + this.x + "  Y: " + this.y;
            return out;
        }
    }
}

Answer 1

您的程序未正确计算房屋总数。

例如，这里有 19 栋房屋，但通过访问方法只统计到 18 栋。这是因为您只访问“连接”到发电厂的案例。

15 22
, , , , , , , , , , . . . , , , , , , , , ,
, , . , , , , H , H H H - - + , , , , , , ,
, , , , , , , , , H H H . . | . , , , . , ,
, , , , , , , , , H H H = , | . , , , . . .
, , , , , , , , , H H H = , | . , , , . . .
, , , . . . . . , H H H = , | , , , , . . .
. . . . . . . . , H H H = , | , , , , . . .
, , . , , = = = = = = = = , | , , , . . . .
, , X X X X , . . . . C C C C C C . . . . .
. . X P X X , . . . . C C C C C C . . . . .
. . X X X X - - - - - C C C C C C . . . . .
. ~ X X X X . . . . . . . . . . . . . . . .
~ ~ ~ ~ . . . . . . . . . . . . . . . . . .
~ ~ ~ ~ ~ . . . . . . . . . . . . . . . . ~
~ ~ ~ ~ ~ ~ . . . . . . . . . . . ~ ~ . ~ ~

您可以这样计算房屋总数:

    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++) {
            grid[i][j] = sc.next();
            if(grid[i][j].equals("H")){
                totalHomes++;
            }
        }

然后用这种方法计算实际的供电房屋数量(我使用了一个新属性homesPwrd(=0)，仅通过此方法修改，不确定您所有其他整数有什么用......):

public void visit (String[][] A, int x, int y, Pair pair, String oldSymbol, String newSymbol, int d) {
    if ((x >= 0 && y >= 0) && (x < row && y < col) && A[x][y].equals(oldSymbol)) {
        if (oldSymbol == "H")
            homesPwrd++;
        A[x][y] = newSymbol;
        dist.put(pair, d);
        q.addLast(pair);

    }
}

终于

    System.out.println(totalHomes-homesPwrd + " of " + totalHomes + " are without power.");

输出

19 个中的 1 个断电。

    1 of 19 are without power.
    ,,,,,,,,,,...,,,,,,,,,
    ,,.,,,,H,******,,,,,,,
    ,,,,,,,,,***..*.,,,.,,
    ,,,,,,,,,***=,*.,,,...
    ,,,,,,,,,***=,*.,,,...
    ,,,.....,***=,*,,,,...
    ........,***=,*,,,,...
    ,,.,,========,*,,,....
    ,,****,....******.....
    ..****,....******.....
    ..***************.....
    .~****................
    ~~~~..................
    ~~~~~................~
    ~~~~~~...........~~.~~