編集: run() 関数で BFS を実装する必要があると思いますか?
EDIT2:コードを現在のものに更新しました。私はそれに慣れていませんが、電源導体にアスタリスクを追加することに成功しているようです. 家の総数と停電している家の数を出力する必要がありますが、その量を適切に追跡する方法がわかりません。
EDIT3：わかりました、グリッドの塗りつぶしが正しいと完全に確信しています。しかし、電力が供給されていない家の数を追跡することはできません。それに関するアドバイスは素晴らしいでしょう。
アイデアは次のとおりです。
シンボルでいっぱいの hxw 行列が与えられました。それらの1つは、発電所を表す文字「P」です。その発電所からは、どの大文字でも導電性があり、マップ全体に電気を運ぶことができます。その上に、電気も運ぶワイヤーを表す 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;
}
}
}