編輯:我想我可能必須在run()函數中實現BFS?使用寬度優先填充算法填充「電網」;我卡住了
編輯2:我已經更新了我現在擁有的代碼。我對此感到不舒服,但它似乎成功地爲電源線添加了星號。我必須輸出總房子,有多少人沒有電力,但我不知道如何正確跟蹤這一數量。編輯3:好吧,我完全相信,我有正確的網格填充。但是,我無法跟蹤未通電的房屋數量。任何意見都會很好。
這裏的想法:
我給出的高x寬矩陣滿符號。其中一個將是代表發電廠的字母「P」。從那個發電廠來看,任何大寫字母都具有導電性,可以通過地圖傳輸電力。最重要的是,有3個符號代表電線也可以帶電。他們是:+, - 和|
最後,有一些由字母「H」表示的房屋。如果在任何其他導電符號旁邊,它們也是導電的。這個想法是如果功率可以達到的話,用星號「*」填滿網格。值得注意的是,每個發電廠P只能爲30個家庭提供電力。我發佈的代碼顯然未完成,但廣度優先填充算法(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;
}
}
}
我愛你的教授。 – 2013-04-28 04:14:17
@CoryKendall哈哈,爲什麼呢? – 2013-04-28 04:16:13
我想你錯過了像+, - ,和| – Dominik 2013-04-28 05:15:51