根据二维网格阵列上的单元格值查找路径
Finding path depending on cells' value on 2D grid array
我有一个用 JLabel 组成的网格。每个细胞有 3 种状态：
public 枚举令牌{
视频，CERCLE_ROUGE，CERCLE_BLEU
}
空单元格 == Token.VIDE
我有这个简单的算法可以找到给定单元格的所有邻居，然后我使用 swing 自定义绘画沿着以标签中心为点的路径绘制多边形。
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;
}
这里是有路径的条件：
if((size() >= MIN_PATH_LEGTH) && neighbors.contains(origin) ) {
add(cell);
return true;
}
现在我想通过添加条件使其更精确，例如如果在邻域中至少有 4 个单元格具有相同的值并且至少有一个相反的值，则路径是有效的。
示例：
(11, 10)(10, 11)(11, 12)(12, 11) 处的红色单元格可以形成有效路径，前提是 (11, 11)。 （见下图）
以下不能是有效路径，所以没有绘图：
目前，该算法仅找到我定义的最小值 (int MIN_PATH_LEGTH = 3) 的路径，但我找不到定义第二个条件的方法 ( 至少邻域内一个相反的像元值)
如果需要，我会使用新元素进行编辑。
也许您可以列出蓝色单元格和红色单元格，如果您想测试红色单元格的路径中是否有蓝色单元格，您可以：
去北，直到你遇到一个红色单元格或地图限制：如果它是一个地图限制，你用下一个蓝色单元格测试，否则你回到你的位置，对东、南、西做同样的事情。
如果在 4 个边上你首先找到一个 redCell，你 return true 否则你 return false。
如果你想在一个很小的地图上测试就足够了。但是如果红细胞做出来的形状可以是自由的我就没有更好的办法了
在调用此方法之前测试 redCell 的路径是否正常：
public boolean isThereABlueCellWithinMyRedPath() {
// height = height of your map
// width = width of yout map
// this array is suppose to be in an other place...
Cell[][] cellArray = new Cell[height][width];
// ... so are those two lists
List<Cell> blueCellsList = new ArrayList<>();
List<Cell> redCellsList = new ArrayList<>();
//foreach blueCell on the map ...
for (Cell blueCell : blueCellsList) {
boolean north = false;
boolean east = false;
boolean south = false;
boolean west = false;
int originX = blueCell.getX();
int originY = blueCell.getY();
// ... if there is a redCell at north...
for (int i = originY; i >= 0; i--) {
if (redCellsList.contains(cellArray[originX][i])) {
north = true;
break;
}
}
// ... East ...
for (int i = originX; i < cellArray[originX].length; i++) {
if (redCellsList.contains(cellArray[i][originY])) {
east = true;
break;
}
}
// ... South ...
for (int i = originY; i < cellArray.length; i++) {
if (redCellsList.contains(cellArray[originX][i])) {
south = true;
break;
}
}
// ... West ...
for (int i = originX; i >= 0; i--) {
if (redCellsList.contains(cellArray[i][originY])) {
west = true;
break;
}
}
// ... I am surrended by redCell
if (south && east && north && west)
return true;
}
return false;
}
我没有尝试代码，但它似乎有效。
我的回答基于 .
中发布的代码
路径class
添加 isWithinLoop 通过检查单元格是否具有
路径单元格到它的左边，右边，顶部和底部。
同时添加getContainedWithin，其中returns所有以路径为界的单元格的集合，它们的标记颜色与路径相反
//returns a collection of all cells that are bounded by the path
//and their token is of the opposite color of the path
List<int[]> getContainedWithin() {
//find path max and min X values, max and min Y values
minPathRow = grid[0].length; //set min to the largest possible value
maxPathCol = grid.length;
maxPathRow = 0; //set max to the largest possible value
maxPathCol = 0;
//find the actual min max x y values of the path
for (int[] cell : this) {
minPathRow = Math.min(minPathRow, cell[0]);
minPathCol = Math.min(minPathCol, cell[1]);
maxPathRow = Math.max(maxPathRow, cell[0]);
maxPathCol = Math.max(maxPathCol, cell[1]);
}
//todo remove after testing
System.out.println("x range: "+minPathRow + "-"
+ maxPathRow + " y range: " + minPathCol + "-" + maxPathCol);
List<int[]> block = new ArrayList<>(25);
int[] cell = get(0);//get an arbitrary cell in the path
Token pathToken = grid[cell[0]][cell[1]]; //keep a reference to its token
//iterate over all cells within path x, y limits
for (int col = minPathCol; col < (maxPathCol); col++) {
for (int row = minPathRow; row < (maxPathRow); row++) {
//check cell color
Token token = grid[row][col];
if ((token == pathToken) || (token == Token.VIDE)) {
continue;
}
if (isWithinLoop(row,col)) {
block.add(new int[] {row, col});
}
}
}
return block;
}
//check if row, col represent a cell with in path by checking if it has a
//path-cell to its left, right, top and bottom
private boolean isWithinLoop(int row, int col) {
if( isPathCellOnLeft(row, col)
&&
isPathCellOnRight(row, col)
&&
isPathCellOnTop(row, col)
&&
isPathCellOnBottom(row, col)
) {
return true;
}
return false;
}
private boolean isPathCellOnLeft(int cellRow, int cellCol) {
for ( int col = minPathCol; col < cellCol ; col++) {
if(getPath().contains(new int[] {cellRow, col})) {
return true;
}
}
return false;
}
private boolean isPathCellOnRight(int cellRow, int cellCol) {
for ( int col = cellCol; col <= maxPathCol ; col++) {
if(getPath().contains(new int[] {cellRow, col})) {
return true;
}
}
return false;
}
private boolean isPathCellOnTop(int cellRow, int cellCol) {
for ( int row =minPathRow; row < cellRow ; row++) {
if(getPath().contains(new int[] {row, cellCol})) {
return true;
}
}
return false;
}
private boolean isPathCellOnBottom(int cellRow, int cellCol) {
for ( int row = cellRow; row <= maxPathRow; row++) {
if(getPath().contains(new int[] {row, cellCol})) {
return true;
}
}
return false;
}
}
型号class
添加一个getter方法来访问getContainedWithin:
List<int[]> getContainedWithin() {
return (path == null ) ? null : path.getContainedWithin();
}
控制class
如果 getContainedWithin 为空，请更新 ModelListener 以忽略路径：
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();
SwingUtilities.invokeLater(new Runnable() {
@Override
public void run() {
view.setCell(token, row, col);
CellsList path = model.getPath();
//ignore path if null, empty or encloses no cell
if((path == null) || path.isEmpty()
|| model.getContainedWithin().isEmpty()) {
return;
}
view.addPath(path);
view.refresh();
}
});
}
}
可以下载此repo的完整代码。
我有一个用 JLabel 组成的网格。每个细胞有 3 种状态： public 枚举令牌{ 视频，CERCLE_ROUGE，CERCLE_BLEU } 空单元格 == Token.VIDE
我有这个简单的算法可以找到给定单元格的所有邻居，然后我使用 swing 自定义绘画沿着以标签中心为点的路径绘制多边形。
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;
}
这里是有路径的条件：
if((size() >= MIN_PATH_LEGTH) && neighbors.contains(origin) ) {
add(cell);
return true;
}
现在我想通过添加条件使其更精确，例如如果在邻域中至少有 4 个单元格具有相同的值并且至少有一个相反的值，则路径是有效的。
示例： (11, 10)(10, 11)(11, 12)(12, 11) 处的红色单元格可以形成有效路径，前提是 (11, 11)。 （见下图）
以下不能是有效路径，所以没有绘图：
目前，该算法仅找到我定义的最小值 (int MIN_PATH_LEGTH = 3) 的路径，但我找不到定义第二个条件的方法 ( 至少邻域内一个相反的像元值)
如果需要，我会使用新元素进行编辑。
也许您可以列出蓝色单元格和红色单元格，如果您想测试红色单元格的路径中是否有蓝色单元格，您可以：
去北，直到你遇到一个红色单元格或地图限制：如果它是一个地图限制，你用下一个蓝色单元格测试，否则你回到你的位置，对东、南、西做同样的事情。 如果在 4 个边上你首先找到一个 redCell，你 return true 否则你 return false。
如果你想在一个很小的地图上测试就足够了。但是如果红细胞做出来的形状可以是自由的我就没有更好的办法了
在调用此方法之前测试 redCell 的路径是否正常：
public boolean isThereABlueCellWithinMyRedPath() {
// height = height of your map
// width = width of yout map
// this array is suppose to be in an other place...
Cell[][] cellArray = new Cell[height][width];
// ... so are those two lists
List<Cell> blueCellsList = new ArrayList<>();
List<Cell> redCellsList = new ArrayList<>();
//foreach blueCell on the map ...
for (Cell blueCell : blueCellsList) {
boolean north = false;
boolean east = false;
boolean south = false;
boolean west = false;
int originX = blueCell.getX();
int originY = blueCell.getY();
// ... if there is a redCell at north...
for (int i = originY; i >= 0; i--) {
if (redCellsList.contains(cellArray[originX][i])) {
north = true;
break;
}
}
// ... East ...
for (int i = originX; i < cellArray[originX].length; i++) {
if (redCellsList.contains(cellArray[i][originY])) {
east = true;
break;
}
}
// ... South ...
for (int i = originY; i < cellArray.length; i++) {
if (redCellsList.contains(cellArray[originX][i])) {
south = true;
break;
}
}
// ... West ...
for (int i = originX; i >= 0; i--) {
if (redCellsList.contains(cellArray[i][originY])) {
west = true;
break;
}
}
// ... I am surrended by redCell
if (south && east && north && west)
return true;
}
return false;
}
我没有尝试代码，但它似乎有效。
我的回答基于
路径class
添加 isWithinLoop 通过检查单元格是否具有
路径单元格到它的左边，右边，顶部和底部。
同时添加getContainedWithin，其中returns所有以路径为界的单元格的集合，它们的标记颜色与路径相反
//returns a collection of all cells that are bounded by the path
//and their token is of the opposite color of the path
List<int[]> getContainedWithin() {
//find path max and min X values, max and min Y values
minPathRow = grid[0].length; //set min to the largest possible value
maxPathCol = grid.length;
maxPathRow = 0; //set max to the largest possible value
maxPathCol = 0;
//find the actual min max x y values of the path
for (int[] cell : this) {
minPathRow = Math.min(minPathRow, cell[0]);
minPathCol = Math.min(minPathCol, cell[1]);
maxPathRow = Math.max(maxPathRow, cell[0]);
maxPathCol = Math.max(maxPathCol, cell[1]);
}
//todo remove after testing
System.out.println("x range: "+minPathRow + "-"
+ maxPathRow + " y range: " + minPathCol + "-" + maxPathCol);
List<int[]> block = new ArrayList<>(25);
int[] cell = get(0);//get an arbitrary cell in the path
Token pathToken = grid[cell[0]][cell[1]]; //keep a reference to its token
//iterate over all cells within path x, y limits
for (int col = minPathCol; col < (maxPathCol); col++) {
for (int row = minPathRow; row < (maxPathRow); row++) {
//check cell color
Token token = grid[row][col];
if ((token == pathToken) || (token == Token.VIDE)) {
continue;
}
if (isWithinLoop(row,col)) {
block.add(new int[] {row, col});
}
}
}
return block;
}
//check if row, col represent a cell with in path by checking if it has a
//path-cell to its left, right, top and bottom
private boolean isWithinLoop(int row, int col) {
if( isPathCellOnLeft(row, col)
&&
isPathCellOnRight(row, col)
&&
isPathCellOnTop(row, col)
&&
isPathCellOnBottom(row, col)
) {
return true;
}
return false;
}
private boolean isPathCellOnLeft(int cellRow, int cellCol) {
for ( int col = minPathCol; col < cellCol ; col++) {
if(getPath().contains(new int[] {cellRow, col})) {
return true;
}
}
return false;
}
private boolean isPathCellOnRight(int cellRow, int cellCol) {
for ( int col = cellCol; col <= maxPathCol ; col++) {
if(getPath().contains(new int[] {cellRow, col})) {
return true;
}
}
return false;
}
private boolean isPathCellOnTop(int cellRow, int cellCol) {
for ( int row =minPathRow; row < cellRow ; row++) {
if(getPath().contains(new int[] {row, cellCol})) {
return true;
}
}
return false;
}
private boolean isPathCellOnBottom(int cellRow, int cellCol) {
for ( int row = cellRow; row <= maxPathRow; row++) {
if(getPath().contains(new int[] {row, cellCol})) {
return true;
}
}
return false;
}
}
型号class
添加一个getter方法来访问getContainedWithin:
List<int[]> getContainedWithin() {
return (path == null ) ? null : path.getContainedWithin();
}
控制class
如果 getContainedWithin 为空，请更新 ModelListener 以忽略路径：
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();
SwingUtilities.invokeLater(new Runnable() {
@Override
public void run() {
view.setCell(token, row, col);
CellsList path = model.getPath();
//ignore path if null, empty or encloses no cell
if((path == null) || path.isEmpty()
|| model.getContainedWithin().isEmpty()) {
return;
}
view.addPath(path);
view.refresh();
}
});
}
}
可以下载此repo的完整代码。