我已经实现了一个洪水填充算法，矩阵在我的计划，我想选择在哪个方向开始。欲检测由上所述网格元件创建的循环：当有一个元素在网格上一个给定位置，一个1被显示在矩阵。当没有任何东西，它是一个0而当它是不会被移动的元素，这是一个2.洪水填充算法开始于一个1并接通每1它遇到成2. 例如：

I've implemented a flood fill algorithm for matrices in my program, and I'd like to choose in which direction it starts. I want to detect loops created by elements on the grid: When there is an element at a given place on the grid, a 1 is displayed in the matrix. When there isn't anything, it's a 0. And when it is elements that won't be moved, it's a 2. The flood fill algorithm starts on a 1 and turns every 1 it encounters into a 2. example:

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

下面是我的code：

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 class.The真实的案例创建很多更使这里复杂的是我的问题： 当一个出发点是给予，我怎么能prevent它看起来在一个方向（比如左）？有没有办法做到这一点？我不希望的算法看在上的起点的左侧的位置。

The algorithm is created in the FloodFill class.The real cases are a lot more complex so here is my problem: When a starting point is given, how can I prevent it to look in one direction (say on the left)? Is there a way to do this? I don't want the algorithm to "look" at the position on the left of the starting point.

这是java的，但在加工中使用。

It is java but used in Processing.

推荐答案

通过评论，你问一个算法，它允许你检查循环。下面的解决方案，这一点使用修改后的颜色填充一样。

Through comments, you've asked for an algorithm which allows you to check for loops. The solution below does this using a modified flood fill.

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;
  }

下面是一个驱动程序，以显示它在行动：

Here's a driver to show it in action:

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