VPF::Минимальный путь передвижения коня

Nike3000

Дата 7.5.2009, 21:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 4.4.2009

Репутация: нет
Всего: нет

Здравствуйте!
Требуется решить данную задачу:
найти min путь передвижения коня по шахматной доске из 1 клетки во 2-ую

Не подскажите с чего начать реализацию??

maxdiver

Дата 7.5.2009, 22:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

Построить граф (вершины - клетки) и реализовать на нём обход в ширину.

Nike3000

Дата 8.5.2009, 13:04 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 4.4.2009

Репутация: нет
Всего: нет

Ну я знаю как это сделать руками..Нужно реализовать на компе...

Алгоритм такой:
сначала строим вершиный графов (вершины-те клетки куда конь сможет сходить)
после надо этот граф както вбить в матрицу, а потом уже там искать мин. путь от клетки1 до 2

Как вот вбить в матрицу граф?
клеток 8 на 8
формулы для хода у коня такие:
upright(x+1,y-2)
upleft(x-1,y-2)
leftup(x-2,y-1)
leftdown(x-2,y+1)
rightup(x+2,y-1)
rightdown(x+2,y+1)
downleft(x-1,y+2)
downright(x+1,y+2)

aram90

Дата 16.5.2009, 08:32 (ссылка)

(нет голосов)

Загрузка ...

Bug hunter

Профиль
Группа: Участник
Сообщений: 17
Регистрация: 1.12.2008
Где: Yerevan, Armenia

Репутация: 1
Всего: 3

В принципе, явно построить граф не обьязательно. Задачу можно решить и так - на матрице, оне все же будет задача на графах, но граф мы не построим явно. Я не понял что ты имеешь в виду: "вбить в матрицу граф". Вот код решения:

Код


#include <iostream>
#include <queue>
using namespace std;
int w[8][8];
bool visited[8][8]={0};
int parent_row[8][8];
int parent_col[8][8];
queue<int> q;
int drow[8]={+1,-1,-2,-2,+2,+2,-1,+1};
int dcol[8]={-2,-2,-1,+1,-1,+1,+2,+2};
void main()
{
    int row1,col1,row2,col2,row,col,next_row,next_col,k;
    cin>>row1>>col1>>row2>>col2;
    w[row1][col1]=0;
    visited[row1][col1]=true;
    q.push(row1);
    q.push(col1);
    while(!q.empty())
    {
        row=q.front(); q.pop();
        col=q.front(); q.pop();
        if(visited[row2][col2]) break;
        for(k=0;k<8;k++)
        {
            next_row=row+drow[k];
            next_col=col+dcol[k];
            if(next_row<0 || next_row>7 || next_col<0 || next_col>7 || visited[next_row][next_col]) continue;
            w[next_row][next_col]=w[row][col]+1;
            visited[next_row][next_col]=true;
            parent_row[next_row][next_col]=row;
            parent_col[next_row][next_col]=col;
            q.push(next_row);
            q.push(next_col);
        }
    }    
    cout<<w[row2][col2]<<endl;
    row=row2; col=col2;
    for(;;)
    {
        cout<<row<<' '<<col<<endl;
        if(row==row1 && col==col1) break;
        next_row=parent_row[row][col];
        next_col=parent_col[row][col];
        row=next_row;
        col=next_col;
    }
}

Это простой поиск в ширину (BFS) в графе, то есть на доске, который использует очередь.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »