Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.03.2013, 14:04   #1
Wanz
 
Регистрация: 24.02.2013
Сообщений: 8
По умолчанию C# Волновой алгоритм поиска пути в лабиринте. Построение пути

Здравствуйте. Некоторое время назад с помощью товарища Phomm был нарыт консольный проект волнового алгоритма поиска пути в лабиринте. Программа строит волну, нет этапа 2 - отображения кратчайшего пути (или уж любого). Прикрутил к коду DataGredView. Вытащил код из методов и засунул в обработчики событий. Вопрос. По какому условию производить поиск самого пути? По какому условию проводить заливку? Есть у кого какие идеи?
Код:


using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        int[,] Map;
        int MapWidht = 10;//ширина
        int MapHeight = 10;//высота
        public Form1()
        {
            InitializeComponent();
        }
        private void button1_Click(object sender, EventArgs e)
        {
            dataGridView1.RowCount = 10;
            dataGridView1.ColumnCount = 10;

            Map = new int[,]{
                {1,1,1,1,1,1,1,1,1,1},           
                {1,0,0,0,0,0,0,0,0,1},
                {1,0,0,0,0,1,1,1,1,1},
                {1,0,0,0,0,0,0,0,0,1},
                {1,0,0,1,1,1,1,1,0,1},
                {1,0,0,1,1,1,1,1,0,1},           //карта
                {1,0,0,1,1,1,0,0,0,1},
                {1,0,0,0,0,1,0,0,0,1},
                {1,0,0,0,0,0,0,0,0,1},
                {1,1,1,1,1,1,1,1,1,1},
            };

            for (int y = 0; y < MapHeight; y++)
            {
                dataGridView1.Columns[y].Width = 25;  //задаю ширину столбцов
                dataGridView1.Rows[y].Cells[0].Value = "";
                for (int x = 0; x < MapWidht; x++)
                    if (Map[y, x] == 1)
                        dataGridView1.Rows[y].Cells[x].Value = "+";
                    else
                        dataGridView1.Rows[y].Cells[x].Value = " ";
            }


            FindWave(1, 1, 8, 8);//стартовая и финишная позиции
            for (int i = 0; i < 10; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    if (dataGridView1.Rows[i].Cells[j].Value.ToString() == " ")
                    {
                        dataGridView1.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Black;


                    }
                    if (dataGridView1.Rows[i].Cells[j].Value.ToString() == "S")
                    {
                        dataGridView1.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Red;


                    }
                    if (dataGridView1.Rows[i].Cells[j].Value.ToString() == "F")
                    {
                        dataGridView1.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Green;
                    }
                }
            }


            //Проверка на существование пути
            bool flag = true;
            for (int i = 0; i < 10 & flag; i++)
            {
                for (int j = 0; j < 10; j++)
                {

                    if (dataGridView1.Rows[i].Cells[j].Value.ToString() == "-1")
                    {
                        MessageBox.Show("Путь не существует");
                        flag = false;
                        break;



                    }
                }
            }
            //----------------------------------------


        }
Вложения
Тип файла: rar Volna1.rar (67.6 Кб, 163 просмотров)
Wanz вне форума Ответить с цитированием
Старый 17.03.2013, 14:04   #2
Wanz
 
Регистрация: 24.02.2013
Сообщений: 8
По умолчанию

Код:
public void FindWave(int startX, int startY, int targetX, int targetY)
        {
            bool add = true;
            int[,] cMap = new int[MapHeight, MapWidht];
            int x, y, step = 0;
            for (y = 0; y < MapHeight; y++)
                for (x = 0; x < MapWidht; x++)
                {
                    if (Map[y, x] == 1)
                        cMap[y, x] = -2;//индикатор стены
                    else
                        cMap[y, x] = -1;//индикатор еще не ступали сюда
                }
            cMap[targetY, targetX] = 0;//Начинаем с финиша
            while (add == true)
            {
                add = false;
                for (y = 0; y < MapWidht; y++)
                    for (x = 0; x < MapHeight; x++)
                    {
                        if (cMap[x, y] == step)
                        {

                            //Ставим значение шага+1 в соседние ячейки (если они проходимы)
                            if (y - 1 >= 0 && cMap[x, y - 1] != -2 && cMap[x, y - 1] == -1)
                                cMap[x, y - 1] = step + 1;
                            if (x - 1 >= 0 && cMap[x - 1, y] != -2 && cMap[x - 1, y] == -1)
                                cMap[x - 1, y] = step + 1;

                            if (y + 1 < MapWidht && cMap[x, y + 1] != -2 && cMap[x, y + 1] == -1)
                                cMap[x, y + 1] = step + 1;
                            if (x + 1 < MapHeight && cMap[x + 1, y] != -2 && cMap[x + 1, y] == -1)
                                cMap[x + 1, y] = step + 1;
                        }

                    }
                step++;

                add = true;
                if (cMap[startY, startX] != -1)//решение найдено
                    add = true;
                if (step > MapWidht * MapHeight)//решение не найдено
                    add = false;
            }
            //Отрисовываем карты
            for (y = 0; y < MapHeight; y++)
            {

                for (x = 0; x < MapWidht; x++)
                    if (cMap[y, x] == -1)
                        dataGridView1.Rows[y].Cells[x].Value = "-1";
                    else
                        if (cMap[y, x] == -2)
                            dataGridView1.Rows[y].Cells[x].Value = " ";
                        else
                            if (y == startY && x == startX)

                                dataGridView1.Rows[y].Cells[x].Value = "S";
                            else
                                if (y == targetY && x == targetX)
                                    dataGridView1.Rows[y].Cells[x].Value = "F";
                                else
                                    if (cMap[y, x] > -1)
                                        dataGridView1.Rows[y].Cells[x].Value = cMap[y, x];
            }

        }



        private void button2_Click(object sender, EventArgs e)
        {   //тут я пытался расчитать маршрут, бред, но все же...
            for (int i = 0; i < 10; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    if (dataGridView1.Rows[i].Cells[j].Value.ToString() == "F")
                    {
                        string a = (dataGridView1.Rows[i - 1].Cells[j - 1].Value.ToString());
                        string b = (dataGridView1.Rows[i - 1].Cells[j].Value.ToString());
                        string c = (dataGridView1.Rows[i].Cells[j - 1].Value.ToString());

                        int a1 = Convert.ToInt32(a);
                        int a2 = Convert.ToInt32(b);
                        int a3 = Convert.ToInt32(c);

                        int a11 = Math.Min(a1, a2);
                        int min = Math.Min(a11, a3);
                        textBox1.Text = min.ToString();
                        if (min == a1)
                        { dataGridView1.Rows[i - 1].Cells[j - 1].Value = "F"; }
                        else if (min == a2)
                        { dataGridView1.Rows[i - 1].Cells[j].Value = "F"; }
                        else if (min == a3)
                        { dataGridView1.Rows[i].Cells[j - 1].Value = "F"; }





                    }
                }

            }

        }
    }
}
продолжение, т.к. код не влез.
Wanz вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск пути в лабиринте. Маршрутный алгоритм. C# Wanz Помощь студентам 9 17.03.2013 18:56
Поиск самого дешёвого пути. Волновой алгоритм girlbuuuger Помощь студентам 16 13.02.2012 20:39
алгоритм поиска пути Ksssssssu Общие вопросы C/C++ 0 06.05.2011 13:05
Алгоритм поиска пути Ksssssssu Общие вопросы C/C++ 2 26.04.2011 05:43
программы для поиска пути в лабиринте. Пролог loshara_de_kontara Помощь студентам 2 19.11.2008 21:46