以遞歸方式查找2D陣列中的連接

Question

我有一款遊戲，並且在執行分數時遇到問題。教授指出，它必須在沒有for循環的情況下遞歸地完成。但是我很難考慮使用的算法。這是遊戲。

評分系統的工作原理是從閥門管道（Pipe.ValvePipe）開始，然後檢查有多少管道連接到它。有這種類型的遞歸有一定的算法/策略嗎？先謝謝你。

pipe.java public class Pipe {0} {0} {0}私人布爾openAtTop; private boolean openAtRight; private boolean openAtBottom; private boolean openAtLeft; private boolean isValve;

private static Pipe  VALVE_PIPE; 

public Pipe(boolean t, boolean r, boolean b, boolean l, boolean valve) { 
    openAtTop = t; openAtBottom = b; openAtRight = r; openAtLeft = l; 
    isValve = valve; 
} 

public boolean isValve() { return isValve; } 
public static Pipe ValvePipe() { return new Pipe(false, false, true, false, true); } 

public boolean isValid() { return !(!openAtTop&&!openAtBottom&&!openAtLeft&&!openAtRight); } 
public static Pipe RandomPipe() { 
    Pipe p; 
    do { 
     p = new Pipe(Math.random() < 0.5, Math.random() < 0.5, 
        Math.random() < 0.5, Math.random() < 0.5, false); 
    } while (!p.isValid()); 
    return p; 
} 

public boolean isOpenAtTop() { return openAtTop; } 
public boolean isOpenAtBottom() { return openAtBottom; } 
public boolean isOpenAtLeft() { return openAtLeft; } 
public boolean isOpenAtRight() { return openAtRight; } 

public boolean fitsBelow(Pipe p) { 
    return (p == null) || (!openAtTop && !p.isOpenAtBottom()) || (openAtTop && p.isOpenAtBottom()); 
} 
public boolean fitsAbove(Pipe p) { 
    return (p == null) || (!openAtBottom && !p.isOpenAtTop()) || (openAtBottom && p.isOpenAtTop()); 
} 
public boolean fitsToLeftOf(Pipe p) { 
    return (p == null) || (!openAtRight && !p.isOpenAtLeft()) || (openAtRight && p.isOpenAtLeft()); 
} 
public boolean fitsToRightOf(Pipe p) { 
    return (p == null) || (!openAtLeft && !p.isOpenAtRight()) || (openAtLeft && p.isOpenAtRight()); 
} 

public String toString() { 
    String s = ""; 
    if (openAtTop) s+="1"; else s+="0"; 
    if (openAtRight) s+="1"; else s+="0"; 
    if (openAtBottom) s+="1"; else s+="0"; 
    if (openAtLeft) s+="1"; else s+="0"; 
    return s; 
} 
public int toInt() { 
    int s = 0; 
    if (openAtTop) s+=8; 
    if (openAtRight) s+=4; 
    if (openAtBottom) s+=2; 
    if (openAtLeft) s+=1; 
    return s; 
} 

}

PipeGameView.java 
import java.awt.*; 
import javax.swing.*; 

// Subclass JFrame so you can display a window 
public class PipeGameView extends JPanel { 
    private PipeGame  game;  // The model 

    private BoardPanel  tiles; 
    private JButton[][]  buttons; 
    private JProgressBar timeBar; 
    private JButton   startStop; 
    private JRadioButton twoMinButton, tenMinButton, noLimitButton; 
    private JLabel   statusLabel; 

    // This constructor builds the window 
    public PipeGameView(PipeGame g) { 
     game = g;  // Store the model for access in update() 

     // Set up the components 
     tiles = new BoardPanel(); 
     tiles.setLayout(new GridLayout(game.getRows(), game.getRows())); 
     buttons = new JButton[game.getRows()][game.getRows()]; 

     // Add the buttons to the tile panel 
     ImageIcon ic = new ImageIcon("Pipes0000.GIF"); 
     for (int r=0; r<game.getRows(); r++) { 
      for (int c=0; c<game.getRows(); c++) { 
       buttons[r][c] = new JButton(ic); 
       tiles.add(buttons[r][c]); 
      } 
     } 

     // Now layout the components using a gridbag layout 
     GridBagLayout layout = new GridBagLayout(); 
     GridBagConstraints layoutConstraints = new GridBagConstraints(); 
     this.setLayout(layout); 

     // Add the Start/Stop Button 
     startStop = new JButton("Start Game"); 
     layoutConstraints.gridx = 0; layoutConstraints.gridy = 0; 
     layoutConstraints.gridwidth = 1; layoutConstraints.gridheight = 1; 
     layoutConstraints.fill = GridBagConstraints.BOTH; 
     layoutConstraints.insets = new Insets(2, 2, 2, 2); 
     layoutConstraints.anchor = GridBagConstraints.NORTHWEST; 
     layoutConstraints.weightx = 0.0; layoutConstraints.weighty = 0.0; 
     layout.setConstraints(startStop, layoutConstraints); 
     this.add(startStop); 

     // Add the JRadioButtons 
     twoMinButton = new JRadioButton("2 minutes"); 
     tenMinButton = new JRadioButton("10 minutes"); 
     noLimitButton = new JRadioButton("No Time Limit"); 
     ButtonGroup group = new ButtonGroup(); 
     group.add(twoMinButton); group.add(tenMinButton); group.add(noLimitButton); 

     layoutConstraints.gridx = 1; 
     layout.setConstraints(twoMinButton, layoutConstraints); 
     this.add(twoMinButton); 
     layoutConstraints.gridx = 2; 
     layout.setConstraints(tenMinButton, layoutConstraints); 
     this.add(tenMinButton); 
     layoutConstraints.gridx = 3; 
     layout.setConstraints(noLimitButton, layoutConstraints); 
     this.add(noLimitButton); 

     // Add the tiles 
     layoutConstraints.gridx = 0; layoutConstraints.gridy = 1; 
     layoutConstraints.gridwidth = 4; layoutConstraints.gridheight = 1; 
     layoutConstraints.fill = GridBagConstraints.BOTH; 
     layoutConstraints.insets = new Insets(2, 2, 2, 2); 
     layoutConstraints.anchor = GridBagConstraints.NORTHWEST; 
     layoutConstraints.weightx = 0.0; layoutConstraints.weighty = 0.0; 
     layout.setConstraints(tiles, layoutConstraints); 
     this.add(tiles); 

     // Add the label 
     statusLabel = new JLabel("Time Left: "); 
     statusLabel.setVisible(false); 
     layoutConstraints.gridx = 0; layoutConstraints.gridy = 2; 
     layoutConstraints.gridwidth = 1; layoutConstraints.gridheight = 1; 
     layoutConstraints.fill = GridBagConstraints.NONE; 
     layoutConstraints.insets = new Insets(2, 2, 2, 2); 
     layoutConstraints.anchor = GridBagConstraints.WEST; 
     layoutConstraints.weightx = 0.0; layoutConstraints.weighty = 0.0; 
     layout.setConstraints(statusLabel, layoutConstraints); 
     this.add(statusLabel); 

     timeBar = new JProgressBar(0, 100); 
     timeBar.setValue(100); 
     timeBar.setVisible(false); 
     layoutConstraints.gridx = 1; layoutConstraints.gridy = 2; 
     layoutConstraints.gridwidth = 3; layoutConstraints.gridheight = 1; 
     layoutConstraints.fill = GridBagConstraints.HORIZONTAL; 
     layoutConstraints.insets = new Insets(2, 2, 2, 2); 
     layoutConstraints.anchor = GridBagConstraints.EAST; 
     layoutConstraints.weightx = 5.0; layoutConstraints.weighty = 0.0; 
     layout.setConstraints(timeBar, layoutConstraints); 
     this.add(timeBar); 
     update(); 
    } 

    // Get methods for the components 
    public JButton getButton(int r, int c) { return buttons[r][c]; } 
    public JButton getStartStopButton() { return startStop; } 
    public JProgressBar getTimeBar() { return timeBar; } 
    public JRadioButton getTwoMinButton() { return twoMinButton; } 
    public JRadioButton getTenMinButton() { return tenMinButton; } 
    public JRadioButton getNoLimitButton() { return noLimitButton; } 

    public void setGame(PipeGame g) { game = g; } 


    // This is called whenever the model has changed. Note that this code is not efficient. All ICONS should really 
    // be loaded upon game start and stored into a static array of ImageIcons. Then, these static icons should be 
    // used instead of re-creating icons each time. 
    public void update() { 
     // Update the look of the buttons 
     for (int r=0; r<game.getRows(); r++) { 
      for (int c=0; c<game.getRows(); c++) { 
       if (game.isOver()) 
        buttons[r][c].setEnabled(false); 
       else 
        buttons[r][c].setEnabled(true); 

       if (game.getPipe(r,c) == null) 
        buttons[r][c].setSelected(false); 
       else { 
        // Determine the portion of the icon's filename that matches the pipe 
        String currentPipeCodes = "Start"; 
        if (!game.getPipe(r,c).isValve()) 
         currentPipeCodes = game.getPipe(r,c).toString(); 
        buttons[r][c].setSelectedIcon(new ImageIcon("pipes"+ currentPipeCodes +".GIF")); 
        buttons[r][c].setSelected(true); 
       } 
      } 
     } 

     // Update the start/stop button 
     if (game.isOver()) 
      startStop.setText("Start"); 
     else 
      startStop.setText("Stop"); 

     // Update the radio buttons 
     if (game.isOver()) { 
      twoMinButton.setEnabled(true); 
      tenMinButton.setEnabled(true); 
      noLimitButton.setEnabled(true); 
     } 
     else { 
      twoMinButton.setEnabled(false); 
      tenMinButton.setEnabled(false); 
      noLimitButton.setEnabled(false); 
     } 

     // Update the status label 
     if (game.isOver()) { 
      statusLabel.setText("Final Score: " + game.getPlacedPipes()); 
      statusLabel.setVisible(true); 
     } 
     else { 
      if (game.getStyle() == 2) { 
       statusLabel.setVisible(false); 
      } 
      else { 
       statusLabel.setText("Time Left: "); 
       statusLabel.setVisible(true); 
      } 
     } 

     // Update the timer bar 
     if (game.isOver() || (game.getStyle() == 2)) { 
      timeBar.setVisible(false); 
     } 
     else { 
      timeBar.setValue((int)(game.getTimeRemaining()/(float)game.getTimeLimit() * 100)); 
      timeBar.setVisible(true); 
     } 

     // Update the cursor 
     ImageIcon i; 
     if (game.isOver()) { 
      tiles.setCursor(Cursor.getDefaultCursor()); 
     } 
     else { 
      if (game.getNextPipe().isValve()) 
       i = new ImageIcon("pipesStart.GIF"); 
      else 
       i = new ImageIcon("pipes"+ game.getNextPipe().toString() +".GIF"); 
      tiles.setCursor(Toolkit.getDefaultToolkit().createCustomCursor(i.getImage(), new Point(0,0), "pipe")); 
     } 
    } 
} 

Answer 1

我沒有經歷所有的代碼，但作爲一個提示的功能應該是這樣的：

getScore(Pipe p){ 
    if (p == null) return 0; 
    int res = 1; // size of this pipe 
    res += getScore(leftPipe); 
    res += getScore(rightPipe); 
    ... 
    return res; 
} 

希望這有助於

Answer 2

我想你需要包括行和列以計算連接到主起動管道的管道

public void connectedPipes(int row, int col){ 
    if(row == null) return 0; 
    int res = 1; // size of this pipe 
    res += getScore(leftPipe); 
    res += getScore(rightPipe); 
    return res; 
}