Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Java
Перезагрузить страницу Алгоритм поиска и обход всех точек
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
zaubra zaubra вне форума
Новичок
 
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 30.06.2011
По умолчанию Алгоритм поиска и обход всех точек - 03.05.2013, 13:08

Привет всем !
Возникла проблема с задачей, нужно помощь...
Необходимо реализовать программу реализующая алгоритм поиска, почитав литературу выбрал поиск в ширину.
Задача состоит в том чтобы пройти по некой фигуре, при этом закрашивая квадратики.(Фигура в начале кода, 1-окрашено, 0-нет) По закрашенным квадратикам ходить нельзя дважды. В конечном итоге нужно с помощью Swing это нарисовать, с некой анимацией хода, раскрашивая квадратики за собой
С этими алгоритмами не особо знаком, теория вроде бы доступна описана, но вот реализовать не совсем получается.
Прилагаю код - кое что сделал, закрашивает с анимацией но не в том порядке.
Java Код:
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Component;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JTable;
import javax.swing.Timer;
import javax.swing.table.DefaultTableCellRenderer;

public class GUI implements ActionListener {

    JFrame frame;
    JTable table;
    private int index;
    Graph theGraph;
    int[][] grid = {
            { 0, 0, 0, 1, 0, 0, 1, 0, 0, 0 },
            { 0, 0, 1, 1, 1, 1, 1, 1, 0, 0 },
            { 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 },
            { 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 },
            { 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 },
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
            { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
            { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
            { 1, 0, 0, 1, 1, 1, 1, 0, 0, 1 },
            { 1, 0, 1, 1, 0, 0, 1, 1, 0, 1 },
            { 1, 0, 1, 1, 0, 0, 1, 1, 0, 1 },
            { 0, 0, 1, 1, 0, 0, 1, 1, 0, 0 },
            { 0, 0, 1, 1, 0, 0, 1, 1, 0, 0 },
            { 0, 0, 1, 1, 0, 0, 1, 1, 0, 0 },
            { 0, 0, 1, 1, 0, 0, 1, 1, 0, 0 }
    };
   
    ArrayList<String> arrayList = new ArrayList<String>();
    /**
     * param args
     */

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        GUI gui = new GUI();
        gui.drawGUI();

    }

    public void readMatrix() {
        theGraph = new Graph();
        for (int i = 14; i >= 0; i--) {
            for (int j = 9; j >= 0; j--) {
                if (grid[i][j]!=0) {
                    table.setValueAt(i+""+j, i, j);
                    theGraph.addVertex(i+""+j+" ");
                    if (!arrayList.contains(i+""+j)) {
                        arrayList.add(i+""+j);
                    }
                } else {
                    table.setValueAt(0, i, j);
                }
            }
        }
        for (int h = arrayList.size()-1; h >= 0; h--) {
            int element = Integer.parseInt(arrayList.get(h));
            for (int k = arrayList.size()-1; k >= 0; k--) {
                int newElement = Integer.parseInt(arrayList.get(k));
                if (newElement-element==1 | newElement-element==10) {
                    theGraph.addEdge(h, k);
                }
            }
        }
    }
   
    public void drawGUI() {
        table = new JTable(15, 10);
        JButton startButton = new JButton();
        startButton.setText("start");
        startButton.addActionListener(this);
       
       
        table.setDefaultRenderer(Object.class, new DefaultColor());
        frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(300, 310);
        frame.setVisible(true);
        frame.getContentPane().add(table);
        frame.getContentPane().add(BorderLayout.SOUTH, startButton);
        readMatrix();
        System.out.println("Посещения: ");
        theGraph.bfs();
       
    }
   
    class PaintCell extends DefaultTableCellRenderer {
        private static final long serialVersionUID = 1L;
        public Component getTableCellRendererComponent(JTable table,
                Object value, boolean isSelected, boolean hasFocus, int row,
                int column) {
            Component c = super.getTableCellRendererComponent(table, value,
                    isSelected, hasFocus, row, column);
            String cell = table.getValueAt(row, column).toString();
            c.setBackground(Integer.parseInt(cell) >= Integer.parseInt(arrayList.get(index)) ? Color.GREEN : null);
            c.setForeground(Integer.parseInt(cell) >= Integer.parseInt(arrayList.get(index)) ? Color.GREEN : Color.WHITE);
            return c;
        }
    }
   
    class DefaultColor extends DefaultTableCellRenderer {
        private static final long serialVersionUID = 1L;
        public Component getTableCellRendererComponent(JTable table,
                Object value, boolean isSelected, boolean hasFocus, int row,
                int column) {
            Component c = super.getTableCellRendererComponent(table, value,
                    isSelected, hasFocus, row, column);
            int cell = Integer.parseInt(table.getValueAt(row, column).toString());
            if (cell!=0) {
                c.setBackground(Color.LIGHT_GRAY);
                c.setForeground(Color.LIGHT_GRAY);
            } else {
                c.setBackground(Color.WHITE);
                c.setForeground(Color.WHITE);
            }
            return c;
        }
    }
   
   
    static class Queue {
        private final int SIZE = 80;
        private int[] queArray;
        private int front;
        private int rear;
 
        public Queue() {
            queArray = new int[SIZE];
            front = 0;
            rear = -1;
        }
 
        public void insert(int j) // put item at rear of queue
        {
            if (rear == SIZE - 1)
                rear = -1;
            queArray[++rear] = j;
        }
 
        public int remove() // take item from front of queue
        {
            int temp = queArray[front++];
            if (front == SIZE)
                front = 0;
            return temp;
        }
 
        public boolean isEmpty() // true if queue is empty
        {
            return (rear + 1 == front || (front + SIZE - 1 == rear));
        }
    }
 
    static class Vertex {
        public String label; // label
        public boolean wasVisited;
 
        public Vertex(String l) {
            label = l;
            wasVisited = false;
        }
    }
 
    static class Graph {
        private final int MAX_VERTS = 80;
        private Vertex vertexList[]; // list of vertices
        private int adjMat[][]; // adjacency matrix
        private int nVerts; // current number of vertices
        private Queue theQueue;
 
        public Graph() {
            vertexList = new Vertex[MAX_VERTS];
            // adjacency matrix
            adjMat = new int[MAX_VERTS][MAX_VERTS];
            nVerts = 0;
            for (int j = 0; j < MAX_VERTS; j++)
                // set adjacency
                for (int k = 0; k < MAX_VERTS; k++)
                    // matrix to 0
                    adjMat[j][k] = 0;
            theQueue = new Queue();
        }
 
        public void addVertex(String l) {
            vertexList[nVerts++] = new Vertex(l);
        }
 
        public void addEdge(int start, int end) {
            adjMat[start][end] = 1;
            adjMat[end][start] = 1;
        }
 
        public void displayVertex(int v) {
            System.out.print(vertexList[v].label);
           
        }
 
        // breadth-first search
        public void bfs()
        { // begin at vertex 0
            vertexList[0].wasVisited = true; // mark it
            displayVertex(0); // display it
            theQueue.insert(0); // insert at tail
            int v2;
 
            while (!theQueue.isEmpty()) // until queue empty,
            {
                int v1 = theQueue.remove(); // remove vertex at head
                // until it has no unvisited neighbors
                while ((v2 = getAdjUnvisitedVertex(v1)) != -1) { // get one,
                    vertexList[v2].wasVisited = true; // mark it
                    displayVertex(v2); // display it
                    theQueue.insert(v2); // insert it
                }
            }
            // queue is empty, so we're done
            for (int j = 0; j < nVerts; j++)
                // reset flags
                vertexList[j].wasVisited = false;
        }
 
        // returns an unvisited vertex adj to v
        public int getAdjUnvisitedVertex(int v) {
            for (int j = 0; j < nVerts; j++)
                if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false)
                    return j;
            return -1;
        }
    }

    Override
    public void actionPerformed(ActionEvent arg0) {
        table.setDefaultRenderer(Object.class, new PaintCell());
        startAnimation();
    }
   
    private void startAnimation() {
        Timer timer = new Timer(20, new ActionListener() {
            Override
            public void actionPerformed(ActionEvent e) {
                index++;
                if (index > 79)
                    index = 0;
                table.repaint();
            }
        });
        timer.setRepeats(true);
        timer.start();
    }
}
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
алгоритм поиска блоков в графе Blair Любые вопросы от новичков 0 31.05.2012 18:22
Усложненный алгоритм бинарного поиска jrsmith Алгоритмы 3 01.10.2010 11:32
Алгоритм пересечения геометрических мест точек Ratozey Алгоритмы 1 25.05.2009 18:25
Алгоритм поиска похожих моментов в массиве bulzz Алгоритмы 1 22.04.2009 09:50
универсальный алгоритм для поиска массивов Red1Kk Алгоритмы 23 10.03.2008 13:49
Логическая задачка. Обход всех вершин графа kyzya Prolog 1 25.11.2006 19:13
Нужен алгоритм поиска в текстовом файле Аваддон C++ Builder 4 02.04.2006 09:11
Алгоритм поиска - метод перемешивание Дева Алгоритмы 6 16.01.2006 12:19
Алгоритм сортировки и поиска в больших числах noirum Вопросы начинающих программистов 9 19.11.2005 16:04
Как построить алгоритм поиска кратчайшего пути Себастьян Вопросы начинающих программистов 3 18.06.2005 15:06
Алгоритм поиска пути blur Алгоритмы 6 30.05.2005 21:16
Дана матрица целых чисел размером 10*12. Напечатайте индексы всех ее седловых точек Timik Pascal 7 10.02.2005 12:40



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов