2013-04-28 39 views
3

編輯:我想我可能必須在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; 
     } 
    } 
} 
+2

我愛你的教授。 – 2013-04-28 04:14:17

+0

@CoryKendall哈哈,爲什麼呢? – 2013-04-28 04:16:13

+0

我想你錯過了像+, - ,和| – Dominik 2013-04-28 05:15:51

回答

0

你的程序是不正確的計數房屋的總nomber。

例如,這裏有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++; 
      } 
     } 

然後計數動力房屋的實際數量這種方式(I使用的新屬性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."); 

輸出

1 of 19 are no power。

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