Advertisement
Guest User

BFS

a guest
Dec 17th, 2011
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.20 KB | None | 0 0
  1. public final class Path {
  2.  
  3.     public enum Block {
  4.         NONE,
  5.         ALL,
  6.         NORTH,
  7.         WEST,
  8.         SOUTH,
  9.         EAST
  10.     }
  11.    
  12.     private final int width;
  13.     private final int height;
  14.     private final Matrix<Block> blockMatrix;
  15.     private final Matrix<Integer> distanceMatrix;
  16.     private Set<Vector> sourceSet;
  17.     private final Set<Vector> targetSet;
  18.    
  19.     /* Constructors, getters and setters go here */
  20.    
  21.     private void initialize() {
  22.         distanceMatrix.reset();
  23.         for (Vector source : sourceSet) {
  24.             distanceMatrix.set(source, 0);
  25.             targetSet.remove(source);
  26.         }
  27.     }
  28.    
  29.     private void addReachableNeighbours(Vector source, int distance, Set<Vector> nextSourceSet) {
  30.        
  31.         /* iterate through a 3x3 square around the source */
  32.         for (int dx = -1; dx <= 1; dx++) {
  33.             for (int dy = -1; dy <= 1; dy++) {
  34.                
  35.                 /* discard the center (source) */
  36.                 if (dx != 0 && dy != 0) {
  37.                     int x = source.getX() + dx;
  38.                     int y = source.getY() + dy;
  39.                    
  40.                     /* check if in bounds */
  41.                     if (x >= 0 && x < width && y >= 0 && y < height) {
  42.                         Vector neighbour = new Vector(x, y);
  43.                        
  44.                         /* check if not reached already */
  45.                         if (distanceMatrix.get(neighbour) == null) {
  46.                            
  47.                             /* check if reachable */
  48.                             boolean block = false;
  49.                             switch (blockMatrix.get(neighbour)) {
  50.                             case ALL: block = true; break;
  51.                             case NORTH: block = dy == 1; break;
  52.                             case WEST: block = dx == 1; break;
  53.                             case SOUTH: block = dy == -1; break;
  54.                             case EAST: block = dx == -1; break;
  55.                             }
  56.                             if (block == false) {
  57.                                
  58.                                 /* add it as source, set distance and remove it as target */
  59.                                 nextSourceSet.add(neighbour);
  60.                                 distanceMatrix.set(neighbour, distance);
  61.                                 targetSet.remove(neighbour);
  62.                             }                          
  63.                         }
  64.                     }
  65.                 }
  66.             }
  67.         }
  68.     }
  69.    
  70.     private boolean iterate(int distance) {
  71.         Set<Vector> nextSourceSet = new HashSet<Vector>();
  72.         for (Vector source : sourceSet) {
  73.             addReachableNeighbours(source, distance, nextSourceSet);
  74.         }
  75.         sourceSet = nextSourceSet;
  76.         return (targetSet.isEmpty() == false) && (sourceSet.isEmpty() == false);
  77.     }
  78.    
  79.     public void compute() {
  80.         initialize();
  81.         int distance = 1;
  82.         while (iterate(distance)) distance = distance + 1;
  83.     }
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement