问题描述
我已经在程序中为矩阵实现了洪水填充算法，我想选择从哪个方向开始。
我想检测由网格上的元素创建的循环：当网格上给定位置有一个元素时，矩阵中将显示1。
当没有任何东西时，它是0。当它是不会移动的元素时，它是2。洪水填充算法从1开始，并将遇到的每1变成2。
例：
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 2 1 1 1 1 0 0 0
0 0 2 0 0 0 1 0 0 0
0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
会成为：
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 2 2 2 2 2 0 0 0
0 0 2 0 0 0 2 0 0 0
0 0 2 2 2 2 2 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
这是我的代码：
import TUIO.*;
import java.util.Arrays;
import java.util.Scanner;
TuioProcessing tuioClient;
// Create matrix
static int[][] matrix = new int[10][10];
// these are some helper variables which are used
// to create scalable graphical feedback
int k, l, iD, x,y;
String myType;
void setup() {
size(1000, 600);
noCursor();
noStroke();
fill(0);
}
void draw() {
matrix [1][5]= 2;
matrix [1][6]= 2;
matrix [2][5]= 2;
matrix [2][6]= 2;
matrix [3][5]=1;
ArrayList<TuioObject> tuioObjectList = tuioClient.getTuioObjectList();
for (int i=0; i<tuioObjectList.size (); i++) {
TuioObject tobj= tuioObjectList.get(i);
stroke(0);
fill(0, 0, 0);
pushMatrix();
translate(tobj.getScreenX(width), tobj.getScreenY(height));
rotate(tobj.getAngle());
rect(-80, -40, 80, 40);
popMatrix();
fill(255);
x = round(10*tobj.getX ());
y = round(10*tobj.getY ());
iD = tobj.getSymbolID();
int taille = fiducialsList.length;
for (int o = 0; o<taille; o++) {
if (iD == o) {
myType = fiducialsList [o];
}
}
activList.add(new Fiducial (x, y, iD, myType));
fiducialCoordinates ();
matrix [x][y] = 1 ;
circuitState ();
for (int p = 0; p < 10; p++) {
for (int r = 0; r < 10; r++) {
System.out.print(matrix[p][r] + " ");
}
System.out.print("\n");
}
System.out.print("\n");
// activList.removeAll(activList);
}
for (int[] row : matrix)
Arrays.fill(row, 0);
}
public static class FloodFill {
public static void resolution(String[] args) {
solve(matrix, 2, 5, 3);
//result
System.out.println("-------------------");
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.print("\n");
}
System.out.print("\n");
}
public static void solve(int[][] matrix, int x, int y, int fillValue) {
if (x>=matrix.length)
return;
if (y>=matrix[x].length)
return;
int originValue=matrix[x][y];
matrix[x][y]=fillValue;
// Up
if (x-1>=0 && originValue==matrix[x-1][y])
solve(matrix, x-1, y, fillValue);
// Right
if (y+1<matrix[x].length && originValue==matrix[x][y+1])
solve(matrix, x, y+1, fillValue);
//south-east
// Down
if (x+1<matrix.length && originValue==matrix[x+1][y])
solve(matrix, x+1, y, fillValue);
//south-west
// Left
if (y-1>=0 && originValue==matrix[x][y-1])
solve(matrix, x, y-1, fillValue);
}
}
该算法是在FloodFill创建的。实际情况要复杂得多，所以这就是我的问题：给出起点后，如何防止它朝一个方向看（例如左侧）？
有没有办法做到这一点？
我不希望算法“看”起点左侧的位置。
它是Java，但在处理中使用。
1楼
通过注释，您要求一种允许您检查循环的算法。 下面的解决方案使用修改后的洪水填充来实现。
private static enum Direction{
UP,
RIGHT,
DOWN,
LEFT,
NONE;
}
public static boolean checkIfPositionIsInLoop(int[][] matrix, int x, int y, int fillValue){
int targetX = x;
int targetY = y;
return fillReachesTargetPosition(matrix, x, y, targetX, targetY, fillValue, Direction.LEFT /*don't allow it to start filling to the left*/);
}
private static boolean fillReachesTargetPosition(int[][] matrix, int x, int y, int targetX, int targetY, int fillValue, Direction forbiddenDirection) {
if (x>=matrix.length)
return false;
if (y>=matrix[x].length)
return false;
int originValue=matrix[x][y];
matrix[x][y]=fillValue;
int xToFillNext;
int yToFillNext;
boolean fillingReachedTargetPosition = false;
// Up
xToFillNext = x-1;
yToFillNext = y;
if(xToFillNext==targetX && yToFillNext==targetY && !forbiddenDirection.equals(Direction.UP)){
return true;
} else if (xToFillNext>=0 && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.UP)){
fillingReachedTargetPosition =
fillReachesTargetPosition(matrix, xToFillNext, yToFillNext, targetX, targetY, fillValue,Direction.DOWN /*Just came from up- don't allow it to try filling here again*/);
if(fillingReachedTargetPosition){
return true;
}
}
// Right
xToFillNext = x;
yToFillNext = y+1;
if(xToFillNext==targetX && yToFillNext==targetY && !forbiddenDirection.equals(Direction.RIGHT)){
return true;
} else if (yToFillNext<matrix[xToFillNext].length && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.RIGHT)) {
fillingReachedTargetPosition =
fillReachesTargetPosition(matrix, xToFillNext, yToFillNext,targetX, targetY, fillValue,Direction.LEFT /*Just came from right- don't allow it to try filling here again*/);
if(fillingReachedTargetPosition){
return true;
}
}
// Down
xToFillNext = x+1;
yToFillNext = y;
if(xToFillNext==targetX && yToFillNext==targetY && !forbiddenDirection.equals(Direction.DOWN)){
return true;
} else if (xToFillNext<matrix.length && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.DOWN)){
fillingReachedTargetPosition =
fillReachesTargetPosition(matrix, xToFillNext, yToFillNext, targetX, targetY, fillValue,Direction.UP /*Just came from up- don't allow it to try filling here again*/);
if(fillingReachedTargetPosition){
return true;
}
}
// Left
xToFillNext = x;
yToFillNext = y-1;
if(xToFillNext==targetX && yToFillNext==targetY && forbiddenDirection.equals(Direction.RIGHT)){
return true;
} else if (yToFillNext>=0 && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.LEFT)){
fillingReachedTargetPosition =
fillReachesTargetPosition(matrix, xToFillNext, yToFillNext, targetX, targetY, fillValue,Direction.RIGHT /*Just came from left- don't allow it to try filling here again*/);
if(fillingReachedTargetPosition){
return true;
}
}
return false;
}
这里是一个驱动程序，以演示它的作用：
public static void main(String[] arg){
System.out.println("Show matrix with loop, before fill");
int[][] matrix = getMatrixWithWideLoop();
printMatrix(matrix);
System.out.println("Found loop: "+checkIfPositionIsInLoop(matrix, 0, 2, 2 /*fill with 2s*/));
System.out.println("-----------------------------------------");
System.out.println("Show matrix without loop, before fill");
matrix = getMatrixWithoutLoop();
printMatrix(matrix);
System.out.println("Found loop: "+checkIfPositionIsInLoop(matrix, 0, 2, 2 /*fill with 2s*/));
System.out.println("-----------------------------------------");
System.out.println("Show matrix with small loop, before fill");
matrix = getMatrixWithSmallLoop();
printMatrix(matrix);
System.out.println("Found loop: "+checkIfPositionIsInLoop(matrix, 0, 2, 2 /*fill with 2s*/));
System.out.println("-----------------------------------------");
System.out.println("Show matrix without loop, before fill");
matrix = getMatrixWithoutLoop();
printMatrix(matrix);
System.out.println("Found loop: "+checkIfPositionIsInLoop(matrix, 0, 1, 2 /*fill with 2s*/));
}
并输出：
Show matrix with loop, before fill
01110
01010
01110
Found loop: true
-----------------------------------------
Show matrix without loop, before fill
01110
00010
01110
Found loop: false
-----------------------------------------
Show matrix with small loop, before fill
01100
01100
00000
Found loop: true
-----------------------------------------
Show matrix without loop, before fill
01110
00010
01110
Found loop: false