Advertisement
Guest User

Untitled

a guest
Feb 6th, 2011
3,878
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.65 KB | None | 0 0
  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Scanner;
  6. import java.util.Stack;
  7.  
  8. /**
  9.  * Простенький класс, представляющий таблицу. Никаких проверок.
  10.  * @author alesha
  11.  *
  12.  * @param <E>
  13.  */
  14. class Table<E> {
  15.     List<List<E>> list = new ArrayList<List<E>>();
  16.    
  17.     public void addLine(List<E> line) {
  18.         list.add(line);
  19.     }
  20.    
  21.     public E get(int y, int x) {
  22.         return list.get(y).get(x);
  23.     }
  24.    
  25.     public void set(int y, int x, E value) {
  26.         list.get(y).set(x, value);
  27.     }
  28.    
  29.     public int cols(int row) {
  30.         return list.get(row).size();
  31.     }
  32.    
  33.     public int rows() {
  34.         return list.size();
  35.     }
  36.    
  37.     @Override
  38.     public String toString() {
  39.         StringBuilder sb = new StringBuilder();
  40.        
  41.         for (List<E> row : list) {
  42.             for (E el : row) {
  43.                 sb.append(el).append(' ');
  44.             }
  45.             sb.append('\n');
  46.         }
  47.        
  48.         return sb.toString();
  49.     }
  50. }
  51.  
  52. public class Fill {
  53.     public static void main(String args[]) throws FileNotFoundException {
  54.         Table<Character> table = new Table<Character>();
  55.         File f = new File("fill.txt");
  56.        
  57.         Scanner scan = new Scanner(f);
  58.         String line;
  59.         List<Character> charLine;
  60.        
  61.         while (scan.hasNextLine()) {
  62.             line = scan.nextLine();
  63.            
  64.             charLine = new ArrayList<Character>();
  65.            
  66.             for (int i = 0; i < line.length(); i++) {
  67.                 charLine.add(line.charAt(i));
  68.             }
  69.            
  70.             table.addLine(charLine);
  71.         }
  72.        
  73.         System.out.println(table);
  74.        
  75.         fill(table, '1', 'x');
  76.        
  77.         System.out.println(table);
  78.        
  79.    
  80.     }
  81.    
  82.     public static int fill(Table<Character> table, Character toFind, Character toReplace) {
  83.         // счетчик найденных фигур
  84.         int count = 0;
  85.    
  86.         // внутренний класс для хранения координат
  87.         class Coord {
  88.             int y;
  89.             int x;
  90.            
  91.             public Coord(int y, int x) {
  92.                 this.y = y;
  93.                 this.x = x;
  94.             }
  95.         }
  96.        
  97.         Stack<Coord> stack = new Stack<Coord>();
  98.        
  99.         int[] nextRows = {-1, 1};
  100.        
  101.         // цикл по всем точкам
  102.         for (int i = 0; i < table.rows(); i++) {
  103.             for (int j = 0; j < table.cols(i); j++) {
  104.                 // если точка - искомая, то в этой фигуре запускаем заливку
  105.                 if (table.get(i, j).equals(toFind)) {
  106.                     // увеличиваем счетчик для найденных фигур
  107.                     count++;
  108.                    
  109.                     // запихиваем координаты точки в стек
  110.                     stack.push(new Coord(i, j));
  111.                     while (!stack.empty()) {
  112.                         // извлекаем координаты из стека
  113.                         Coord cur = stack.pop();
  114.                        
  115.                         // если извлеченная точка еще не закрашена - закрашиваем
  116.                         if (table.get(cur.y, cur.x).equals(toFind)) {
  117.                             table.set(cur.y, cur.x, toReplace);
  118.                         }
  119.                        
  120.                         // закрашиваем все точки слева от текущей
  121.                         int xl = cur.x - 1;
  122.                        
  123.                         while (xl >= 0 && table.get(cur.y, xl).equals(toFind)) {
  124.                             table.set(cur.y, xl, toReplace);
  125.                             xl--;
  126.                         }
  127.                        
  128.                         // закрашиваем все точки справа от текущей
  129.                         int xr = cur.x + 1;
  130.                        
  131.                         while (xr < table.cols(cur.y) && table.get(cur.y, xr).equals(toFind)) {
  132.                             table.set(cur.y, xr, toReplace);
  133.                             xr++;
  134.                         }
  135.                        
  136.                         // теперь переходим к строке снизу и сверху
  137.                         for (int k = 0; k < nextRows.length; k++) {
  138.                             int dy = nextRows[k];
  139.                            
  140.                             // проверяем, чтобы не вышло за пределы
  141.                             if (dy < 0 || dy >= table.rows()) {
  142.                                 continue;
  143.                             }
  144.                            
  145.                             // берем левое x и ищем начало строки для заливки
  146.                             int x = xl + 1;
  147.                            
  148.                             // пока x не достиг правого края только что залитой строки
  149.                             while (x < xr) {
  150.                                 int x0 = x;
  151.                                
  152.                                 // ищем то, что нужно заливать
  153.                                 while (x < xr && table.get(dy, x).equals(toFind)) {
  154.                                     x++;
  155.                                 }
  156.                                
  157.                                 // если не равно - значит хоть одна итерация была - добавляем точку в стек
  158.                                 if (x0 != x) {
  159.                                     stack.push(new Coord(dy, x));
  160.                                 }
  161.                                
  162.                                 // теперь пропускаем всё то, что заливать не надо - на случай "дырки"
  163.                                 while (x < xr && !table.get(dy, x).equals(toFind)) {
  164.                                     x++;
  165.                                 }
  166.                             }
  167.    
  168.                         }
  169.                        
  170.                     }
  171.        
  172.                 }
  173.                
  174.                
  175.             }
  176.         }
  177.            
  178.         return count;
  179.     }
  180. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement