二维数组中的寻路算法 [英] Algorithm for pathfinding in 2D Array
本文介绍了二维数组中的寻路算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我想知道如何找到从一个单元格穿过所有具有相同值的单元格回到起始单元格的路径.这里的 value 是指 Token.CERCLE_ROUGE 或 Token.CERCLE_BLEU
I would like to know how to find the path from a cell passing through all cells which have same value back to the starting cell.
By value here I mean either Token.CERCLE_ROUGE or Token.CERCLE_BLEU
考虑 cell(4,5) == Token.CERCLE_BLEU 并且有邻居:3,4 - 4,4 - 5,4 - 3,5 - 5,5 - 3,6 - 4,6 - 5,6 全部 == Token.CERCLE_ROUGE
Consider cell(4,5) == Token.CERCLE_BLEU and has neighbors: 3,4 - 4,4 - 5,4 - 3,5 - 5,5 - 3,6 - 4,6 - 5,6 all of them == Token.CERCLE_ROUGE
现在我们以 cell(3,4) 作为起点:如何找到通过 (4,4), (5,4), (3,5), (5,5), (3,6), (4,6), (5,6) 然后回到 (3,4).在这里，我们可以绘制一条从一个单元格到另一个单元格的线段，这样 cell(4,5) 将位于中心.(见下图)
Now we have cell(3,4) as starting point: how one can find a path passing through (4,4), (5,4), (3,5), (5,5), (3,6), (4,6), (5,6) then back to (3,4). Here we can draw a line segment passing from cell to cell so that cell(4,5) will be in the center. (See the image below)
这里的想法是捕获"对手的令牌，这就是玩家获得积分的方式.
The idea here is to "capture" opponent's token, that's how a player gains points.
如果需要，我会更新任何信息.
I'll update with any information if needed.
更新:
我找到了一个我认为可以解决这个问题的寻路实用程序，但我不知道如何实现它:https://gist.github.com/benruijl/3385624
I found a pathfinding utility that I think can solve this, but I have no idea how to implement it: https://gist.github.com/benruijl/3385624
下面是我的代码:
这个枚举类代表一个细胞状态:
This enum class represents a cell state:
public enum Token {
VIDE, CERCLE_BLEU, CERCLE_ROUGE
}
我使用下面的代码来检查单元格的邻居:
I use the code below to check for neighbors of a cell:
public void neighbours(int row, int col) {
for (int colNum = col - 1 ; colNum <= (col + 1) ; colNum +=1 ) {
for (int rowNum = row - 1 ; rowNum <= (row + 1) ; rowNum +=1 ) {
if(!((colNum == col) && (rowNum == row))) {
if(withinGrid (rowNum, colNum )) {
System.out.println("Neighbor of "+ row + " " + col + " is " + rowNum +" " + colNum +
" Contains "+ board[rowNum][colNum]);
}
}
}
}
}
private boolean withinGrid(int colNum, int rowNum) {
if((colNum < 0) || (rowNum <0) ) {
return false;
}
if((colNum >= COLS) || (rowNum >= ROWS)) {
return false;
}
return true;
}
我的整个代码如下.我还不能让它适应 MVC，到目前为止我所做的尝试似乎不起作用.
My whole code is below. I'm not yet able to adapt it to MVC, the attempts I made seems not to work so far.
import javax.swing.JFrame;
import java.awt.*;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import javax.swing.*;
public final class Pha extends JFrame {
public static int ROWS = 15;
public static int COLS = ROWS;
public static int cellSize = 15;
public static int canvasWidth = cellSize * COLS + (ROWS *4) ;
public static int canvasHeight = cellSize * ROWS ;
public static int gridWidth = 1;
public static int halfGridWidth = gridWidth / 2;
public static int cellPadding = cellSize / 5;
public static int symbolSize = cellSize - cellPadding * 2;
public static int symbolStrokeWidth = 3;
public enum GameState{
JOUE, NUL, CERCLE_ROUGE_GAGNE, CERCLE_BLEU_GAGNE
}
private GameState actualState;
public enum Token{
VIDE, CERCLE_ROUGE, CERCLE_BLEU
}
private Token actualPlayer;
private Token[][] board;
private final DrawCanvas canvas;
private JLabel statusBar;
public Pha(){
canvas = new DrawCanvas();
canvas.setPreferredSize(new Dimension(canvasWidth, canvasHeight));
canvas.addMouseListener(new MouseAdapter() {
@Override
public void mouseClicked(MouseEvent e) {
int x = e.getX();
int y = e.getY();
int selectedRow = y / cellSize;
int selectedCol;
selectedCol = x / cellSize;
if(actualState == GameState.JOUE){
if(selectedRow >= 0 && selectedRow < ROWS && selectedCol >= 0
&& selectedCol < COLS &&
board[selectedRow][selectedCol] == Token.VIDE){
board[selectedRow][selectedCol] = actualPlayer;
updateGame(actualPlayer, selectedRow, selectedCol);
actualPlayer = (actualPlayer == Token.CERCLE_BLEU)? Token.CERCLE_ROUGE : Token.CERCLE_BLEU;
neighbours(selectedRow, selectedCol);
}
} else {
initGame();
}
repaint();
}
});
statusBar = new JLabel(" ");
statusBar.setFont(new Font(Font.DIALOG_INPUT, Font.ITALIC, 15));
statusBar.setBorder(BorderFactory.createEmptyBorder(2, 5, 4, 5));
Container cp = getContentPane();
cp.setLayout(new BorderLayout());
cp.add(canvas, BorderLayout.EAST);
cp.add(statusBar, BorderLayout.NORTH);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
pack();
setTitle("Pha par esQmo");
setVisible(true);
board = new Token[ROWS][COLS];
initGame();
}
public void initGame(){
for(int ligne = 0; ligne < ROWS; ++ligne){
for(int colonne = 0; colonne < COLS; ++colonne){
board[ligne][colonne] = Token.VIDE;
}
}
actualState = GameState.JOUE;
actualPlayer = Token.CERCLE_ROUGE;
}
public void updateGame(Token theSeed, int ligneSelectionnee, int colonneSelectionnee) {
if (aGagne(theSeed, ligneSelectionnee, colonneSelectionnee)) {
actualState= (theSeed == Token.CERCLE_ROUGE) ? GameState.CERCLE_ROUGE_GAGNE : GameState.CERCLE_BLEU_GAGNE;
} else if (estNul()) {
actualState = GameState.CERCLE_BLEU_GAGNE;
}
}
public boolean estNul() {
/*for (int row = 0; row < ROWS; ++row) {
for (int col = 0; col < COLS; ++col) {
if (board[row][col] == Token.VIDE) {
return false;
}
}
}*/
return false;
}
public boolean aGagne(Token token, int ligneSelectionnee, int colonneSelectionnee) {
return false;
}
public void neighbours(int row, int col) {
for (int colNum = col - 1 ; colNum <= (col + 1) ; colNum +=1 ) {
for (int rowNum = row - 1 ; rowNum <= (row + 1) ; rowNum +=1 ) {
if(!((colNum == col) && (rowNum == row))) {
if(withinGrid (rowNum, colNum )) {
System.out.println("Neighbor of "+ row + " " + col + " is " + rowNum +" " + colNum );
}
}
}
}
}
private boolean withinGrid(int colNum, int rowNum) {
if((colNum < 0) || (rowNum <0) ) {
return false;
}
if((colNum >= COLS) || (rowNum >= ROWS)) {
return false;
}
return true;
}
class DrawCanvas extends JPanel{
@Override
public void paintComponent(Graphics g){
super.paintComponent(g);
setBackground(Color.WHITE);
g.setColor(Color.BLACK);
for(int ligne = 1; ligne < ROWS; ++ligne){
g.fillRoundRect(0, cellSize * ligne - halfGridWidth, canvasWidth - 1,
gridWidth, gridWidth, gridWidth);
}
for(int colonne = 1; colonne < COLS; ++colonne){
g.fillRoundRect(cellSize * colonne - halfGridWidth, 0
, gridWidth, canvasHeight - 1,
gridWidth, gridWidth);
}
Graphics2D g2d = (Graphics2D)g;
g2d.setStroke(new BasicStroke(symbolStrokeWidth,
BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND));
for(int ligne = 0; ligne < ROWS; ++ligne){
for(int colonne = 0; colonne < COLS; ++colonne){
int x1 = colonne * cellSize + cellPadding;
int y1 = ligne * cellSize + cellPadding;
if(board[ligne][colonne] == Token.CERCLE_ROUGE){
g2d.setColor(Color.RED);
g2d.drawOval(x1, y1, symbolSize, symbolSize);
g2d.fillOval(x1, y1, symbolSize, symbolSize);
} else
if(board[ligne][colonne] == Token.CERCLE_BLEU){
int x2 = colonne * cellSize + cellPadding;
g2d.setColor(Color.BLUE);
g2d.drawOval(x1, y1, symbolSize, symbolSize);
g2d.fillOval(x2, y1, symbolSize, symbolSize);
}
}
}
public static void main(String[] args){
SwingUtilities.invokeLater(() -> {
Pha pha = new Pha();
});
}
}
下面，充满鳗鱼的气垫船 提出的 MVC 有效，但不符合预期:
Below, the MVC proposed by Hovercraft Full Of Eels works, but not as expected:
代表细胞状态的枚举类:
The enum class representing cells state:
public enum Token {
VIDE, CERCLE_BLEU, CERCLE_ROUGE
}
控制:
import java.beans.IndexedPropertyChangeEvent;
import java.beans.PropertyChangeEvent;
import java.beans.PropertyChangeListener;
import javax.swing.JFrame;
public class Control {
private Model model;
private View view;
public Control(Model model, View view) {
this.model = model;
this.view = view;
view.createGrid(model.getRows(), model.getCols());
view.getMainPanel().addPropertyChangeListener(new ViewListener());
model.addPropertyChangeListener(Model.TOKEN, new ModelListener());
}
private class ViewListener implements PropertyChangeListener {
@Override
public void propertyChange(PropertyChangeEvent evt) {
if (evt.getPropertyName().equals(View.CELL_SELECTION)) {
int row = view.getSelectedRow();
int col = view.getSelectedCol();
Token token = model.getToken(row, col);
if (token == Token.VIDE) {
token = Token.CERCLE_BLEU;
} else if (token == Token.CERCLE_BLEU) {
token = Token.CERCLE_ROUGE;
} else {
token = Token.VIDE;
}
model.setToken(token, row, col);
}
}
}
private class ModelListener implements PropertyChangeListener {
@Override
public void propertyChange(PropertyChangeEvent evt) {
IndexedPropertyChangeEvent iEvt = (IndexedPropertyChangeEvent)evt;
int index = iEvt.getIndex();
int row = index / Model.COLS;
int col = index % Model.COLS;
Token token = (Token) evt.getNewValue();
view.setCell(token, row, col);
}
}
public void start() {
JFrame frame = new JFrame("MVC");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.add(view.getMainPanel());
frame.pack();
frame.setLocationRelativeTo(null);
frame.setVisible(true);
}
}
视图:
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.GridLayout;
import java.awt.RenderingHints;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.image.BufferedImage;
import java.util.EnumMap;
import java.util.Map;
import javax.swing.BorderFactory;
import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JLabel;
import javax.swing.JPanel;
public class View {
private static final int ICON_W = 12;
public static final String CELL_SELECTION = "cell selection";
private int rows;
private int cols;
private JPanel mainPanel = new JPanel();
private JLabel[][] grid;
private Map<Token, Icon> iconMap = new EnumMap<>(Token.class);
private int selectedRow;
private int selectedCol;
public View() {
iconMap.put(Token.VIDE, createIcon(new Color(0, 0, 0, 0)));
iconMap.put(Token.CERCLE_BLEU, createIcon(Color.BLUE));
iconMap.put(Token.CERCLE_ROUGE, createIcon(Color.RED));
}
private Icon createIcon(Color color) {
BufferedImage img = new BufferedImage(ICON_W, ICON_W, BufferedImage.TYPE_INT_ARGB);
Graphics2D g2 = img.createGraphics();
g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
g2.setColor(color);
g2.fillOval(1, 1, ICON_W - 2, ICON_W - 2);
g2.dispose();
return new ImageIcon(img);
}
public void createGrid(int rows, int cols) {
MyMouse myMouse = new MyMouse();
this.setRows(rows);
this.cols = cols;
mainPanel.setLayout(new GridLayout(rows, cols, 1, 1));
mainPanel.setBorder(BorderFactory.createLineBorder(Color.BLACK));
mainPanel.setBackground(Color.BLACK);
grid = new JLabel[rows][cols];
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[r].length; c++) {
grid[r][c] = new JLabel(iconMap.get(Token.VIDE));
grid[r][c].addMouseListener((MouseListener) myMouse); //cast
grid[r][c].setOpaque(true);
grid[r][c].setBackground(Color.WHITE);
mainPanel.add(grid[r][c]);
}
}
}
public JPanel getMainPanel() {
return mainPanel;
}
public int getSelectedRow() {
return selectedRow;
}
public int getSelectedCol() {
return selectedCol;
}
public void setCell(Token token, int row, int col) {
grid[row][col].setIcon(iconMap.get(token));
}
public int getRows() {
return rows;
}
public void setRows(int rows) {
this.rows = rows;
}
private class MyMouse extends MouseAdapter {
@Override
public void mousePressed(MouseEvent e) {
JLabel selection = (JLabel) e.getSource();
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[r].length; c++) {
if (selection == grid[r][c]) {
selectedRow = r;
selectedCol = c;
int index = r * grid[r].length + c;
mainPanel.firePropertyChange(CELL_SELECTION, -1, index);
}
}
}
}
}
}
模型:
import java.beans.PropertyChangeListener;
import javax.swing.event.SwingPropertyChangeSupport;
public class Model {
public static final int ROWS = 75;
public static final int COLS = ROWS;
public static final String TOKEN = "token";
private Token[][] grid = new Token[ROWS][COLS];
private SwingPropertyChangeSupport pcSupport = new SwingPropertyChangeSupport(this);
public Model() {
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[r].length; c++) {
grid[r][c] = Token.VIDE;
}
}
}
public Token getToken(int row, int col) {
return grid[row][col];
}
public void setToken(Token token, int row, int col) {
Token oldValue = grid[row][col];
Token newValue = token;
grid[row][col] = token;
int index = row * grid[row].length + col;
pcSupport.fireIndexedPropertyChange(TOKEN, index, oldValue, newValue);
}
public void addPropertyChangeListener(PropertyChangeListener listener) {
pcSupport.addPropertyChangeListener(listener);
}
public void addPropertyChangeListener(String name, PropertyChangeListener listener) {
pcSupport.addPropertyChangeListener(name, listener);
}
public int getRows() {
return ROWS;
}
public int getCols() {
return COLS;
}
}
主类:
import javax.swing.SwingUtilities;
public class Pha {
public static void main(String[] args) {
// run all on the Swing event thread
SwingUtilities.invokeLater(() -> {
Model model = new Model();
View view = new View();
Control control = new Control(model, view);
control.start();
});
}
}
推荐答案
在下面的代码中，我删除了所有对于演示请求的算法来说不是必需的东西.该代码确实包含一些用于测试的数据.
我认为发布 mcve 对高质量的问题和答案非常有帮助.太多的信息和太少一样糟糕.
该代码根据请求搜索路径.请注意，它不会搜索任何特定的路径属性(例如最短或最长路径).
此外，编写的代码寻找一条路径.他们可能更多.
我假设您需要研究代码以使其适应您的需求，进一步测试它，并希望对其进行改进.
In the following code, I removed everything which is not essential to demonstrate the requested algorithm. The code does include some data for testing.
I think posting a mcve is very helpful for quality questions and answers. Too much information is as bad as too little.
The code searches a path as requested. Please note that it does not search for any particular path property (like shortest ot longest path).
Also, the code as written looks for one path. Their may be more.
I assume you'll need to study the code to adapt it to your needs, further test it, and hopefully improve it.
import java.awt.BasicStroke;
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Container;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
public final class Pha extends JFrame {
//a collection of cells in the path.
//each cell represented by [row,col]
private Stack<int[]>path;
//a path shorter than min can not surround any cell
private static final int MIN_PATH_LEGTH = 4;
//a collection of cells that has been tested
private ArrayList<int[]>checked;
//represents the cell where the search starts from
int[] origin;
//represents the token of the origin
Token originToken;
private static int ROWS = 15;
private static int COLS = ROWS;
private static int cellSize = 15;
private static int canvasWidth = (cellSize * COLS) + (ROWS *4) ;
private static int canvasHeight = cellSize * ROWS ;
private static int gridWidth = 1;
private static int halfGridWidth = gridWidth / 2;
private static int cellPadding = cellSize / 5;
private static int symbolSize = cellSize - (cellPadding * 2);
private static int symbolStrokeWidth = 3;
private enum Token{
VIDE, CERCLE_ROUGE, CERCLE_BLEU
}
private Token[][] board;
private final DrawCanvas canvas;
//used to set different test data
private static int testNumber = 0;
public Pha(){
canvas = new DrawCanvas();
canvas.setPreferredSize(new Dimension(canvasWidth, canvasHeight));
Container cp = getContentPane();
cp.setLayout(new BorderLayout());
cp.add(canvas, BorderLayout.EAST);
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
pack();
setTitle("Pha par esQmo");
setVisible(true);
board = new Token[ROWS][COLS];
initGame();
//fill some data for testing
int[] origin = loadtestData(board);
findPath(origin);
}
private void initGame(){
for(int ligne = 0; ligne < ROWS; ++ligne){
for(int colonne = 0; colonne < COLS; ++colonne){
board[ligne][colonne] = Token.VIDE;
}
}
}
//search for a path
private void findPath(int[] origin) {
//initialize path and checked
path = new Stack<>();
this.origin = origin;
int row = origin[0] , col = origin[1];
//represents the token of the origin
originToken = board[row][col];
//initialize list of checked items
checked = new CellsList();
boolean found = findPath(row, col);
if(found) {
printPath();
} else {
System.out.println("No path found");
}
}
//recursive method to find path. a cell is represented by its row, col
//returns true when path was found
private boolean findPath(int row, int col) {
//check if cell has the same token as origin
if(board[row][col] != originToken) {
return false;
}
int[] cell = new int[] {row, col};
//check if this cell was tested before to avoid checking again
if(checked.contains(cell)) {
return false;
}
//get cells neighbors
CellsList neighbors = getNeighbors(row, col);
//check if solution found. If path size > min and cell
//neighbors contain the origin it means that path was found
if((path.size() > MIN_PATH_LEGTH) && neighbors.contains(origin) ) {
path.add(cell);
return true;
}
//add cell to checked
checked.add(cell);
//add cell to path
path.add(cell);
//if path was not found check cell neighbors
for(int[] neighbor : neighbors ) {
boolean found = findPath(neighbor[0],neighbor[1]);
if(found) {
return true;
}
}
//path not found
path.pop(); //remove last element from stack
return false;
}
//return a list of all neighbors of cell row, col
private CellsList getNeighbors(int row, int col) {
CellsList neighbors = new CellsList();
for (int colNum = col - 1 ; colNum <= (col + 1) ; colNum +=1 ) {
for (int rowNum = row - 1 ; rowNum <= (row + 1) ; rowNum +=1 ) {
if(!((colNum == col) && (rowNum == row))) {
if(withinGrid (rowNum, colNum ) ) {
neighbors.add( new int[] {rowNum, colNum});
}
}
}
}
return neighbors;
}
private boolean withinGrid(int colNum, int rowNum) {
if((colNum < 0) || (rowNum <0) ) {
return false;
}
if((colNum >= COLS) || (rowNum >= ROWS)) {
return false;
}
return true;
}
private void printPath() {
System.out.print("Path : " );
for(int[] cell : path) {
System.out.print(Arrays.toString(cell));
}
System.out.println("");
}
class DrawCanvas extends JPanel{
@Override
public void paintComponent(Graphics g){
super.paintComponent(g);
setBackground(Color.WHITE);
g.setColor(Color.BLACK);
for(int ligne = 1; ligne < ROWS; ++ligne){
g.fillRoundRect(0, (cellSize * ligne) - halfGridWidth, canvasWidth - 1,
gridWidth, gridWidth, gridWidth);
}
for(int colonne = 1; colonne < COLS; ++colonne){
g.fillRoundRect((cellSize * colonne) - halfGridWidth, 0
, gridWidth, canvasHeight - 1,
gridWidth, gridWidth);
}
Graphics2D g2d = (Graphics2D)g;
g2d.setStroke(new BasicStroke(symbolStrokeWidth,
BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND));
for(int ligne = 0; ligne < ROWS; ++ligne){
for(int colonne = 0; colonne < COLS; ++colonne){
int x1 = (colonne * cellSize) + cellPadding;
int y1 = (ligne * cellSize) + cellPadding;
if(board[ligne][colonne] == Token.CERCLE_ROUGE){
g2d.setColor(Color.RED);
g2d.drawOval(x1, y1, symbolSize, symbolSize);
g2d.fillOval(x1, y1, symbolSize, symbolSize);
} else
if(board[ligne][colonne] == Token.CERCLE_BLEU){
int x2 = (colonne * cellSize) + cellPadding;
g2d.setColor(Color.BLUE);
g2d.drawOval(x1, y1, symbolSize, symbolSize);
g2d.fillOval(x2, y1, symbolSize, symbolSize);
}
}
}
}
}
public static void main(String[] args){
//set test number. Change values between 0-2 to run different tests
testNumber = 2;
SwingUtilities.invokeLater(() -> {
new Pha();
});
}
//method used for testing only: load test data
private static int[] loadtestData(Token[][] board) {
switch (testNumber) {
case 1:
board[6][6] = Token.CERCLE_ROUGE; //origin and target
board[6][7] = Token.CERCLE_ROUGE;
board[6][8] = Token.CERCLE_BLEU;
board[7][6] = Token.CERCLE_ROUGE;
board[7][7] = Token.CERCLE_BLEU;
board[7][8] = Token.CERCLE_BLEU;
board[8][6] = Token.CERCLE_ROUGE;
board[8][7] = Token.CERCLE_ROUGE;
board[8][8] = Token.CERCLE_ROUGE;
board[5][7] = Token.CERCLE_ROUGE;
board[5][8] = Token.CERCLE_ROUGE;
board[5][9] = Token.CERCLE_ROUGE;
board[6][9] = Token.CERCLE_ROUGE;
board[7][9] = Token.CERCLE_ROUGE;
return new int[] {6,6};
case 2:
//line 3
board[3][6] = Token.CERCLE_ROUGE;
//line 4
board[4][4] = Token.CERCLE_BLEU; //origin
board[4][5] = Token.CERCLE_BLEU;
board[4][6] = Token.CERCLE_BLEU;
board[4][8] = Token.CERCLE_BLEU;
//line5
board[5][3] = Token.CERCLE_BLEU;
board[5][5] = Token.CERCLE_ROUGE;
board[5][7] = Token.CERCLE_BLEU;
board[5][8] = Token.CERCLE_ROUGE;
board[5][9] = Token.CERCLE_BLEU;
//line 6
board[6][2] = Token.CERCLE_BLEU;
board[6][3] = Token.CERCLE_ROUGE;
board[6][4] = Token.CERCLE_ROUGE;
board[6][5] = Token.CERCLE_ROUGE;
board[6][6] = Token.CERCLE_ROUGE;
board[6][7] = Token.CERCLE_ROUGE;
board[6][8] = Token.CERCLE_ROUGE;
board[6][9] = Token.CERCLE_BLEU;
//line 7
board[7][3] = Token.CERCLE_BLEU;
board[7][4] = Token.CERCLE_BLEU;
board[7][5] = Token.CERCLE_BLEU;
board[7][6] = Token.CERCLE_BLEU;
board[7][7] = Token.CERCLE_ROUGE;
board[7][8] = Token.CERCLE_BLEU;
//line 8
board[8][3] = Token.CERCLE_ROUGE;
board[8][7] = Token.CERCLE_BLEU;
board[8][8] = Token.CERCLE_ROUGE;
board[8][9] = Token.CERCLE_BLEU;
//line 9
board[9][7] = Token.CERCLE_ROUGE;
board[9][8] = Token.CERCLE_BLEU;
board[9][9] = Token.CERCLE_ROUGE;
//line 10
board[10][8] = Token.CERCLE_ROUGE;
board[10][9] = Token.CERCLE_ROUGE;
return new int[] {4,4};
case 0: default:
board[6][6] = Token.CERCLE_ROUGE;
board[6][7] = Token.CERCLE_ROUGE; //origin and target
board[6][8] = Token.CERCLE_BLEU;
board[7][6] = Token.CERCLE_ROUGE;
board[7][7] = Token.CERCLE_BLEU;
board[7][8] = Token.CERCLE_ROUGE;
board[8][6] = Token.CERCLE_ROUGE;
board[8][7] = Token.CERCLE_ROUGE;
board[8][8] = Token.CERCLE_ROUGE;
board[5][7] = Token.CERCLE_ROUGE;
board[5][8] = Token.CERCLE_ROUGE;
board[5][9] = Token.CERCLE_ROUGE;
board[6][9] = Token.CERCLE_ROUGE;
board[7][9] = Token.CERCLE_ROUGE;
return new int[] {6,7};
}
}
}
class CellsList extends ArrayList<int[]>{
@Override //override to check by the value of int[]
public boolean contains(Object o) {
for (int[] a : this) {
if(Arrays.equals(a, (int[]) o)) {
return true;
}
}
return false;
}
}
这篇关于二维数组中的寻路算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
